# Prove equality for Fibonacci sequence [duplicate]

I have to show that

$F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$, where $F_{n}$ is nth Fibonacci element.

I was trying with mathematical induction applied to n and saying k is constant.

1. step for $n=1$ $F_{k+1} = F_{k}F_{2} + F_{k-1}F_{1}$ which is true, because $F_1=F_2=1$

2. step let say our theorem is true for some n

3. step I was trying to do it like this: $F_{n+1+k} = F_{n+k}+F_{n+k-1} = F_{k}F_{n+1} + F_{k-1}F_{n} + F_{n+k-1}$

but there is $F_{n+k-1}$and I do not know what to do with it.

Thanks!

• $n+k-1 = (n-1)+k$. And modify your property so that you can use it for $n$ and for $n-1$ in the induction step. – Daniel Fischer Apr 27 '16 at 20:03
• Another method is using the Binet formular – MrYouMath Apr 27 '16 at 20:16
• I was looking for similiar problem, but coudn't find it. Now I see it in the Related column. Should I delete my question? – janusz Apr 27 '16 at 21:14

We wish to prove that the Fibonacci numbers $F_n$ satisfy $F_{n+k}=F_kF_{n+1}+F_{k-1}F_n$. We use induction on $n$. The result is true for $n=1$ because $F_1=F_2=1$ and $F_{k+1}=F_k+F_{k-1}$. Suppose it is true for $m<n$.
Then we have $F_{n+k}=F_{n+k-1}+F_{n+k-2}=(F_kF_n+F_{k-1}F_{n-1})+(F_kF_{n-1}+F_{k-1}F_{n-2})$ $=F_k(F_n+F_{n-1})+F_{k-1}(F_{n-1}+F_{n-2})$ $=F_kF_{n+1}+F_{k-1}F_n$. So the result is true for $n$. Hence it is true for all $n$.
Here's a slightly different approach, for kicks: Claim: $$A_n = \begin{bmatrix}F_n & F_{n-1}\\F_{n-1} & F_{n-2}\end{bmatrix} = \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{n-1}$$ Which is easily proven with induction.
Then $$A_{n+1}A_{k}=\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{n}\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{k-1}=A_{n+k}$$
Now the first element of $A_{n+1}A_{k}$ is $F_{n+1}F_{k}+F_{n}F_{k-1}$. The first element of $A_{n+k}$ is $F_{n+k}$. We're done.