Mixing
Proving the Fibonacci identity $(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$
$begingroup$
Prove that for two natural numbers $m$ and $k$, where $m>k$ the following identity holds:
$$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$$
Here the exercise comes with a hint:
The constant is $F^2 _m$, try to substitute $k=0$ in.
Okay fair enough, let us try this, this will give us:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}F_{m}) =F_{0}^2+F_{1}^2$$
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =F_{0}^2+F_{1}^2=0^2+1^2=1$$
We can now use a identity by Cassini, namely that for $m>0=k$ we have:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =(-1)^m(-1)^m=(-1)^{2m}=1 checkmark$$
Okay great, so our identity works whenever $k=0$, but I do not see how this helps with a generalisation.
Edit/idea: Did I just write down the base case for an approach via induction on $k$ perhaps?
sequences-and-series discrete-mathematics induction recurrence-relations fibonacci-numbers
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
$endgroup$
add a comment |
$begingroup$
Prove that for two natural numbers $m$ and $k$, where $m>k$ the following identity holds:
$$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$$
Here the exercise comes with a hint:
The constant is $F^2 _m$, try to substitute $k=0$ in.
Okay fair enough, let us try this, this will give us:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}F_{m}) =F_{0}^2+F_{1}^2$$
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =F_{0}^2+F_{1}^2=0^2+1^2=1$$
We can now use a identity by Cassini, namely that for $m>0=k$ we have:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =(-1)^m(-1)^m=(-1)^{2m}=1 checkmark$$
Okay great, so our identity works whenever $k=0$, but I do not see how this helps with a generalisation.
Edit/idea: Did I just write down the base case for an approach via induction on $k$ perhaps?
sequences-and-series discrete-mathematics induction recurrence-relations fibonacci-numbers
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
$endgroup$
1
$begingroup$
How about using mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
$endgroup$
– lab bhattacharjee
Jan 4 at 12:52
1
$begingroup$
This is a special case of the more general fact that if $a,b,c,d$ are any integers such that $a+b=c+d$ then $F_aF_b -F_cF_d = (-1)^{r}(F_{a+r}F_{b+r}-F_{c+r}F_{d+r})$ for any integer $r$. I know this by the name of Johnson’s bi-linear index formula. It can be proven using vajda’s identity.
$endgroup$
– Adam Higgins
Jan 4 at 14:20
add a comment |
$begingroup$
Prove that for two natural numbers $m$ and $k$, where $m>k$ the following identity holds:
$$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$$
Here the exercise comes with a hint:
The constant is $F^2 _m$, try to substitute $k=0$ in.
Okay fair enough, let us try this, this will give us:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}F_{m}) =F_{0}^2+F_{1}^2$$
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =F_{0}^2+F_{1}^2=0^2+1^2=1$$
We can now use a identity by Cassini, namely that for $m>0=k$ we have:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =(-1)^m(-1)^m=(-1)^{2m}=1 checkmark$$
Okay great, so our identity works whenever $k=0$, but I do not see how this helps with a generalisation.
Edit/idea: Did I just write down the base case for an approach via induction on $k$ perhaps?
sequences-and-series discrete-mathematics induction recurrence-relations fibonacci-numbers
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
$endgroup$
Prove that for two natural numbers $m$ and $k$, where $m>k$ the following identity holds:
$$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k}) =F_{k}^2+F_{k+1}^2$$
Here the exercise comes with a hint:
The constant is $F^2 _m$, try to substitute $k=0$ in.
Okay fair enough, let us try this, this will give us:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}F_{m}) =F_{0}^2+F_{1}^2$$
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =F_{0}^2+F_{1}^2=0^2+1^2=1$$
We can now use a identity by Cassini, namely that for $m>0=k$ we have:
$$ (−1)^{m}(F_{m+1}F_{m−1}−F_{m}^2) =(-1)^m(-1)^m=(-1)^{2m}=1 checkmark$$
Okay great, so our identity works whenever $k=0$, but I do not see how this helps with a generalisation.
Edit/idea: Did I just write down the base case for an approach via induction on $k$ perhaps?
sequences-and-series discrete-mathematics induction recurrence-relations fibonacci-numbers
sequences-and-series discrete-mathematics induction recurrence-relations fibonacci-numbers
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
edited Jan 4 at 13:46
Wesley Strik
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
asked Jan 4 at 12:40
Wesley StrikWesley Strik
1,660423
1,660423
1
$begingroup$
How about using mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
$endgroup$
– lab bhattacharjee
Jan 4 at 12:52
1
$begingroup$
This is a special case of the more general fact that if $a,b,c,d$ are any integers such that $a+b=c+d$ then $F_aF_b -F_cF_d = (-1)^{r}(F_{a+r}F_{b+r}-F_{c+r}F_{d+r})$ for any integer $r$. I know this by the name of Johnson’s bi-linear index formula. It can be proven using vajda’s identity.
$endgroup$
– Adam Higgins
Jan 4 at 14:20
add a comment |
1
$begingroup$
How about using mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
$endgroup$
– lab bhattacharjee
Jan 4 at 12:52
1
$begingroup$
This is a special case of the more general fact that if $a,b,c,d$ are any integers such that $a+b=c+d$ then $F_aF_b -F_cF_d = (-1)^{r}(F_{a+r}F_{b+r}-F_{c+r}F_{d+r})$ for any integer $r$. I know this by the name of Johnson’s bi-linear index formula. It can be proven using vajda’s identity.
$endgroup$
– Adam Higgins
Jan 4 at 14:20
1
1
$begingroup$
How about using mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
$endgroup$
– lab bhattacharjee
Jan 4 at 12:52
$begingroup$
How about using mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
$endgroup$
– lab bhattacharjee
Jan 4 at 12:52
1
1
$begingroup$
This is a special case of the more general fact that if $a,b,c,d$ are any integers such that $a+b=c+d$ then $F_aF_b -F_cF_d = (-1)^{r}(F_{a+r}F_{b+r}-F_{c+r}F_{d+r})$ for any integer $r$. I know this by the name of Johnson’s bi-linear index formula. It can be proven using vajda’s identity.
$endgroup$
– Adam Higgins
Jan 4 at 14:20
$begingroup$
This is a special case of the more general fact that if $a,b,c,d$ are any integers such that $a+b=c+d$ then $F_aF_b -F_cF_d = (-1)^{r}(F_{a+r}F_{b+r}-F_{c+r}F_{d+r})$ for any integer $r$. I know this by the name of Johnson’s bi-linear index formula. It can be proven using vajda’s identity.
$endgroup$
– Adam Higgins
Jan 4 at 14:20
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
I will give an outline of a proof, but leave the details to you. This is almost certainly not the method that you are expected to take, but it avoids the messy algebra of Binet's Formula.
One first proves (however they wish, perhaps by induction) that
$$
F_{p+q} = F_{p-1}F_{q} + F_{p}F_{q+1}
$$
for all integers $p,q$. Importantly, $p,q$ can be negative in the above formula. We also have that
$$
F_{-n} = (-1)^{n+1}F_{n}
$$
for all $n$. Then one gets $textit{D'Ocagne's Identity}$:
$$
F_{p-q} = (-1)^{q}left(F_{p+1}F_{q-1} - F_{p-1}F_{q+1}right)
$$
as a simple corollary. Then from these one can prove that
$$
F_{r}F_{a+b} = F_{a}F_{b+r} - (-1)^{r}F_{a-r}F_{b}
$$
for all integers $a,b,r$. We can rewrite this as
$$
F_{r}F_{a+b+r} = F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b}
$$
and hence if $a,b,c,d$ are integers such that $a+b=c+d$ then
$$
F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} = F_{r}F_{a+b+r} = F_{r}F_{c+d+r} = F_{c+r}F_{d+r} - (-1)^{r}F_{c}F_{d}
$$
and so for all such $a,b,c,d$ and any $r$ we have
$$
F_{a}F_{b} - F_{c}F_{d} = (-1)^{r}left(F_{a+r}F_{b+r} - F_{c+r}F_{d+r}right)
$$
From this we conclude that the LHS of your equation is simply $F_{2k+1}$, but then using the very first formula we wrote down we see that
$$
F_{2k+1} = F_{(k+1) + k} = F_{k}^{2} + F_{k+1}^{2}
$$
Just to add a few comments. In your question you stated some restrictions on the values that $m,k$ can take. It is clear from my proof that in fact the formula remains true for any integers $m,k$. I suspect that the exercise is stated as it is to avoid considering Fibonacci numbers with negative coefficients, but really this is a natural consideration. Since most of these formulae that hold for the positive index Fibonacci numbers hold for the negative index Fibonacci numbers too.
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
$endgroup$
2
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
add a comment |
$begingroup$
Using Binet's formula, we have:
$F_n = frac{phi^n - psi^n}{sqrt{5}}$ where $phi = frac{1+sqrt{5}}{2}, psi = phi-1 = frac{-1}{phi}$
Then subbing it into your equation:
$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k})$
$ = (−1)^{m−k}(frac{phi^{m+k+1} - psi^{m+k+1}}{sqrt{5}} frac{phi^{m-k-1} - psi^{m-k-1}}{sqrt{5}} - frac{phi^{m+k} - psi^{m+k}}{sqrt{5}} frac{phi^{m-k} - psi^{m-k}}{sqrt{5}})$
$ = (−1)^{m−k}(frac{phi^{2m} + psi^{2m} - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{phi^{2m} + psi^{2m} - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(frac{ - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{ - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(frac{ - phipsi^{-2k-1} - psiphi^{-2k-1}}{5} + frac{ psi^{-2k} + phi^{-2k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(phi-psi)(frac{psi^{-2k-1} - phi^{-2k-1}}{5})$
$ = (−1)^{m−k}(-1)^{m+k}(frac{phi-psi}{sqrt{5}})(frac{psi^{-2k-1} - phi^{-2k-1}}{sqrt{5}})$
$ = (−1)^{2m}(F_1)(F_{-2k-1})$
Now using the fact that $F_{-n} = (-1)^{n+1}F_n$,
$(F_1)(F_{-2k-1}) = (-1)^{-2k}(F_{2k+1})$
Using some tedious algebra, one can also show that $F_{2k+1} = F_{k}^2 + F_{k+1}^2$ and so,
$(F_{2k+1}) = F_{k}^2 + F_{k+1}^2$
answered Jan 4 at 23:32
DariusDarius
878
$endgroup$
add a comment |
$begingroup$
Here is a proof based upon Binets formula
begin{align*}
F_k=frac{varphi^k-psi^k}{varphi-psi}qquad kgeq 0tag{1}
end{align*}
where $varphi=frac{1}{2}left(1+sqrt{5}right), psi=frac{1}{2}left(1-sqrt{5}right)=-1/varphi$.
We start with the right-hand side of OPs formula and obtain
begin{align*}
F_k^2=left(frac{varphi^k-psi^k}{varphi-psi}right)^2&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2left(varphipsiright)^k+psi^{2k}right)\
&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)tag{2}\
end{align*}
Putting $kto k+1$ in (2) we get
begin{align*}
color{blue}{F_k^2+F_{k+1}^2}&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)\
&qquad+frac{1}{(varphi-psi)^2}left(varphi^{2k+2}-2(-1)^k+psi^{2k+2}right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{3}
end{align*}
And now the left-hand side.
We obtain
begin{align*}
F_{m+k}F_{m-k}&=frac{1}{left(varphi-psiright)^2}left(varphi^{m+k}-psi^{m+k}right)left(varphi^{m-k}-psi^{m-k}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-varphi^{m+k}psi^{m+k}-varphi^{m-k}psi^{m+k}+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-left(varphipsiright)^{m-k}left(varphi^{2k}+psi^{2k}right)+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)tag{4}
end{align*}
Replacing $k$ with $k+1$ in (4) we get
begin{align*}
F_{m+k+1}F_{m-k-1}&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)tag{5}
end{align*}
The left-hand side of OPs formula can now be rewritten using (4) and (5) as
begin{align*}
color{blue}{(-1)^{m-k}}&color{blue}{left(F_{m+k+1}F_{m-k-1}-F_{m+k}F_{m-k}right)}\
&=frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)\
&qquad-frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{6}
end{align*}
A comparison of (3) and (6) shows OPs identity is valid.
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
$endgroup$
add a comment |
$begingroup$
I found another approach that is also very satisfying.
We will use the fact that we can write the Fibonacci $Q$-matrix:
$$Q^{m+k} Q^{k-m}=Q^k Q^k $$
$$begin{pmatrix} F_{m+k+1} & F_{m+k} \
F_{m+k} & F_{m+k-1} end{pmatrix} begin{pmatrix} F_{k-m+1} & F_{k-m} \
F_{k-m} & F_{k-m-1} end{pmatrix} =
begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} $$
We now compute the matrix product but are only interested in the first entry:
$$begin{pmatrix} F_{m+k+1}F_{k-m+1}+F_{m+k}F_{k-m} & dots \
dots & dots end{pmatrix} =
begin{pmatrix} F^2_k+ F^2_{k+1} & dots \
dots & dots end{pmatrix} $$
This gives us the following equality:
$$ F_{m+k+1}F_{-(m-k-1)}+F_{m+k}F_{-(m-k)} = F^2_k+ F^2_{k+1} $$ Which is almost what we desire. Notice that as $m>k$, we actually know that $F_{m-k}$ and $F_{k-m-1}$ have negative indices, we will use the extension of the Fibonacci sequence to negative integers and the corresponding identity: $F_{-n}= (-1)^{n+1} F_n $, After applying this to our equality, we get:
$$ F_{m+k+1}cdot (-1)^{m-k-1+1} F_{m-k-1}+F_{m+k}cdot (-1)^{m-k+1}F_{m-k} = F^2_k+ F^2_{k+1} $$
Now we simplify this to:
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1})- (-1)^{m-k}(F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1}-F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
As desired $square$.
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3061617%2fproving-the-fibonacci-identity-%25e2%2588%25921m%25e2%2588%2592kf-mk1f-m%25e2%2588%2592k%25e2%2588%25921%25e2%2588%2592f-mkf-m%25e2%2588%2592k-f%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I will give an outline of a proof, but leave the details to you. This is almost certainly not the method that you are expected to take, but it avoids the messy algebra of Binet's Formula.
One first proves (however they wish, perhaps by induction) that
$$
F_{p+q} = F_{p-1}F_{q} + F_{p}F_{q+1}
$$
for all integers $p,q$. Importantly, $p,q$ can be negative in the above formula. We also have that
$$
F_{-n} = (-1)^{n+1}F_{n}
$$
for all $n$. Then one gets $textit{D'Ocagne's Identity}$:
$$
F_{p-q} = (-1)^{q}left(F_{p+1}F_{q-1} - F_{p-1}F_{q+1}right)
$$
as a simple corollary. Then from these one can prove that
$$
F_{r}F_{a+b} = F_{a}F_{b+r} - (-1)^{r}F_{a-r}F_{b}
$$
for all integers $a,b,r$. We can rewrite this as
$$
F_{r}F_{a+b+r} = F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b}
$$
and hence if $a,b,c,d$ are integers such that $a+b=c+d$ then
$$
F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} = F_{r}F_{a+b+r} = F_{r}F_{c+d+r} = F_{c+r}F_{d+r} - (-1)^{r}F_{c}F_{d}
$$
and so for all such $a,b,c,d$ and any $r$ we have
$$
F_{a}F_{b} - F_{c}F_{d} = (-1)^{r}left(F_{a+r}F_{b+r} - F_{c+r}F_{d+r}right)
$$
From this we conclude that the LHS of your equation is simply $F_{2k+1}$, but then using the very first formula we wrote down we see that
$$
F_{2k+1} = F_{(k+1) + k} = F_{k}^{2} + F_{k+1}^{2}
$$
Just to add a few comments. In your question you stated some restrictions on the values that $m,k$ can take. It is clear from my proof that in fact the formula remains true for any integers $m,k$. I suspect that the exercise is stated as it is to avoid considering Fibonacci numbers with negative coefficients, but really this is a natural consideration. Since most of these formulae that hold for the positive index Fibonacci numbers hold for the negative index Fibonacci numbers too.
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
$endgroup$
2
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
add a comment |
$begingroup$
I will give an outline of a proof, but leave the details to you. This is almost certainly not the method that you are expected to take, but it avoids the messy algebra of Binet's Formula.
One first proves (however they wish, perhaps by induction) that
$$
F_{p+q} = F_{p-1}F_{q} + F_{p}F_{q+1}
$$
for all integers $p,q$. Importantly, $p,q$ can be negative in the above formula. We also have that
$$
F_{-n} = (-1)^{n+1}F_{n}
$$
for all $n$. Then one gets $textit{D'Ocagne's Identity}$:
$$
F_{p-q} = (-1)^{q}left(F_{p+1}F_{q-1} - F_{p-1}F_{q+1}right)
$$
as a simple corollary. Then from these one can prove that
$$
F_{r}F_{a+b} = F_{a}F_{b+r} - (-1)^{r}F_{a-r}F_{b}
$$
for all integers $a,b,r$. We can rewrite this as
$$
F_{r}F_{a+b+r} = F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b}
$$
and hence if $a,b,c,d$ are integers such that $a+b=c+d$ then
$$
F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} = F_{r}F_{a+b+r} = F_{r}F_{c+d+r} = F_{c+r}F_{d+r} - (-1)^{r}F_{c}F_{d}
$$
and so for all such $a,b,c,d$ and any $r$ we have
$$
F_{a}F_{b} - F_{c}F_{d} = (-1)^{r}left(F_{a+r}F_{b+r} - F_{c+r}F_{d+r}right)
$$
From this we conclude that the LHS of your equation is simply $F_{2k+1}$, but then using the very first formula we wrote down we see that
$$
F_{2k+1} = F_{(k+1) + k} = F_{k}^{2} + F_{k+1}^{2}
$$
Just to add a few comments. In your question you stated some restrictions on the values that $m,k$ can take. It is clear from my proof that in fact the formula remains true for any integers $m,k$. I suspect that the exercise is stated as it is to avoid considering Fibonacci numbers with negative coefficients, but really this is a natural consideration. Since most of these formulae that hold for the positive index Fibonacci numbers hold for the negative index Fibonacci numbers too.
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
$endgroup$
2
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
add a comment |
$begingroup$
I will give an outline of a proof, but leave the details to you. This is almost certainly not the method that you are expected to take, but it avoids the messy algebra of Binet's Formula.
One first proves (however they wish, perhaps by induction) that
$$
F_{p+q} = F_{p-1}F_{q} + F_{p}F_{q+1}
$$
for all integers $p,q$. Importantly, $p,q$ can be negative in the above formula. We also have that
$$
F_{-n} = (-1)^{n+1}F_{n}
$$
for all $n$. Then one gets $textit{D'Ocagne's Identity}$:
$$
F_{p-q} = (-1)^{q}left(F_{p+1}F_{q-1} - F_{p-1}F_{q+1}right)
$$
as a simple corollary. Then from these one can prove that
$$
F_{r}F_{a+b} = F_{a}F_{b+r} - (-1)^{r}F_{a-r}F_{b}
$$
for all integers $a,b,r$. We can rewrite this as
$$
F_{r}F_{a+b+r} = F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b}
$$
and hence if $a,b,c,d$ are integers such that $a+b=c+d$ then
$$
F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} = F_{r}F_{a+b+r} = F_{r}F_{c+d+r} = F_{c+r}F_{d+r} - (-1)^{r}F_{c}F_{d}
$$
and so for all such $a,b,c,d$ and any $r$ we have
$$
F_{a}F_{b} - F_{c}F_{d} = (-1)^{r}left(F_{a+r}F_{b+r} - F_{c+r}F_{d+r}right)
$$
From this we conclude that the LHS of your equation is simply $F_{2k+1}$, but then using the very first formula we wrote down we see that
$$
F_{2k+1} = F_{(k+1) + k} = F_{k}^{2} + F_{k+1}^{2}
$$
Just to add a few comments. In your question you stated some restrictions on the values that $m,k$ can take. It is clear from my proof that in fact the formula remains true for any integers $m,k$. I suspect that the exercise is stated as it is to avoid considering Fibonacci numbers with negative coefficients, but really this is a natural consideration. Since most of these formulae that hold for the positive index Fibonacci numbers hold for the negative index Fibonacci numbers too.
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
$endgroup$
I will give an outline of a proof, but leave the details to you. This is almost certainly not the method that you are expected to take, but it avoids the messy algebra of Binet's Formula.
One first proves (however they wish, perhaps by induction) that
$$
F_{p+q} = F_{p-1}F_{q} + F_{p}F_{q+1}
$$
for all integers $p,q$. Importantly, $p,q$ can be negative in the above formula. We also have that
$$
F_{-n} = (-1)^{n+1}F_{n}
$$
for all $n$. Then one gets $textit{D'Ocagne's Identity}$:
$$
F_{p-q} = (-1)^{q}left(F_{p+1}F_{q-1} - F_{p-1}F_{q+1}right)
$$
as a simple corollary. Then from these one can prove that
$$
F_{r}F_{a+b} = F_{a}F_{b+r} - (-1)^{r}F_{a-r}F_{b}
$$
for all integers $a,b,r$. We can rewrite this as
$$
F_{r}F_{a+b+r} = F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b}
$$
and hence if $a,b,c,d$ are integers such that $a+b=c+d$ then
$$
F_{a+r}F_{b+r} - (-1)^{r}F_{a}F_{b} = F_{r}F_{a+b+r} = F_{r}F_{c+d+r} = F_{c+r}F_{d+r} - (-1)^{r}F_{c}F_{d}
$$
and so for all such $a,b,c,d$ and any $r$ we have
$$
F_{a}F_{b} - F_{c}F_{d} = (-1)^{r}left(F_{a+r}F_{b+r} - F_{c+r}F_{d+r}right)
$$
From this we conclude that the LHS of your equation is simply $F_{2k+1}$, but then using the very first formula we wrote down we see that
$$
F_{2k+1} = F_{(k+1) + k} = F_{k}^{2} + F_{k+1}^{2}
$$
Just to add a few comments. In your question you stated some restrictions on the values that $m,k$ can take. It is clear from my proof that in fact the formula remains true for any integers $m,k$. I suspect that the exercise is stated as it is to avoid considering Fibonacci numbers with negative coefficients, but really this is a natural consideration. Since most of these formulae that hold for the positive index Fibonacci numbers hold for the negative index Fibonacci numbers too.
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
edited Jan 4 at 14:56
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
answered Jan 4 at 14:48
Adam HigginsAdam Higgins
51512
51512
2
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
add a comment |
2
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
2
2
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
$begingroup$
A couple of summers ago I did some work proving lots of Fibonacci identities, a summary of which can be found at this link: dropbox.com/s/wrgogc5dtjdtdh6/…. I prove all of the above formulae, proving the first one in an interesting way.
$endgroup$
– Adam Higgins
Jan 4 at 14:49
add a comment |
$begingroup$
Using Binet's formula, we have:
$F_n = frac{phi^n - psi^n}{sqrt{5}}$ where $phi = frac{1+sqrt{5}}{2}, psi = phi-1 = frac{-1}{phi}$
Then subbing it into your equation:
$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k})$
$ = (−1)^{m−k}(frac{phi^{m+k+1} - psi^{m+k+1}}{sqrt{5}} frac{phi^{m-k-1} - psi^{m-k-1}}{sqrt{5}} - frac{phi^{m+k} - psi^{m+k}}{sqrt{5}} frac{phi^{m-k} - psi^{m-k}}{sqrt{5}})$
$ = (−1)^{m−k}(frac{phi^{2m} + psi^{2m} - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{phi^{2m} + psi^{2m} - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(frac{ - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{ - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(frac{ - phipsi^{-2k-1} - psiphi^{-2k-1}}{5} + frac{ psi^{-2k} + phi^{-2k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(phi-psi)(frac{psi^{-2k-1} - phi^{-2k-1}}{5})$
$ = (−1)^{m−k}(-1)^{m+k}(frac{phi-psi}{sqrt{5}})(frac{psi^{-2k-1} - phi^{-2k-1}}{sqrt{5}})$
$ = (−1)^{2m}(F_1)(F_{-2k-1})$
Now using the fact that $F_{-n} = (-1)^{n+1}F_n$,
$(F_1)(F_{-2k-1}) = (-1)^{-2k}(F_{2k+1})$
Using some tedious algebra, one can also show that $F_{2k+1} = F_{k}^2 + F_{k+1}^2$ and so,
$(F_{2k+1}) = F_{k}^2 + F_{k+1}^2$
answered Jan 4 at 23:32
DariusDarius
878
$endgroup$
add a comment |
$begingroup$
Using Binet's formula, we have:
$F_n = frac{phi^n - psi^n}{sqrt{5}}$ where $phi = frac{1+sqrt{5}}{2}, psi = phi-1 = frac{-1}{phi}$
Then subbing it into your equation:
$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k})$
$ = (−1)^{m−k}(frac{phi^{m+k+1} - psi^{m+k+1}}{sqrt{5}} frac{phi^{m-k-1} - psi^{m-k-1}}{sqrt{5}} - frac{phi^{m+k} - psi^{m+k}}{sqrt{5}} frac{phi^{m-k} - psi^{m-k}}{sqrt{5}})$
$ = (−1)^{m−k}(frac{phi^{2m} + psi^{2m} - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{phi^{2m} + psi^{2m} - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(frac{ - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{ - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(frac{ - phipsi^{-2k-1} - psiphi^{-2k-1}}{5} + frac{ psi^{-2k} + phi^{-2k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(phi-psi)(frac{psi^{-2k-1} - phi^{-2k-1}}{5})$
$ = (−1)^{m−k}(-1)^{m+k}(frac{phi-psi}{sqrt{5}})(frac{psi^{-2k-1} - phi^{-2k-1}}{sqrt{5}})$
$ = (−1)^{2m}(F_1)(F_{-2k-1})$
Now using the fact that $F_{-n} = (-1)^{n+1}F_n$,
$(F_1)(F_{-2k-1}) = (-1)^{-2k}(F_{2k+1})$
Using some tedious algebra, one can also show that $F_{2k+1} = F_{k}^2 + F_{k+1}^2$ and so,
$(F_{2k+1}) = F_{k}^2 + F_{k+1}^2$
answered Jan 4 at 23:32
DariusDarius
878
$endgroup$
add a comment |
$begingroup$
Using Binet's formula, we have:
$F_n = frac{phi^n - psi^n}{sqrt{5}}$ where $phi = frac{1+sqrt{5}}{2}, psi = phi-1 = frac{-1}{phi}$
Then subbing it into your equation:
$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k})$
$ = (−1)^{m−k}(frac{phi^{m+k+1} - psi^{m+k+1}}{sqrt{5}} frac{phi^{m-k-1} - psi^{m-k-1}}{sqrt{5}} - frac{phi^{m+k} - psi^{m+k}}{sqrt{5}} frac{phi^{m-k} - psi^{m-k}}{sqrt{5}})$
$ = (−1)^{m−k}(frac{phi^{2m} + psi^{2m} - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{phi^{2m} + psi^{2m} - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(frac{ - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{ - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(frac{ - phipsi^{-2k-1} - psiphi^{-2k-1}}{5} + frac{ psi^{-2k} + phi^{-2k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(phi-psi)(frac{psi^{-2k-1} - phi^{-2k-1}}{5})$
$ = (−1)^{m−k}(-1)^{m+k}(frac{phi-psi}{sqrt{5}})(frac{psi^{-2k-1} - phi^{-2k-1}}{sqrt{5}})$
$ = (−1)^{2m}(F_1)(F_{-2k-1})$
Now using the fact that $F_{-n} = (-1)^{n+1}F_n$,
$(F_1)(F_{-2k-1}) = (-1)^{-2k}(F_{2k+1})$
Using some tedious algebra, one can also show that $F_{2k+1} = F_{k}^2 + F_{k+1}^2$ and so,
$(F_{2k+1}) = F_{k}^2 + F_{k+1}^2$
answered Jan 4 at 23:32
DariusDarius
878
$endgroup$
Using Binet's formula, we have:
$F_n = frac{phi^n - psi^n}{sqrt{5}}$ where $phi = frac{1+sqrt{5}}{2}, psi = phi-1 = frac{-1}{phi}$
Then subbing it into your equation:
$(−1)^{m−k}(F_{m+k+1}F_{m−k−1}−F_{m+k}F_{m−k})$
$ = (−1)^{m−k}(frac{phi^{m+k+1} - psi^{m+k+1}}{sqrt{5}} frac{phi^{m-k-1} - psi^{m-k-1}}{sqrt{5}} - frac{phi^{m+k} - psi^{m+k}}{sqrt{5}} frac{phi^{m-k} - psi^{m-k}}{sqrt{5}})$
$ = (−1)^{m−k}(frac{phi^{2m} + psi^{2m} - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{phi^{2m} + psi^{2m} - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(frac{ - phi^{m+k+1}psi^{m-k-1} - psi^{m+k+1}phi^{m-k-1}}{5} - frac{ - phi^{m+k}psi^{m-k} - psi^{m+k}phi^{m-k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(frac{ - phipsi^{-2k-1} - psiphi^{-2k-1}}{5} + frac{ psi^{-2k} + phi^{-2k}}{5})$
$ = (−1)^{m−k}(phipsi)^{m+k}(phi-psi)(frac{psi^{-2k-1} - phi^{-2k-1}}{5})$
$ = (−1)^{m−k}(-1)^{m+k}(frac{phi-psi}{sqrt{5}})(frac{psi^{-2k-1} - phi^{-2k-1}}{sqrt{5}})$
$ = (−1)^{2m}(F_1)(F_{-2k-1})$
Now using the fact that $F_{-n} = (-1)^{n+1}F_n$,
$(F_1)(F_{-2k-1}) = (-1)^{-2k}(F_{2k+1})$
Using some tedious algebra, one can also show that $F_{2k+1} = F_{k}^2 + F_{k+1}^2$ and so,
$(F_{2k+1}) = F_{k}^2 + F_{k+1}^2$
answered Jan 4 at 23:32
DariusDarius
878
edited Jan 4 at 23:57
answered Jan 4 at 23:32
DariusDarius
878
answered Jan 4 at 23:32
DariusDarius
878
answered Jan 4 at 23:32
DariusDarius
878
878
add a comment |
add a comment |
$begingroup$
Here is a proof based upon Binets formula
begin{align*}
F_k=frac{varphi^k-psi^k}{varphi-psi}qquad kgeq 0tag{1}
end{align*}
where $varphi=frac{1}{2}left(1+sqrt{5}right), psi=frac{1}{2}left(1-sqrt{5}right)=-1/varphi$.
We start with the right-hand side of OPs formula and obtain
begin{align*}
F_k^2=left(frac{varphi^k-psi^k}{varphi-psi}right)^2&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2left(varphipsiright)^k+psi^{2k}right)\
&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)tag{2}\
end{align*}
Putting $kto k+1$ in (2) we get
begin{align*}
color{blue}{F_k^2+F_{k+1}^2}&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)\
&qquad+frac{1}{(varphi-psi)^2}left(varphi^{2k+2}-2(-1)^k+psi^{2k+2}right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{3}
end{align*}
And now the left-hand side.
We obtain
begin{align*}
F_{m+k}F_{m-k}&=frac{1}{left(varphi-psiright)^2}left(varphi^{m+k}-psi^{m+k}right)left(varphi^{m-k}-psi^{m-k}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-varphi^{m+k}psi^{m+k}-varphi^{m-k}psi^{m+k}+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-left(varphipsiright)^{m-k}left(varphi^{2k}+psi^{2k}right)+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)tag{4}
end{align*}
Replacing $k$ with $k+1$ in (4) we get
begin{align*}
F_{m+k+1}F_{m-k-1}&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)tag{5}
end{align*}
The left-hand side of OPs formula can now be rewritten using (4) and (5) as
begin{align*}
color{blue}{(-1)^{m-k}}&color{blue}{left(F_{m+k+1}F_{m-k-1}-F_{m+k}F_{m-k}right)}\
&=frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)\
&qquad-frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{6}
end{align*}
A comparison of (3) and (6) shows OPs identity is valid.
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
$endgroup$
add a comment |
$begingroup$
Here is a proof based upon Binets formula
begin{align*}
F_k=frac{varphi^k-psi^k}{varphi-psi}qquad kgeq 0tag{1}
end{align*}
where $varphi=frac{1}{2}left(1+sqrt{5}right), psi=frac{1}{2}left(1-sqrt{5}right)=-1/varphi$.
We start with the right-hand side of OPs formula and obtain
begin{align*}
F_k^2=left(frac{varphi^k-psi^k}{varphi-psi}right)^2&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2left(varphipsiright)^k+psi^{2k}right)\
&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)tag{2}\
end{align*}
Putting $kto k+1$ in (2) we get
begin{align*}
color{blue}{F_k^2+F_{k+1}^2}&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)\
&qquad+frac{1}{(varphi-psi)^2}left(varphi^{2k+2}-2(-1)^k+psi^{2k+2}right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{3}
end{align*}
And now the left-hand side.
We obtain
begin{align*}
F_{m+k}F_{m-k}&=frac{1}{left(varphi-psiright)^2}left(varphi^{m+k}-psi^{m+k}right)left(varphi^{m-k}-psi^{m-k}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-varphi^{m+k}psi^{m+k}-varphi^{m-k}psi^{m+k}+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-left(varphipsiright)^{m-k}left(varphi^{2k}+psi^{2k}right)+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)tag{4}
end{align*}
Replacing $k$ with $k+1$ in (4) we get
begin{align*}
F_{m+k+1}F_{m-k-1}&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)tag{5}
end{align*}
The left-hand side of OPs formula can now be rewritten using (4) and (5) as
begin{align*}
color{blue}{(-1)^{m-k}}&color{blue}{left(F_{m+k+1}F_{m-k-1}-F_{m+k}F_{m-k}right)}\
&=frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)\
&qquad-frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{6}
end{align*}
A comparison of (3) and (6) shows OPs identity is valid.
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
$endgroup$
add a comment |
$begingroup$
Here is a proof based upon Binets formula
begin{align*}
F_k=frac{varphi^k-psi^k}{varphi-psi}qquad kgeq 0tag{1}
end{align*}
where $varphi=frac{1}{2}left(1+sqrt{5}right), psi=frac{1}{2}left(1-sqrt{5}right)=-1/varphi$.
We start with the right-hand side of OPs formula and obtain
begin{align*}
F_k^2=left(frac{varphi^k-psi^k}{varphi-psi}right)^2&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2left(varphipsiright)^k+psi^{2k}right)\
&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)tag{2}\
end{align*}
Putting $kto k+1$ in (2) we get
begin{align*}
color{blue}{F_k^2+F_{k+1}^2}&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)\
&qquad+frac{1}{(varphi-psi)^2}left(varphi^{2k+2}-2(-1)^k+psi^{2k+2}right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{3}
end{align*}
And now the left-hand side.
We obtain
begin{align*}
F_{m+k}F_{m-k}&=frac{1}{left(varphi-psiright)^2}left(varphi^{m+k}-psi^{m+k}right)left(varphi^{m-k}-psi^{m-k}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-varphi^{m+k}psi^{m+k}-varphi^{m-k}psi^{m+k}+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-left(varphipsiright)^{m-k}left(varphi^{2k}+psi^{2k}right)+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)tag{4}
end{align*}
Replacing $k$ with $k+1$ in (4) we get
begin{align*}
F_{m+k+1}F_{m-k-1}&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)tag{5}
end{align*}
The left-hand side of OPs formula can now be rewritten using (4) and (5) as
begin{align*}
color{blue}{(-1)^{m-k}}&color{blue}{left(F_{m+k+1}F_{m-k-1}-F_{m+k}F_{m-k}right)}\
&=frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)\
&qquad-frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{6}
end{align*}
A comparison of (3) and (6) shows OPs identity is valid.
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
$endgroup$
Here is a proof based upon Binets formula
begin{align*}
F_k=frac{varphi^k-psi^k}{varphi-psi}qquad kgeq 0tag{1}
end{align*}
where $varphi=frac{1}{2}left(1+sqrt{5}right), psi=frac{1}{2}left(1-sqrt{5}right)=-1/varphi$.
We start with the right-hand side of OPs formula and obtain
begin{align*}
F_k^2=left(frac{varphi^k-psi^k}{varphi-psi}right)^2&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2left(varphipsiright)^k+psi^{2k}right)\
&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)tag{2}\
end{align*}
Putting $kto k+1$ in (2) we get
begin{align*}
color{blue}{F_k^2+F_{k+1}^2}&=frac{1}{(varphi-psi)^2}left(varphi^{2k}-2(-1)^k+psi^{2k}right)\
&qquad+frac{1}{(varphi-psi)^2}left(varphi^{2k+2}-2(-1)^k+psi^{2k+2}right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{3}
end{align*}
And now the left-hand side.
We obtain
begin{align*}
F_{m+k}F_{m-k}&=frac{1}{left(varphi-psiright)^2}left(varphi^{m+k}-psi^{m+k}right)left(varphi^{m-k}-psi^{m-k}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-varphi^{m+k}psi^{m+k}-varphi^{m-k}psi^{m+k}+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}-left(varphipsiright)^{m-k}left(varphi^{2k}+psi^{2k}right)+psi^{2m}right)\
&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)tag{4}
end{align*}
Replacing $k$ with $k+1$ in (4) we get
begin{align*}
F_{m+k+1}F_{m-k-1}&=frac{1}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)tag{5}
end{align*}
The left-hand side of OPs formula can now be rewritten using (4) and (5) as
begin{align*}
color{blue}{(-1)^{m-k}}&color{blue}{left(F_{m+k+1}F_{m-k-1}-F_{m+k}F_{m-k}right)}\
&=frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}+(-1)^{m-k}left(varphi^{2k+2}+psi^{2k+2}right)right)\
&qquad-frac{(-1)^{m-k}}{left(varphi-psiright)^2}left(varphi^{2m}+psi^{2m}-(-1)^{m-k}left(varphi^{2k}+psi^{2k}right)right)\
&,,color{blue}{=frac{1}{(varphi-psi)^2}left(varphi^{2k}left(1+varphi^2right)+psi^{2k}left(1+psi^2right)right)}tag{6}
end{align*}
A comparison of (3) and (6) shows OPs identity is valid.
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
edited Jan 6 at 6:55
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
answered Jan 5 at 20:31
Markus ScheuerMarkus Scheuer
60.7k455145
60.7k455145
add a comment |
add a comment |
$begingroup$
I found another approach that is also very satisfying.
We will use the fact that we can write the Fibonacci $Q$-matrix:
$$Q^{m+k} Q^{k-m}=Q^k Q^k $$
$$begin{pmatrix} F_{m+k+1} & F_{m+k} \
F_{m+k} & F_{m+k-1} end{pmatrix} begin{pmatrix} F_{k-m+1} & F_{k-m} \
F_{k-m} & F_{k-m-1} end{pmatrix} =
begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} $$
We now compute the matrix product but are only interested in the first entry:
$$begin{pmatrix} F_{m+k+1}F_{k-m+1}+F_{m+k}F_{k-m} & dots \
dots & dots end{pmatrix} =
begin{pmatrix} F^2_k+ F^2_{k+1} & dots \
dots & dots end{pmatrix} $$
This gives us the following equality:
$$ F_{m+k+1}F_{-(m-k-1)}+F_{m+k}F_{-(m-k)} = F^2_k+ F^2_{k+1} $$ Which is almost what we desire. Notice that as $m>k$, we actually know that $F_{m-k}$ and $F_{k-m-1}$ have negative indices, we will use the extension of the Fibonacci sequence to negative integers and the corresponding identity: $F_{-n}= (-1)^{n+1} F_n $, After applying this to our equality, we get:
$$ F_{m+k+1}cdot (-1)^{m-k-1+1} F_{m-k-1}+F_{m+k}cdot (-1)^{m-k+1}F_{m-k} = F^2_k+ F^2_{k+1} $$
Now we simplify this to:
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1})- (-1)^{m-k}(F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1}-F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
As desired $square$.
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
$endgroup$
add a comment |
$begingroup$
I found another approach that is also very satisfying.
We will use the fact that we can write the Fibonacci $Q$-matrix:
$$Q^{m+k} Q^{k-m}=Q^k Q^k $$
$$begin{pmatrix} F_{m+k+1} & F_{m+k} \
F_{m+k} & F_{m+k-1} end{pmatrix} begin{pmatrix} F_{k-m+1} & F_{k-m} \
F_{k-m} & F_{k-m-1} end{pmatrix} =
begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} $$
We now compute the matrix product but are only interested in the first entry:
$$begin{pmatrix} F_{m+k+1}F_{k-m+1}+F_{m+k}F_{k-m} & dots \
dots & dots end{pmatrix} =
begin{pmatrix} F^2_k+ F^2_{k+1} & dots \
dots & dots end{pmatrix} $$
This gives us the following equality:
$$ F_{m+k+1}F_{-(m-k-1)}+F_{m+k}F_{-(m-k)} = F^2_k+ F^2_{k+1} $$ Which is almost what we desire. Notice that as $m>k$, we actually know that $F_{m-k}$ and $F_{k-m-1}$ have negative indices, we will use the extension of the Fibonacci sequence to negative integers and the corresponding identity: $F_{-n}= (-1)^{n+1} F_n $, After applying this to our equality, we get:
$$ F_{m+k+1}cdot (-1)^{m-k-1+1} F_{m-k-1}+F_{m+k}cdot (-1)^{m-k+1}F_{m-k} = F^2_k+ F^2_{k+1} $$
Now we simplify this to:
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1})- (-1)^{m-k}(F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1}-F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
As desired $square$.
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
$endgroup$
add a comment |
$begingroup$
I found another approach that is also very satisfying.
We will use the fact that we can write the Fibonacci $Q$-matrix:
$$Q^{m+k} Q^{k-m}=Q^k Q^k $$
$$begin{pmatrix} F_{m+k+1} & F_{m+k} \
F_{m+k} & F_{m+k-1} end{pmatrix} begin{pmatrix} F_{k-m+1} & F_{k-m} \
F_{k-m} & F_{k-m-1} end{pmatrix} =
begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} $$
We now compute the matrix product but are only interested in the first entry:
$$begin{pmatrix} F_{m+k+1}F_{k-m+1}+F_{m+k}F_{k-m} & dots \
dots & dots end{pmatrix} =
begin{pmatrix} F^2_k+ F^2_{k+1} & dots \
dots & dots end{pmatrix} $$
This gives us the following equality:
$$ F_{m+k+1}F_{-(m-k-1)}+F_{m+k}F_{-(m-k)} = F^2_k+ F^2_{k+1} $$ Which is almost what we desire. Notice that as $m>k$, we actually know that $F_{m-k}$ and $F_{k-m-1}$ have negative indices, we will use the extension of the Fibonacci sequence to negative integers and the corresponding identity: $F_{-n}= (-1)^{n+1} F_n $, After applying this to our equality, we get:
$$ F_{m+k+1}cdot (-1)^{m-k-1+1} F_{m-k-1}+F_{m+k}cdot (-1)^{m-k+1}F_{m-k} = F^2_k+ F^2_{k+1} $$
Now we simplify this to:
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1})- (-1)^{m-k}(F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1}-F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
As desired $square$.
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
$endgroup$
I found another approach that is also very satisfying.
We will use the fact that we can write the Fibonacci $Q$-matrix:
$$Q^{m+k} Q^{k-m}=Q^k Q^k $$
$$begin{pmatrix} F_{m+k+1} & F_{m+k} \
F_{m+k} & F_{m+k-1} end{pmatrix} begin{pmatrix} F_{k-m+1} & F_{k-m} \
F_{k-m} & F_{k-m-1} end{pmatrix} =
begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} begin{pmatrix} F_{k+1} & F_{k} \
F_{k} & F_{k-1} end{pmatrix} $$
We now compute the matrix product but are only interested in the first entry:
$$begin{pmatrix} F_{m+k+1}F_{k-m+1}+F_{m+k}F_{k-m} & dots \
dots & dots end{pmatrix} =
begin{pmatrix} F^2_k+ F^2_{k+1} & dots \
dots & dots end{pmatrix} $$
This gives us the following equality:
$$ F_{m+k+1}F_{-(m-k-1)}+F_{m+k}F_{-(m-k)} = F^2_k+ F^2_{k+1} $$ Which is almost what we desire. Notice that as $m>k$, we actually know that $F_{m-k}$ and $F_{k-m-1}$ have negative indices, we will use the extension of the Fibonacci sequence to negative integers and the corresponding identity: $F_{-n}= (-1)^{n+1} F_n $, After applying this to our equality, we get:
$$ F_{m+k+1}cdot (-1)^{m-k-1+1} F_{m-k-1}+F_{m+k}cdot (-1)^{m-k+1}F_{m-k} = F^2_k+ F^2_{k+1} $$
Now we simplify this to:
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1})- (-1)^{m-k}(F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
$$ (-1)^{m-k} (F_{m+k+1} F_{m-k-1}-F_{m+k} F_{m-k}) = F^2_k+ F^2_{k+1} $$
As desired $square$.
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
answered Jan 16 at 16:21
Wesley StrikWesley Strik
1,660423
1,660423
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3061617%2fproving-the-fibonacci-identity-%25e2%2588%25921m%25e2%2588%2592kf-mk1f-m%25e2%2588%2592k%25e2%2588%25921%25e2%2588%2592f-mkf-m%25e2%2588%2592k-f%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
How about using mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
$endgroup$
– lab bhattacharjee
Jan 4 at 12:52
1
$begingroup$
This is a special case of the more general fact that if $a,b,c,d$ are any integers such that $a+b=c+d$ then $F_aF_b -F_cF_d = (-1)^{r}(F_{a+r}F_{b+r}-F_{c+r}F_{d+r})$ for any integer $r$. I know this by the name of Johnson’s bi-linear index formula. It can be proven using vajda’s identity.
$endgroup$
– Adam Higgins
Jan 4 at 14:20