# Fibonacci Sequence Proof

I was given the following to prove and I have not a clue as to how to approach this problem. I have a solid understanding or Complete Induction and Mathematical Induction but I couldn't quite grasp Structural Induction. I have a test soon and I would really appreciate if anyone could explain how to solve problems of the sort.

Prove that $$f_{k}f_{n}+f_{k+1}f_{n+1}=f_{n+k+1}$$

where $f_{k}$ is the k_th Fibonacci number.

• See math.stackexchange.com/a/1834546/61216 for a proof (with obvious shifts for the indices) using the matrix form of the Fibonacci numbers. – gammatester Oct 24 '16 at 10:31
• @gammatester That's a little above what I'm at right now but thanks for the input I'll make sure to bookmark it for the future. – Marco Neves Oct 24 '16 at 10:38

By induction on $\;k+n\;$: for $\;k+n=1,\,2\;$ (whatever you choose or both of them) the claim is trivially verified. Assume for all indexes up to $\;k+n\;$ and prove for $\;k+n+1\;$ :

\begin{align*}&\text{First Case}\,: k+1\;:\;\;\;f_{k+1}f_n+f_{k+2}f_{n+1}\stackrel?=f_{n+k+2}\end{align*}

but then

$$f_{k+1}f_n+f_{k+2}f_{n+1}=(\color{red}{f_{k-1}}+\color{green}{f_k})f_n+(\color{green}{f_{k+1}}+\color{red}{f_k})f_{n+1}=$$

$$=f_{k-1}f_n+f_kf_{n+1}+f_kf_n+f_{k+1}f_{n+1}\stackrel{\text{Ind. Hyp.}}=f_{n+(k-1)+1}+f_{k+n+1}=$$

$$=f_{n+k}+f_{n+k+1}=f_{n+k+2}\;\;\;\color{green}\checkmark$$

Now you do the second case with $\;n+1\;$ and fill in whatever minor details are left.

• The equality is symmetric in n and k so you're actually done. – Sophie Oct 24 '16 at 9:39
• @MussuliniYes, I know...yet the details are not there but in justifying all the minor steps done in the above. – DonAntonio Oct 24 '16 at 9:47
• I'm sorry I don't quite understand it. Where did you use your Induction Hyp. ? – Marco Neves Oct 24 '16 at 9:48
• @MarcoNeves Honestly? I begin working on the proof and decide on my way, though in this case it is a rather special case as there are two indexes, so the choice to do induction on their sum looked natural. This is mainly practice, experience...neither deep thinking nor genius involved here. – DonAntonio Oct 24 '16 at 9:54
• @DonAntonio Thanks a bunch man I'll keep practicing so I can be like you :) – Marco Neves Oct 24 '16 at 10:02

Hint. Use induction to show that for any $n\in\mathbb{N}$ $$f_{k}f_{n}+f_{k+1}f_{n+1}=f_{n+k+1}\quad \forall k\in\mathbb{N}.$$

i) Basic step. Show $$f_{k}f_{0}+f_{k+1}f_{0+1}=f_{0+k+1}\quad \forall k\in\mathbb{N}.$$

ii) Inductive step. Notice that $\forall k\in\mathbb{N}$, $$f_{n+k+1}=f_{n+k}+f_{n-1+k}=(f_{k}f_{n-1}+f_{k+1}f_n)+(f_{k}f_{n-2}+f_{k+1}f_{n-1})\\ =f_{k}(f_{n-1}+f_{n-2})+f_{k+1}(f_n+f_{n-1}) .$$