# 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.

• Yes, a proof by normal induction is evident, but I have to use strong induction, that is what the professor asks. In fact, I see that this induction step is pretty much like that for normal induction. What would be the difference? – JORGE Mar 18 '15 at 23:58
• 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)$. – Elzee Mar 19 '15 at 0:11
• In the Basis Step I got the result for n=1,2,3; so I guess the inductive step would be: P(j) is true for 1 <= j <= k where k >= 3 and I would have to prove for P(k+1). Shouldn´t I use the truth of P(n-2)? Is my reasoning correct? – JORGE Mar 19 '15 at 2:26
• The above comment is very important to me, I will very much appreciate if you provide a clue. Our professor uses the approach of "P(n-something)" and I would like to use it too. – JORGE Mar 19 '15 at 14:04
• 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. – Elzee Mar 19 '15 at 14:17