Proof by induction (exponents)

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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$

Answer 4

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