1
$\begingroup$

The Fibonacci numbers can be defined recursively by letting
\begin{align} F_{0}=0, \ F_{1}=1\end{align} Then for every natural number $n\geq 2$, \begin{align} F_{n}= F_{n-2}+F_{n-1}\end{align}

Prove that for all $n,k\in\mathbb{N}$, \begin{align} F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}. \end{align} So far this is my proof.

First for $k=1$, \begin{align}F_{n+1}=F_{1}F_{n+1}+F_{0}F_{n-1}\end{align}\begin{align} =1{\cdot}F_{n+1}+0{\cdot}F_{n-1}\end{align} \begin{align} =F_{n+1} \end{align} Now let $k\in\mathbb{N}$ with $k\geq2$ and assume that \begin{align}F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\end{align}

I'm unsure about whether \begin{align} F_{n+(k+1)}=F_{k+1}F_{n+1}+F_{k}F_{n} \end{align} is true or not because if so, then \begin{align} F_{n+(k+1)}=F_{(n+1)+k}=F_{k}F_{n+2}+F_{k-1}F_{n+1} \end{align} could be true as well. Any advice about how to finish this induction would be very helpful.

$\endgroup$
  • $\begingroup$ Well then since they're both true, then would I be done after showing that $F_{n+k+1}=F_{k+1}F_{n+1}+F_{k}F_{n}$? $\endgroup$ – JB071098 Jan 16 '18 at 1:51
2
$\begingroup$

Suppose by induction that $$ F_{n+k}=F_kF_{n+1}+F_{k-1}F_n\quad (1) $$ holds for all for numbers $N\leq k$, and let us proof for $k+1$. Hence, as $(1)$ holds for all $N\leq k$, we have $$ F_{n+k-1}=F_{k-1}F_{n+1}+F_{k-2}F_n\quad (2) $$ Summing $(1)$ and $(2)$ we obtain \begin{eqnarray} F_{n+k}+F_{n+k-1}&=&F_kF_{n+1}+F_{k-1}F_n+F_{k-1}F_{n+1}+F_{k-2}F_n\\ &=&(F_k+F_{k-1})F_{n+1}+(F_{k-1}+F_{k-2})F_n. \end{eqnarray} By the definition of Fibonacci sequence we have $F_k=F_{k-2}+F_{k-1}$, $F_{k+1}=F_{k-1}+F_{k}$ and $F_{n+k+1}=F_{n+k}+F_{n+k-1}$. Hence, $$ F_{n+k+1}=F_{k+1}F_{n+1}+F_kF_n. $$ Which is $(1)$ for $k+1$.

$\endgroup$
  • $\begingroup$ Thank you. Using strong induction makes it much easier. $\endgroup$ – JB071098 Jan 16 '18 at 3:24
2
$\begingroup$

Let $M$ be the $2\times2$ matrix with top-row entries $1,1$ and botton-row entries $1,0$ (from left to right): $$ M = \pmatrix { 1 & 1 \\ 1 & 0 } $$

Prove by induction on $n\in \Bbb N$ that the top row of $M^n$ is $F_{n+1}, F_n$ and the bottom row is $F_n,F_{n-1}$: $$ {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}} $$ Compare the entries of $M^{n+k}$ with those of $(M^n\cdot M^k).$

$\endgroup$
  • $\begingroup$ I would greatly appreciate it if someone would tell me how to format matrices in LaTex. $\endgroup$ – DanielWainfleet Jan 16 '18 at 11:04
  • $\begingroup$ @lhf. Thank you for your edit. $\endgroup$ – DanielWainfleet Jan 16 '18 at 11:36
  • $\begingroup$ See also en.wikipedia.org/wiki/Fibonacci_number#Matrix_form. $\endgroup$ – lhf Jan 16 '18 at 11:38
  • $\begingroup$ You can also just copy the formulas from Wikipedia, as I did in the second one. $\endgroup$ – lhf Jan 16 '18 at 11:40

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.