1
$\begingroup$

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!

$\endgroup$
3
  • 2
    $\begingroup$ $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. $\endgroup$ – Daniel Fischer Apr 27 '16 at 20:03
  • $\begingroup$ Another method is using the Binet formular $\endgroup$ – MrYouMath Apr 27 '16 at 20:16
  • $\begingroup$ I was looking for similiar problem, but coudn't find it. Now I see it in the Related column. Should I delete my question? $\endgroup$ – janusz Apr 27 '16 at 21:14
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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