# Proof by induction (exponents)

Use proof by induction and show that the formula holds for all positive integers:$$1+3+3^2+\dots+3^{n-1}=\frac{3^n -1}2$$

The confusing step in my opinion is the first expression: $3^{n-1}$, when I have to show for $k+1$. Any solutions?

-
Is this really algebra-precalculus? –  Shahar Aug 27 '14 at 20:27
See the second answer here: math.stackexchange.com/questions/22599/… –  user133281 Aug 27 '14 at 20:27
@Shahar Well, it's not calculus! But yes, I guess it'd appear in algebra $2$ in high school. –  Sanath Devalapurkar Aug 27 '14 at 20:27
@SanathDevalapurkar Not really calculus but I didn't learn this in algebra either. What should I tag this? –  Shahar Aug 27 '14 at 20:28
alright, so I guess I get 3^(k-1)+1) which is 3^k? @user133281 –  gger234 Aug 27 '14 at 20:29

1. Show $3^{1-1}=\dfrac{3^1-1}{2}$

2. Assume $\sum\limits_{k=0}^{n-1}3^k=\dfrac{3^n-1}{2}$

3. Prove $\sum\limits_{k=0}^{n}3^k=\dfrac{3^{n+1}-1}{2}$:

• $\sum\limits_{k=0}^{n}3^k=(\sum\limits_{k=0}^{n-1}3^k)+3^n$

• $(\sum\limits_{k=0}^{n-1}3^k)+3^n=\dfrac{3^n-1}{2}+3^n$

• $\dfrac{3^n-1}{2}+3^n=\dfrac{3^n-1+2\cdot3^n}{2}$

• $\dfrac{3^n-1+2\cdot3^n}{2}=\dfrac{3^n+2\cdot3^n-1}{2}$

• $\dfrac{3^n+2\cdot3^n-1}{2}=\dfrac{3\cdot3^n-1}{2}$

• $\dfrac{3\cdot3^n-1}{2}=\dfrac{3^{n+1}-1}{2}$

Note that the induction-step is applied only at the second bullet.

-
wow nice, could you please explain the second last line? thanks –  gger234 Aug 27 '14 at 20:36
@gger234: I added a line explaining that; hope it helps... –  barak manos Aug 27 '14 at 20:40
@gger234: Note that the induction step takes place only at the second bullet of section 2. –  barak manos Aug 27 '14 at 20:42
@gger234: $X+2\cdot{X}=3X$ –  barak manos Aug 27 '14 at 20:43
(Don't you also want to include the case $n=1$?) –  user84413 Aug 27 '14 at 20:44

Suppose that $x \neq 1$. We wish to show by inducting on $n$ that $\sum\limits_{k=0}^{n-1}x^{k} = \frac{x^{n} - 1}{x-1}$.

Then $1 = \frac{x-1}{x-1}$ so that the formula holds for $n = 1$. Suppose that we have $\sum\limits_{k=0}^{n-1}x^{k} = \frac{x^{n} - 1}{x-1}$. We must show that $\sum\limits_{k=0}^{n}x^{k} = \frac{x^{n+1} - 1}{x-1}$.

We have $\sum\limits_{k=0}^{n}x^{k} = \sum\limits_{k=0}^{n- 1}x^{k} + x^{n} = \frac{x^{n} - 1}{x-1} + x^{n}\frac{x -1}{x-1} = \frac{x^{n} - 1 + x^{n+1} - x^{n}}{x - 1} = \frac{x^{n+1} - 1}{x-1}$

-

For n+1 it is

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

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{3\cdot 3^{n}-1}{2}$

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{(1+2)\cdot 3^{n}-1}{2}$

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{1\cdot 3^{n}-1}{2}+\frac{2\cdot 3^{n}}{2}$

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\left( \frac{1\cdot 3^{n}-1}{2}\right) + 3^n$

-

For the base case simply show that the premise is true for the smallest positive integer: $\mathsf P(1)$.

For the iterative case, you have to show that if the premise holds for $n$, then it is implied to hold for $n+1$.   $\mathsf P(n)\implies\mathsf P(n+1)$

Do that by substituting $n+1$ for $n$ and demonstrate that the left and right hand side both contain terms of the original premise and the same modifier.

Here we show that modifier is the addition of $3^n$.

\begin{align} \text{Prove }\forall n\in \mathbb Z^+: \sum_{k=0}^{n-1} 3^k & = \frac {3^n-1}{2} & \text{premise } \\[3ex] 3^0 & = \frac{3^1-1}{2} & \text{base case} \\[3ex] 3^n + \sum_{k=0}^{n-1} 3^k & = \sum_{k=0}^{n} 3^k \\[1ex] 3^n+\frac {3^n-1}{2} & = \frac{3\cdot 3^n-1}{2} \\[2ex] \therefore \sum_{k=0}^{n-1} 3^k & = \frac {3^n-1}{2} \implies \sum_{k=0}^{n} 3^k = \frac{3^{n+1}-1}{2} &\text{iterative step } \\[2ex]\therefore \forall n\in\mathbb Z^+: \sum_{k=0}^{n-1} 3^k & = \frac {3^n-1}{2} & \text{by induction} \end{align}

-