Prove that $a_{n+1} = 2a_n$ for all integers n≥1. Prove that $a_n = 2^{n−1}$ for n≥1.

Question

Define a sequence $a_0, a_1, \dots$ in the following way. Put $a_0 = 1$. For each n≥1 define $$ a_n = a_0 +a_1 + \dots + a_{n−1}. $$

(a) Prove that $a_{n+1} = 2a_n$ for all integers n≥1.

(b) Prove that $a_n = 2^{n−1}$ for n≥1.

Answer 1

Part $a:$ $$a_n = (a_0 +a_1 + \dots + a_{n−1}) \\\text{now add $a_n$ to both sides} \\ a_n+a_n = a_n + (a_0 +a_1 + \dots + a_{n−1})\\ 2a_n = a_0 +a_1 + \dots + a_{n−1}+ a_n \\ \to 2a_n = a_{n+1}$$

Part b:

$$\dfrac{a_{n}}{a_{n-1}}=2,\dfrac{a_{n-1}}{a_{n-2}}=2,...,\dfrac{a_{1}}{a_0}=2 \\ \text{now multiply all of them:}\\ \dfrac{a_{n}}{a_{n-1}} \cdot\dfrac{a_{n}}{a_{n-1}} ... \dfrac{a_{1}}{a_{0}} =2^{n-1} \\ \dfrac{a_n}{a_0}=2^{n-1}\\ \text {and } a_0=1 \\ \to a_n=2^{n-1}$$

Answer 2

Start with $a_n = a_1 + a_2... + a_{n-2} + a_{n-1}$ and $a_n = a_1 + a_2... + a_{n-2}$ use substitution to get $a_n = a_{n-1} + a_{n-1}$ and $a_n = 2 a_{n-1}$

this means that $a_2 = 2 a_1$. By using the recurrence relation to find that $a_3 = 4 a_1$, $a_4 = 8 a_1$, $a_5 = 16 a_1$ etc. the obvious pattern emerging is that $a_n = 2^{n-1} a_1$, and because $a_1 = 1$, $a_n = 2^{n-1}$