# Help with how to prepare the inductive step of a strong induction exercise.

I have the following exercise:

"Use strong induction to prove that $f_1^2 + f_2^2 + \cdots + f_n^2 = (f_n)(f_{n+1})$ where $f_n$ in the nth Fibonacci number."

This is what I have done:

Fibonacci sequence - $f_n = f_{n-1} + f_{n-2}, f_1=1, f_2=1$

$f_3=f_2+f_1=2; f_4=f_3+f_2=3; f_5=f_4+f_3=5$ and so on.

*** BASIS STEP:

for $n=1: f_1^2 = f_1f_2; 1=1$

for $n=2: f_1^2 + f_2^2 = f_2f_3; 2=2$

for $n=3: f_1^2 + f_2^2 + f_3^2 = f_3f_4; 6=6$

Therefore $P(n)$ is true for n=1,2,3.

*** INDUCTIVE STEP:

Now you need to show that $$f_1^2 + \cdots + f_{n+1}^2 = f_{n+1}f_{n+2}$$ is true if $$f_1^2 + \cdots + f_m^2 = f_m f_{m+1}$$ is true for all $m \leq n$.
We proceed by using the equality for $m=n$ and then applying the property $f_{n+2} = f_n + f_{n+1}$. \begin{align*} f_1^2 + \cdots + f_n^2 + f_{n+1}^2 & = f_{n}f_{n+1} + f_{n+1}^2 \\ & = f_{n+1}(f_n+f_{n+1}) \\ & = f_{n+1}f_{n+2} \end{align*}
And we're done. You should have noticed that we only required the truth of the equation for $m=n$, so a normal induction would have sufficed.
• In normal induction we assume $P(n)$ and then prove $P(n+1)$. But in strong induction one assumes $P(m)$ for all $m \leq n$ and then proves $P(n+1)$, so we could use the truth of $P(n-1)$ or $P(n-3)$ in our inductive step if we wanted. But in this case we only need $P(n)$. – Falko Mar 19 '15 at 0:11
• Instead of doing "normal/weak" induction you can always do strong induction if you like, it doesn't change a thing. So you can use $P(n-1), P(n-2)$ etc. in the proof of the inductive step. I just wanted to say that in this case strong induction doesn't make the proof any easier. – Falko Mar 19 '15 at 14:17