# How to prove $1 + 3 + 3^2 + … + 3^{n-1} = (3^n - 1)/2$ by mathematical induction?

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

I am stuck at

$\dfrac{3^k - 1}2 + 3^k$

and I'm not sure if I am right or not.

• use that $3-1=2$, and that $3^n-1^n=(3-1)(3^{n-1}+\cdots+1)$ – Mirko Dec 13 '15 at 0:12
• $\frac{3^k-1}{2}+3^k=\frac{3^{k+1}-1}{2}$. – user236182 Dec 13 '15 at 0:13
• with added detail, $\frac{3^k - 1}2 + 3^k=\frac{3^k - 1+2\cdot 3^k}2=\frac{3\cdot3^k - 1}2=\frac{3^{k+1} - 1}2$ – Mirko Dec 13 '15 at 0:19

Problem. $\quad$Prove by induction the following formula: $\quad 1+3+3^2+\dots+3^{n−1} = \dfrac{1}{2}\big(3^n−1\big)\,$.

Solution. $\quad$Proof by induction is given in three following steps:

1. Base: assume $\,n=2,\,$ then $\;1+3 = 4 = \dfrac{1}{2}\big(3^2−1\big), \,$ so the formula is correct.
2. Hypothesis: assume formula holds for some positive integer $\,n.\,$
3. Induction: show that formula holds for $\,n+1,\;$ i.e. $\; 1+3+\dots+3^{n−1} + \color{#df0000}{3^n}= \dfrac{1}{2}\big(3^{n+1}−1\big)\,$

• by induction hypothesis we have $\quad 1+3+3^2+\dots+3^{n−1} = \dfrac{1}{2}\big(3^n−1\big)\,$
• let us add $\,3^n\,$ to the formula above in order to complete the induction step: \begin{align} \Big(1+3+3^2+\dots+3^{n−1}\Big) + \color{#df0000}{3^n} & = \dfrac{1}{2}\big(3^{n}−1\big) + \color{#df0000}{3^n} \\ & = \dfrac{1}{2}\big(3^{n}−1+2\cdot \color{#cc0000}{3^n}\big) \\ & = \dfrac{1}{2}\big(3\cdot \color{#df0000}{3^n} -1\big) \\ & = \dfrac{1}{2}\big(\color{#df0000}{3^{n+1}} -1\big). \end{align}

Thus we established that $$\bbox[4pt, border:solid 2pt #FC0000]{\;1+3+3^2+\dots+3^{n−1} + 3^{n} = \dfrac{1}{2}\big(3^{n+1}−1\big)}$$

Q.E.D.

• Note that the base case could be $1$. – YoTengoUnLCD Dec 19 '15 at 3:54

For $n=1$ is true because $1=(3^1-1)/2=2/2=1$. Suppose that is true for $n\leq k$. $1+...+3^{k-1}+3^k=_{HI} \frac{3^k-1}{2}+3^k=\frac{3}{2}3^k-\frac{1}{2}=\frac{3^{k+1}}{2}-\frac{1}{2}=\frac{3^{k+1}-1}{2}$. And then is true for all $n$

First, show that this is true for $n=1$:

$\sum\limits_{k=0}^{1-1}3^k=\frac12(3^1-1)$

Second, assume that this is true for $n$:

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

Third, prove that this is true for $n+1$:

$\sum\limits_{k=0}^{n}3^k=$

$\color\red{\sum\limits_{k=0}^{n-1}3^k}+3^n=$

$\color\red{\frac12(3^n-1)}+3^n=$

$\frac12(3^n-1+2\cdot3^n)=$

$\frac12(3\cdot3^n-1)=$

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

Please note that the assumption is used only in the part marked red.

$\dfrac{3^k - 1}2 + 3^k=\dfrac32 3^k - \dfrac12=\dfrac12 3^{k+1} - \dfrac12=\dfrac12(3^{k+1} - 1)$