Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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$.

share|improve this answer
    
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

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$$

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

$$\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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.