5
$\begingroup$

Let $F_n$ be a Fibonacci sequence with initial terms $F_0=0, F_1=1$ and $F_{n+1}=F_n+F_{n-1}$ for $n\geqslant 1$.

Prove that $F_n^2+F_{n+1}^2=F_{2n+1}$ for $n\geqslant 0$ (with mathematical induction).

My efforts: For $n=0$ it is true.

Suppose that our statement holds for $0\leqslant k \leqslant n$ i.e. $F_k^2+F_{k+1}^2=F_{2k+1}$

Let's try to prove it for $k=n+1$. $$F_{2n+3}=F_{2n+1}+F_{2n+2}=F_{n+1}^2+(F_{n}^2+F_{2n+2})= ?$$

Here I'm stuck and I have applied different methods but none of them brings a positive result.

Can anyone help to complete this?

$\endgroup$
  • 1
    $\begingroup$ math.stackexchange.com/questions/295173/… $\endgroup$ – lab bhattacharjee Nov 28 '17 at 11:14
  • $\begingroup$ @labbhattacharjee, thanks but your link has matrix proof which is given below and proof suing binet's formula. As I said above i am interested in induction proof $\endgroup$ – ZFR Nov 28 '17 at 11:18
2
$\begingroup$

This follows from the matrix formulation, which is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$ Just compare $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^{2n}= \begin{pmatrix}F_{2n+1}&*\\*&*\end{pmatrix} $$ with $$ \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}^2= \begin{pmatrix}\cdots&*\\*&*\end{pmatrix} $$ Alternatively (and equivalently), you can use induction to prove simultaneously that $$ F_{2n} = F_n (F_{n+1} + F_{n-1}), \quad F_{2n+1}=F_n^2+F_{n+1}^2 $$

$\endgroup$
  • $\begingroup$ Adapted from math.stackexchange.com/a/1505284/589 $\endgroup$ – lhf Nov 28 '17 at 11:14
  • 2
    $\begingroup$ Nice proof but I would like to see the induction proof $\endgroup$ – ZFR Nov 28 '17 at 11:15
  • $\begingroup$ How to use induction in order to prove the second identity? Could you write the induction proof? $\endgroup$ – ZFR Nov 28 '17 at 11:34
  • $\begingroup$ @RFZ, proceed as in lab bhattacharjee's answer. $\endgroup$ – lhf Nov 28 '17 at 12:37
  • $\begingroup$ I have added an answer. Please take a look $\endgroup$ – ZFR Nov 28 '17 at 15:21
2
$\begingroup$

We can prove more general identity, i.e. $F_{n+m+1}=F_{m+1}F_{n+1}+F_{m}F_{n}$.

Let's prove above by mathematical induction on $n$.

For $n=0$ we have $F_{m+1}=F_{m+1}$

Suppose it is true for all $0\leqslant n \leqslant k$.

Let's prove it for $n=k+1$ then $$F_{k+m+2}=F_{k+m}+F_{k+m+1}=(F_{m+1}F_{k}+F_{m}F_{k-1})+(F_{m+1}F_{k+1}+F_{m}F_{k})=F_{m+1}(F_k+F_{k+1})+F_m(F_{k-1}+F_k)=F_{m+1}F_{k+2}+F_mF_{k+1}$$

The first two parentheses were derived from induction assumption for $n=k-1$ or $n=k$.

Thus, we have proved our initial statement. If we put $n=m$ we get $$F_{2n+1}=F_{n+1}^2+F_n^2$$

$\endgroup$
1
$\begingroup$

$$F_{2(n+1)+1}=F_{2n+1}+F_{2n+2}$$

$$=F_{n+1}^2+(F_{n}^2+F_{2n+2})$$

$=F_{n+1}^2+F_{n}^2+F_{n+1}(F_{n+2}+F_n)$ (Using Proving a Fibonacci identity: $F_{2n} = F_n (F_{n+1} + F_{n-1})$,)

$$=F_{n+1}^2+F_{n+1}F_{n+2}+F_n(\underbrace{F_n+F_{n+1}})$$

$$=F_{n+1}^2+F_{n+1}F_{n+2}+F_nF_{n+2}$$

$$=F_{n+1}^2+F_{n+2}(\underbrace{F_{n+1}+F_n})$$

$$=?$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.