# Help with math induction $S_{n+1}=1+aS_n$

Using mathematical induction I would like to prove the following.

$S_0=1$

$S_1=1+a,...,S_n=\sum_{i=0}^n a^i$

Prove that $S_{n+1}=1+aS_n$ where $n \ge 0$.

-
What have you tried? What are you having difficulty with? This is straightforward. –  Calvin Lin Feb 5 '13 at 6:35

## 2 Answers

Check that it holds for $n=1$. Fix an $n\geq 1$ and assume that $S_n=\sum_{i=0}^n a^i$. $$aS_n=a\sum_{i=0}^n a^i=\sum_{i=0}^n a^{i+1}=\sum_{i=1}^{n+1}a^i.$$ Now add $1$ and conclude that $S_{n+1}$ has the right form.

-
Wow that was pretty simple. I get it now. When I first saw it I thought it would be much more difficult to solve it. Thanks. –  Blue Pony Inc. Feb 5 '13 at 15:47

Hint $\$ Below is an overview of the induction step.

$$\begin{eqnarray} \rm S_n =\, \sum_{i\, =\, 0}^n\,a^i\ \ \Rightarrow\ \ S_{n+1} &=&\rm\ \ S_n\ +\ a^n \\ \\ \rm Hence\ \quad S_{n+2} - a\, S_{n+1} &=&\rm\ (S_{n+1} +\color{#C00}{a^{n+2}}) - \color{#C00}a\,(S_{n}+\color{#C00}{a^{n+1}})\\ \\ &=&\rm\ \ S_{n+1} - a\, S_n\ =\ 1\ \ \ \text{by induction}\\ \end{eqnarray}$$

-