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.
On
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}) .$$
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.