The Fibonacci sequence is defined as follows:
$a_0=0,a_1=1,a_2=1$
$a_n=a_{n-1}+a_{n-2},n\geq 2$
And the problem asks:
Show, using induction:
$a_1^2+a_2^2+...+a_n^2=a_na_{n+1}$.
Here's my attempt:
Proof:
Let $P(n)$ be the statement $a_1^2+a_2^2+...+a_n^2=a_na_{n+1}$ for all $n\in \mathbb{N} ,n\geq 2$.
Base case:
Let $n=2$, then $1^2+1^2=1*2\implies 2=2$. Therefore, $P(2)$ is true.
Inductive assumption:
Let $n\in \mathbb{N} ,n\geq 2$ be generic, and assume that $P(n)$ is true, i.e. $a_1^2+a_2^2+...+a_n^2=a_na_{n+1}$.
Induction step:
$(a_1^2+a_2^2+...+a_n^2)+a_{n+1}^2=a_na_{n+1}+a_{n+1}^2=a_{n+1}(a_n+a_{n+1})=a_{n+1}a_{n+2}=a_{n+1}a_{(n+1)+1}$. Therefore, $P(n+1)$ is true. $\blacksquare$
I'm not sure why $n\in \mathbb{N}$ isn't in the question, but I assumed that. How is my proof? Did I miss anything?
Thanks.
You have proven that:
$$\forall n\in \mathbb{N} ,n\geq 2 : P(n)$$
But assuming we define $P(n)$ as:
$$\sum_{i=0}^n a_i^2 = a_n a_{n+1}$$
You'll find that $P(n)$ also holds for $n=0$ and $n=1$, i.e. you can prove:
$$\forall n\in \mathbb{N}: P(n)$$
... and it certainly looks like that's what you are supposed to prove.
So, that means that you will need $n=0$ as your base case, and not $n=2$
P.s. The Wikipedia page on Fibonacci numbers has a nice 'proof' by picture of the theorem you're proving: