# Proof by induction, inductive step problem

Prove by induction:

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

Now, i know how to do the first step and i understand it but then i have a problem with the second step which is showing that its true for n+1.

My question is:

Is this notation corect:

$$\sum_{i=0}^{n+1} 3^i =\frac {1}{2} (3^{n+2}-1)$$ Which of these is corect and why? $$\sum_{i=0}^{n+1} 3^i =\sum_{i=0}^{n} 3^i+n+1$$ or $$\sum_{i=0}^{n+1} 3^i =\sum_{i=0}^{n} 3^{n+1}$$

Neither of those is correct, but the first one is closer. What you want to say is $$\sum_{i=0}^{n+1}3^{i}=\sum_{i=0}^{n}3^{i}+3^{n+1}$$ since $$3^{n+1}$$ is the extra term missing from the sum on the right hand side. To complete the proof, the induction hypothesis implies that the right hand side is $$\frac{1}{2}(3^{n+1}-1)+3^{n+1}=\frac{3}{2}\cdot3^{n+1}-\frac{1}{2}=\frac{1}{2}\cdot 3^{n+2}-\frac{1}{2}=\frac{1}{2}(3^{n+2}-1)$$

Notation looks good.

$$\sum_{i=0}^0{3^i}=3^0=1$$ $$\frac12(3^1-1)=\frac12(2)=1$$ so true for $$n=0$$

Inductive Step:

Assume the statement true for $$n=k$$, that is:

$$\sum_{i=0}^k{3^i}=\frac12(3^{k+1}-1)$$ Then show for $$n=k+1$$. We use that:

$$\sum_{i=0}^{k+1}{3^i}=\sum_{i=0}^{k}{3^i}+3^{k+1}$$ This is the correct expansion of that sum as opposed to what you suggested. We achieve this by finding the $$(k+1)$$th term of the sum and adding it to the summation to $$k$$ terms.

So you need to show that:

$$\frac12(3^{k+1}-1)+3^{k+1}=\frac12(3^{k+2}-1)$$