Let $a_1=a_2=1$, $a_3=2$ and $a_n=a_{n-1}+a_{n-2}$ for $n\ge3$. Prove that $a_1 + a_2 + \ldots + a_n = a_{n+2} - 1$.

Question

I think that this needs the use of a strong form of induction.

So, I tried it with $k$

$3\le k\le n$, where $n$ is arbitrarily chosen.

But I can't proceed beyond this.

Answer 1

Here is a slightly different take.

Let $b_n = 1 + a_1 + a_2 + \cdots + a_n$.

Then

$b_{n-1} = 1 + a_1 + a_2 + a_3 + \cdots + a_{n-1}$

$b_{n-2} = \hspace{9mm} 1 + a_1 + a_2 + \cdots + a_{n-2}$

gives

$b_{n-1}+b_{n-2} = 1 + (a_1 + 1) +(a_2+a_1) + (a_3+a_2) + \cdots + (a_{n-1}+ a_{n-2})$

$\hspace{22mm}= 1 + (a_1 + a_2) + a_3 + a_4 + \cdots + a_{n} = b_{n}$

Since $b_1 = 2 = a_3$ and $b_2=3=a_4$, we have $b_n=a_{n+2}$ for all $n$.

Answer 2

You have :

$$a_n=a_{n-1}+a_{n-2}\Leftrightarrow a_n-a_{n-1}=a_{n-2} \Rightarrow \sum_{k=3}^{n+2}(a_k-a_{k-1})= \sum_{k=3}^{n+2}a_{k-2} \\ \Leftrightarrow a_{n+2}-1=\sum_{k=1}^{n}a_k \text{ using telescopic sums}$$