# Prove by induction:$\sum_{i=0}^n 3^i = \frac {(3^{n+1})-1}{2}$

Prove by induction: $$\sum_{i=0}^n 3^i = \frac {(3^{n+1})-1}{2}$$

Basis: For $n=0$ we have $1 = 1$

Inductive Step: Now this is where I don't know what to do, any kind of help would be much appreciated. Thanks!

• Have you tried anything yourself? If you have any idea as to how the proof might go then indicating this would be useful. – Joe Tait Apr 1 '14 at 8:44

Inductive Step: Assume that the expression holds for $n$. We want to prove that the expression holds also for $n+1$. That is \begin{align*}\sum_{i=0}^{n+1} 3^i &=\sum_{i=0}^n 3^i +3^{n+1}=^{\text{assumption of inductive step}}\\&= \frac {(3^{n+1})-1}{2}+3^{n+1}=\frac{3^{n+1}-1+2\cdot3^{n+1}}{2}=\frac{3\cdot3^{n+1}-1}{2}=\frac{3^{n+2}-1}{2}\\&=\frac{3^{(n+1)+1}-1}{2}\end{align*} which proves that the expression holds also for $n+1$.

You have the base step.

Induction hypothesis: Assume that $$\sum_{i=0}^k3^i=\frac{3^{k+1}-1}{2}$$

for some $k\ge0$

Inductive step: Then \begin{align}\sum_{i=0}^{k+1}&=3^{k+1}+\sum_{i=0}^k3^i\\&=3^{k+1}+\frac{3^{k+1}-1}{2}\\&=\frac{3^{k+2}-1}{2}\end{align}

Thus our formula is proved.

Hint:$$\sum_{i=0}^{n+1}3^{i}=\sum_{i=0}^{n}3^{i}+3^{n+1}=\frac{3^{n+1}-1}{3-1}+3^{n+1}=\dots$$