2
$\begingroup$

The Fibonacci numbers are defined such that $f_n = f_{n-1}+f_{n-2}$. Prove that for all $n \ge 1$, $f_1^2 + f_2^2 + f_3^2 + \cdots + f_n^2 = f_n \cdot f_{n+1}$.

$P(n) = f_1^2 + f_2^2 + f_3^2 + \cdots + f_n^2 = f_n \cdot f_{n+1}$

Base case: $1^2 = 1 \cdot 1$

Inductive step - need to prove $P(n + 1)$:

  1. $f_1^2 + f_2^2 + f_3^2 + \cdots + f_n^2 + f_{n+1}^2 = f_{n+1} \cdot f_{n+2}$
  2. $f_n \cdot f_{n + 1} + f_{n+1}^2 = f_{n+1} \cdot f_{n+2}$ (by the inductive hypothesis)
  3. $f_{n+1}(f_n + f_{n+1}) = f_{n+1}(f_n + f_{n +1 })$

I'm wondering if I took the correct steps in this proof by induction to reach the conclusion. If there are any quicker methods to reach the conclusion, then any feedback is appreciated.

$\endgroup$
  • 1
    $\begingroup$ You've discovered a very nice solution! But remember, after the brainstorming is done, when you're writing the proof you should always start with known facts, and derive things from there until you derive the statement you are trying to prove. So a proper proof of the inductive step would start with 3., then 2., and then (using the inductive hypothesis) 1. $\endgroup$ – Greg Martin Oct 6 '16 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.