How to prove this statement through induction?

Question

I need to show that for the terms of the fibonnaci sequence, where $n \ge 1$, $a_{n-1}^2 + a_{n}^2 = a_{2n-1}$

So far, I have this:

$a_{n-1}^2 + a_{n}^2$

$=a_{n-1}^2 +(a_{n-1} + a_{n-2}$

$=a_{n-1}^2 +a_{n-1}^2 + a_{n-2}^2 + 2a_{n-1}a_{n-2}$

$=a_{n-1}^2 + a_{2n-3} + 2a_{n-1}a_{n-2}$

$=a_{n-1} (a_{n-1} + 2a_{n-2}) + a_{2n-3}$

$=a_{n-1} (a_{n} + a_{n-2}) + a_{2n-3}$

I'm kind of stuck at this point. How can I simplify the first part so it becomes $a_{2n-2}$? I was thinking that would be necessary so I could have $a_{2n-3} + a_{2n-2} = a_{2n-1}$

Answer 1

$a_{n-1}^2+a_{n}^2=a_{2n-1}$

base case: $n = 2$

$a_1^2 + a_2^2 = a_3\\ 1^2 + 1^2 = 2$

Suppose for all $n\le k, a_{n-1}^2+a_{n}^2=a_{2n-1}$

We must show that

$a_{k}^2+a_{k+1}^2=a_{2k+1}$

$a_{2k+1} =$$ a_{2k} + a_{2k-1}\\ = 2a_{2k-1} + a_{2k-2}\\ = 3a_{2k-1} - a_{2k-3}$

$a_{2k+1} = 3(a_k^2 + a_{k-1}^2) - (a_{k-1}^2 + a_{k-2}^2)$

by the inductive hypothesis

$3a_k^2 + 2 a_{k-1}^2 - a_{k-2}^2\\ 3a_k^2 + a_{k-1}^2 + (a_{k-1}+a_{k-2})(a_{k-1}-a_{k-2})\\ 3a_k^2 + a_{k-1}^2 + (a_{k})(a_{k-1}-a_{k-2})\\ a_k(3a_k + a_{k-1}-a_{k-2}) + a_{k-1}^2\\ a_k(2a_k + 2a_{k-1}) + a_{k-1}^2\\ 2a_k^2 + 2a_ka_{k-1} + a_{k-1}^2\\ a_k^2 + (a_{k}+a_{k-1})^2\\ a_k^2 + a_{k+1}^2$

Answer 2

I'm not sure if you completely understand what a proof by induction entails. Lets start from the beginning. Every proof by induction starts with a base case. In this case, lets suppose $a_{0} = 0$ and $a_{1} = 1$. Then we have $a_{0}^2 + a_{1}^2 = 0^2+1^2 = 1 = a_{2(1)-1}$. Hence our base case is true.

Now we do the induction step. In induction, we assume our $n^{th}$ case is true, and using that, we try and show the $(n+1)^{th}$ case is also true. If we can do that, then all cases that follow the base case must be true. Here, this means we assume $a_{n-1}^2 + a_{n}^2 = a_{2n-1}$, and we want to show $a_{n}^2 + a_{n+1}^2 = a_{2(n+1)-1}$

So lets try and show that $a_{n}^2 + a_{n+1}^2 = a_{2(n+1)-1}$ is true.

Subtracting the induction assumption, we get $a_{n+1}^2 - a_{n-1}^2 = a_{2n+1}-a_{2n-1} = a_{2n}$. Note that we can do this because we are assuming that our induction hypothesis is true. See if you can take it from here and argue that these two sides are equal.