Fibonacci Sequence. Proof via induction

Question

Prove with induction on $n \ge 1$ that:

$$a_1\cdot a_2 + a_2\cdot a_3 +...+a_{2n} . a_{2n+1} = a_{2n+1}^2 -1$$

Where $a_1 = a_2 =1, a_3 = 2 , a_n = a_{n-1} + a_{n-2}$.

Answer 1

The base case $n = 1$ , you have to prove: $$a_1\cdot a_2 +a_2\cdot a_3 = a_3^2 -1$$. But this is clear because $LHS = 1\cdot 1+1\cdot 2 = 3 = 2^2 - 1 = RHS$. Thus assume the statement is true for $n = k$, that is:$$a_1\cdot a_2+a_2\cdot a_3+\cdots a_{2k}\cdot a_{2k+1} = a_{2k+1}^2 - 1$$, you prove its true for $n = k+1$:

We have: $a_1\cdot a_2+\cdots +a_{2k+2}\cdot a_{2k+3} = a_{2k+1}^2 - 1 + a_{2k+1}\cdot a_{2k+2} + a_{2k+2}\cdot a_{2k+3} = a_{2k+1}(a_{2k+1}+ a_{2k+2})+a_{2k+2}\cdot a_{2k+3} - 1 = a_{2k+1}\cdot a_{2k+3} + a_{2k+2}\cdot a_{2k+3} - 1 = a_{2k+3}(a_{2k+1}+a_{2k+2}) - 1 = a_{2k+3}\cdot a_{2k+3}-1 = a_{2k+3}^2 - 1 $.

Thus we've proven that its true for $n = k+1$, hence is true for all $n \ge 1$.

Answer 2

Suppose the claim is true when $n=k$ (as is certainly true for $k=1$ because then we just need to verify $a_1a_2+a_2a_3=a_3^2-1$, i.e. $1^2+1\times 2 = 2^2-1$). Increasing $n$ to $k+1$ adds $a_{2k+1}a_{2k+2}+a_{2k+2}a_{2k+3}=2a_{2k+1}a_{2k+2}+a_{2k+2}^2$ to the left-hand side while adding $a_{2k+3}^2-a_{2k+1}^2=2a_{2k+1}a_{2k+2}+a_{2k+2}^2$ to the right-hand side. Thus the claim also holds for $n=k+1$.

Answer 3

The basis step is immediate. For the inductive step, see if you can generalize from the following specific example (I prove that if the identity holds for $N = 7$, then it must hold for $N = 8$):

\begin{align*} &(a_1a_2 + a_2a_3 + \cdots + a_{14}a_{15}) + a_{15}a_{16} + a_{16}a_{17} \\ &= (a_{15}^2 - 1) + a_{15}a_{16} + a_{16}a_{17} &\text{by the induction hypothesis} \\ &= a_{15}(a_{15} + a_{16}) + a_{16}a_{17} - 1 \\ &= a_{15}a_{17} + a_{16}a_{17} - 1 &\text{using the Fibonacci recurrence} \\ &= (a_{15} + a_{16})a_{17} - 1 \\ &= a_{17}^2 - 1 &\text{using the Fibonacci recurrence} \\ \end{align*} as desired.