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

Question

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

Answer 1

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$

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

Assume $$S=1+3+3^2+3^3+...+3^{n-1}$$ in this case $$ 3\cdot S=3\cdot1+3\cdot3+3\cdot3^2+...+3\cdot3^{n-2}+3\cdot3^{n-1}$$ $$ 3\cdot S=3+3^2+3^3+...+3^{n-1}+3^{n}$$ Now subtracting $S$ from $3\cdot S$ we have: $$3\cdot S-S=-1+3-3+3^2-3^2+3^3-3^3+...+3^{n-1}-3^{n-1}+3^n$$ it is easy to see that the result will be $$2\cdot S=3^n-1$$ so $$S=\frac{3^n-1}{2}$$ Replacing $S$ with the original sum we have: $$1+3+3^2+3^3+...+3^{n-1}=\frac{3^n-1}{2}$$ Q.E.D