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.


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.


Please help how to set this 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.

  • $\begingroup$ 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? $\endgroup$
    – JORGE
    Mar 18 '15 at 23:58
  • $\begingroup$ 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)$. $\endgroup$
    – Falko
    Mar 19 '15 at 0:11
  • $\begingroup$ 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? $\endgroup$
    – JORGE
    Mar 19 '15 at 2:26
  • $\begingroup$ 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. $\endgroup$
    – JORGE
    Mar 19 '15 at 14:04
  • $\begingroup$ 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. $\endgroup$
    – Falko
    Mar 19 '15 at 14:17

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.