5
$\begingroup$

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.

2 Answers 2

5

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

  • 0
    Hi Nameless, thank you for your help.2013-01-09
4

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

  • 0
    Hi Jesper, thank you for your help.2013-01-09