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.

Your base case is:

$$\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:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.