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.

  • $\begingroup$ See math.stackexchange.com/a/1834546/61216 for a proof (with obvious shifts for the indices) using the matrix form of the Fibonacci numbers. $\endgroup$ – gammatester Oct 24 '16 at 10:31
  • $\begingroup$ @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. $\endgroup$ – 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_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}=$$


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

  • $\begingroup$ The equality is symmetric in n and k so you're actually done. $\endgroup$ – Sophie Oct 24 '16 at 9:39
  • $\begingroup$ @MussuliniYes, I know...yet the details are not there but in justifying all the minor steps done in the above. $\endgroup$ – DonAntonio Oct 24 '16 at 9:47
  • $\begingroup$ I'm sorry I don't quite understand it. Where did you use your Induction Hyp. ? $\endgroup$ – Marco Neves Oct 24 '16 at 9:48
  • 1
    $\begingroup$ @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. $\endgroup$ – DonAntonio Oct 24 '16 at 9:54
  • 1
    $\begingroup$ @DonAntonio Thanks a bunch man I'll keep practicing so I can be like you :) $\endgroup$ – 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}) .$$


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.