Proof by induction.. something that I am missing can't figure it out

Question

The question is to prove by induction: $ \sum_{k=1}^n r^k = \dfrac{r-r^{n+1}}{1-r} $ $\forall n \in \mathbb{N}$ $\mid r \neq 1 $

I can show the base case. Let $n=r=2;$ $2^1 + 2^2 = \dfrac{2-2^{3}}{1-2}=6$

My try: Let $n=k$. We want to prove $\sum_{k=1}^n r^k + r^{k+1} = \dfrac{r-r^{k+2}}{1-r}$...... But already I think that I am making some mistake. However, I will continue:

$r^{k+1}(1-r)=r-r^{k+2}$

But I am stuck here. Not sure what I am missing in terms of factoring or if I am completely off track or what. Can someone tell me what I am doing wrong?

Answer 1

If this is true at all, it is true for all $r\ne 1$. You don't do induction on $r$. This could be true for any real $r$ (as long as it is not equal to $r$.)

Your base case is $\sum\limits_{k=1}^1 r^k = r = \frac {r - r^2}{1-r} = \frac {r(1-r)}{1-r} = r$. That is the base case. It must be true for all $r$ that $r \ne 1$.

Induction step:

You must prove that $\sum\limits_{k=1}^n r^k = \frac {r - r^{n+1}}{1-r} \implies \sum\limits_{k=1}^{n+1} r^k = \frac {r-r^{n+1}}{1-r}$. (What you actually wrote with index is just fubar. None of your indexes actually match up in any reasonable way.

You do this by noting:

$\sum\limits_{k=1}^{n+1} r^k = (\sum\limits_{k=1}^n r^k) + r^{n+1}$

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

....

$= \frac {r - r^{n+2}}{1-r}$.

Can you fill in the $...$?

... it is ...

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

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

$\frac {r - r^{n+1}}{1-r} + \frac {r^{n+1} - r^{n+2}}{1-r}=$

$\frac {(r - r^{n+1})+(r^{n+1} - r^{n+2})}{1-r} $

$= \frac {r - r^{n+2}}{1-r}$.

Answer 2

For base case, I don't think we need $r=2$. We need $r \ne 1$. Also, base case should be $n=1$ or $n=0$ depending on your definition of $\mathbb{N}$.

For the induction step, I think you are confusing your $k$ with $n$.

\begin{align} \sum_{k=1}^n r^k + r^{\color{red}n+1} &= \frac{r-r^{n+1}}{1-r}+r^{n+1}\\ &=\frac{r-r^{n+1}+r^{n+1}-r^{n+2}}{r-1}\\ &=\frac{r-r^{n+2}}{r-1} \end{align}

Answer 3

Assume that $\sum_{k=1}^n r^k = \dfrac{r-r^{n+1}}{1-r}$.

We need to prove that $\sum_{k=1}^{n+1} r^k = \dfrac{r-r^{n+2}}{1-r}$.

This is true because $\sum_{k=1}^{n+1} r^k=\sum_{k=1}^n r^k+r^{n+1}=\dfrac{r-r^{n+1}}{1-r}+r^{n+1}=\dfrac{r-r^{n+1}+r^{n+1}(1-r)}{1-r}=\dfrac{r-r^{n+1}+r^{n+1}-r^{n+2}}{1-r}=\dfrac{r-r^{n+2}}{1-r}.$

Answer 4

For $n=t$ you assume it is true, you then prove the hypothesis for $n=t+1$ $$\sum_{k=1}^tr^k=\frac{r-r^{t+1}}{1-r} \\ P(k+1):\sum_{k=1}^{t+1}r^k=\sum_{k=1}^tr^k+r^{t+1}=\frac{r-r^{t+1}}{1-r}+r^{t+1} \\ =\frac{r-r^{t+1}+r^{t+1}-r^{t+2}}{1-r}=\frac{r-r^{t+2}}{1-r}$$ This proves the hypothesis for $t+1$

Answer 5

You can't assume $r = 2$ in the base case.

base case $n = 1:$

$\sum_\limits{k=1}^{1} r^k = r = \frac {r- r^2}{1-r}$

Inductive hypothesis

Suppose:

$\sum_\limits{k=1}^{n} r^k = \frac {r- r^{n+1}}{1-r}$

We must show that when the inductive hypothesis holds

$\sum_\limits{k=1}^{n+1} r^k = \frac {r- r^{n+2}}{1-r}$

$\sum_\limits{k=1}^{n+1} r^k = \sum_\limits{k=1}^{n} r^k + r^{n+1} = \frac {r-r^{n+1}}{1-r} + r^{n+1}$

Based on the inductive hypothesis

$\frac {r-r^{n+1}}{1-r} + r^{n+1} = \frac {r-r^{n+1} + r^{n+1} - r^{n+2}}{1-r} = \frac {r - r^{n+2}}{1-r}$