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.

How can we show by mathematical induction that the following holds for $ n \ge 0$ and $a \ne 1$?

$$ 1 + a + a^2 + a^3 + \ldots + a^n = \frac{a^{n+1}-1}{a-1}$$

I understand the principle of mathematical induction, but I've no idea how to apply it here. I know in general I have to prove it for $n = 1$ and then assume $n = k$ is correct. Then prove $n = k+1$ is true. But what about $a$?

I've watched a load of YouTube videos on the subject, and I've read a few questions here but it's not helping. The videos make sense while I'm watching them, but I don't know how to apply it. This question appeared on my discrete math exam last week. I did not do well. I think I'm missing something fundamental in my understanding of this subject.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

If $n=0$, we must prove $1=\frac{a-1}{a-1}$ which is trivial.

Assume that it holds for $n=k$, that is: $$1+a+...+a^k=\frac{a^{k+1}-1}{a-1}$$ We must prove that it holds for $n=k+1$ or in other words that $$1+a+...+a^k+a^{k+1}=\frac{a^{k+2}-1}{a-1}$$ But this is simple to prove with our assumption: $$1+a+...+a^k+a^{k+1}=\frac{a^{k+1}-1}{a-1}+a^{k+1}=\frac{a^{k+1}-1+a^{k+2}-a^{k+1}}{a-1}=\frac{a^{k+2}-1}{a-1}$$

share|improve this answer
    
Note that he is supposed to start at $n=0$ (which is even easier to start with), not at $n=1$. –  Hagen von Eitzen Dec 17 '12 at 16:47
    
Thank you, I will study this and come back to you. –  bot_bot Dec 17 '12 at 16:48
    
Hi Nameless, thank you for your help. –  bot_bot Jan 9 '13 at 9:27

Let $P(n)$ be the statement that $1+a+...+a^n=\frac{a^{n+1}-1}{a-1}$. Since $1=\frac{a-1}{a-1}$, $P(0)$ is true.

Suppose $P(k)$ is true for some non-negative integer $k$. Then $1+a+...+a^k=\frac{a^{k+1}-1}{a-1}$, so that $1+a+...+a^{k+1}=\frac{a^{k+1}-1}{a-1}+a^{k+1}=\frac{a^{k+1}-1}{a-1}+\frac{a^{k+2}-a^{k+1}}{a-1}=\frac{a^{k+2}-1}{a-1}$, so that $P(k+1)$ is true.

Hence we have $P(n)$ for all non-negative integers $n$.

Note that in this example, you are asked to start at $n=0$ and not $n=1$ and thus prove the statement for all non-negative integers and not just positive integers. Also note that here $a\neq 1$ is fixed and we are doing induction on $n$ and not on $a$.

share|improve this answer
    
Hi Jasper, did you lose a $-1$ term in the final numerator? –  Amzoti Dec 17 '12 at 16:54
    
Hi Jesper, thank you for your help. –  bot_bot Jan 9 '13 at 9:27

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.