Proving this expression via mathematical induction

39 Views Asked by At

I have an expression:

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

And the stating "assume that r is a real number other than 1, prove the above for every nonnegative integer n as true". So I performed the "basis step" (I used $r = 2$ and $n = 1$):

$$\sum_{i=0}^1 2^i = 2^0 + 2^1 = 1 + 2 = 3$$

$$\frac{1-2^{1+1}}{1-2} = \frac{1-4}{1-2} = \frac{-3}{-1} = 3$$

So now I move onto the "induction step", namely proving $P(n+1)$. Such that:

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

Is my current process correct?

1

There are 1 best solutions below

3
On

Yes, your induction step is correct. Nevertheless, we have to exclude not only $r = 1$ but $r = 0 $ as well since $r = 0$ yields in the first term of sum the expression $0^0$ which is undefined (and, as you pointed out in the comment to my unedited answer, the case $r = 0, n = 1$ also does not work).

We want to prove by induction that the following formula holds for any $n \geq 0$ and $r \in \mathbb{R} \setminus \{ 0 \} $ $$ \sum_{i = 0}^n r^i = \frac{1 - r^{n+1}}{1-r} \ .$$

First step of induction: proof for $n = 0$. This holds trivially since $$ \sum_{i = 0}^0 r^i = r^0 = 1 = \frac{1 - r}{1-r} \ .$$

Second step (the inductin step): assume that the formula holds for all $k < n$ and proof that then it must hold for $k = n$ as well. We have

$$ \sum_{i = 0}^n r^i = \sum_{i = 0}^{n-1} (r^i) + r^{n} \ . $$

Since the first summand on the righ side of the above equality satisfies the formula by assumption, we can expand it accordingly and thus get

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

which was intended to be shown.