Prove $\sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}$ by induction

Question

I was assigned two induction problems that I tried to solve. One was easy to solve using the following method, but one got me stuck. Problem:

Prove by induction on $n \geq 1$ that for every $a \neq 1$, $\sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}$

Work: We note that since this is of the form $\sum_{k=1}^{n} f(k) = g(n)$, we can solve this by induction by showing that $f(1) = g(1)$ and $g(n + 1) - g(n) = f(n + 1)$.

So $f(1) = \sum_{i=0}^{1} a^i = a^0 + a^1 = a^1 + 1$, and $g(1) = \frac{a^{1+1} - 1}{a - 1} = \frac{a^2 -1}{a - 1} = \frac{(a + 1)(a - 1)}{a - 1} = a + 1$. Thus, $f(1) = g(1)$.

Evaluating the second condition, we see that the left side ($f(n)$) becomes $a^{n+1}$, and the right side ($g(n)$) becomes $\frac{a^{n+1+1} - 1}{a + 1 - 1} - \frac{a^{n+1} - 1}{a - 1}$.

$\begin{aligned} a^{n+1} &=^? \frac{a^{n+1+1} - 1}{a + 1 - 1} - \frac{a^{n+1} - 1}{a - 1}\\ &=^? \frac{a^{n+2} - 1}{a} - \frac{a^{n+1} - 1}{a - 1}\\ &=^? \frac{a^na^2 - 1}{a} - \frac{a^na^1 - 1}{a - 1}\\ &=^? \frac{a^na^2 - 1}{a}(\frac{a - 1}{a - 1}) - \frac{a^na^1 - 1}{a - 1}(\frac{a}{a})\\ &=^? \frac{(a^na^2 - 1)(a - 1)}{a(a - 1)} - \frac{a^na^2 - a}{a(a - 1)}\\ &=^? \frac{a^na^2(a - 1) - 1(a - 1) - a^na^2 + a}{a(a - 1)}\\ &=^? \frac{a^na^3 - a^na^2 - a + 1 - a^na^2 + a}{a(a - 1)}\\ &=^?\frac{a^na^3 -2a^na^2 + 1}{a^2 - a}\\ \end{aligned}$

I checked over my algebra several times, and I can't find a mistake. I haven't been able to figure out how to manipulate $\frac{a^na^3 -2a^na^2 + 1}{a^2 - a}$ into a simpler form. Can someone point out an error, if one exists, or show me the next step in simplification?

score 3 · Answer 1 · 2013-01-26T21:39:38.707

3

Why is there a $a+1$ in the denominator of your first step? We are inducting on $n$ and not $a$.

$$\dfrac{a^{n+1+1} - 1}{\color{red}{\underbrace{a + 1}_{\text{Incorrect}}} - 1} - \dfrac{a^{n+1} - 1}{a - 1}$$

Once you correct it, the rest should follow as a breeze.

$$\dfrac{a^{n+1+1} - 1}{a - 1} - \dfrac{a^{n+1} - 1}{a - 1} = \dfrac{a^{n+2} - a^{n+1}}{a-1} = a^{n+1} \dfrac{a-1}{a-1} = a^{n+1}, \,\,\,\,\,\, \forall a \neq 1$$

edited Jan 26 '13 at 21:39

answered Jan 26 '13 at 21:24

Thanks! I don't know how I missed it. – SSumner Jan 26 '13 at 21:42

score 3 · Accepted Answer · answered Jan 26 '13 at 21:26

3

Your mistake comes at the very beginning: $g(n+1)-g(n)$ is not

$$\frac{a^{n+1+1} - 1}{a + 1 - 1} - \frac{a^{n+1} - 1}{a - 1}\;,$$

but rather $$\frac{a^{(n+1)+1}}{a-1}-\frac{a^{n+1}-1}{a-1}\;.$$

You’re doing the induction on $n$, not on $a$.

answered Jan 26 '13 at 21:26

Brian M. Scott

616,228

I looked at that like 5 times, too. Thanks for the catch – SSumner Jan 26 '13 at 21:42
@SSumner: You’re welcome. Sometimes it’s like trying to find a typo in one’s own writing: the eye just slides over it. – Brian M. Scott Jan 26 '13 at 21:45

score 1 · Answer 3 · answered Jan 26 '13 at 21:33

1

$$\sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}$$

$$\sum_{i=0}^{n+1} a^i =\sum_{i=0}^{n} a^i +a^{n+1}= \frac{a^{n+1} - 1}{a - 1}+a^{n+1}=\frac{a^{n+1} - 1+aa^{n+1}-a^{n+1}}{a - 1}=$$ $$=\frac{ - 1+aa^{n+1}}{a - 1}=\frac{ a^{(n+1)+1}-1}{a - 1}$$

answered Jan 26 '13 at 21:33

Adi Dani

16,949

Prove $\sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}$ by induction

3 Answers3