Prove using general induction:
$f_\ell = f_{m+1} \cdot f_{\ell-m} + f_m \cdot f_{\ell-(m+1)}$ for $m \le 0$, for $\ell \ge m+1$
Where, $f_\ell$ is the $\ell$-th Fibonacci number and $f_0 = 0$, $f_1=1$ ...
I have tried to read on general induction and have solved many examples. However I couldn't crack this one! Please help!
Note: $\ell$ and $m$ are suffix to $f$ - so they represent the $\ell$-th or the $m$-th fibonacci number
The proposition is clearly true for $m=0$, because $$ f_l=1\cdot f_{l-0}+0\cdot f_{l-m-1} $$ Now, if it is true for a given $m$, let's try to prove it for $m+1$ $$ f_l=f_{m+1}\cdot f_{l-m} + f_m\cdot f_{l-m-1}=f_{m+1}\cdot (f_{l-m-2} +f_{l-m-1}) + f_m\cdot f_{l-m-1}= $$ $$ f_{m+1}\cdot f_{l-m-2} + f_{m+1}\cdot f_{l-m-1} + f_m\cdot f_{l-m-1}= f_{m+1}\cdot f_{l-m-2} + (f_m + f_{m+1})\cdot f_{l-m-1}= $$
Can you take it from here?