Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Use proof by induction and show that the formula holds for all positive integers:$$1+3+3^2+\dots+3^{n-1}=\frac{3^n -1}2$$

The confusing step in my opinion is the first expression: $3^{n-1}$, when I have to show for $k+1$. Any solutions?

share|cite|improve this question
Is this really algebra-precalculus? – Shahar Aug 27 '14 at 20:27
See the second answer here:… – user133281 Aug 27 '14 at 20:27
@Shahar Well, it's not calculus! But yes, I guess it'd appear in algebra $2$ in high school. – Sanath K. Devalapurkar Aug 27 '14 at 20:27
@SanathDevalapurkar Not really calculus but I didn't learn this in algebra either. What should I tag this? – Shahar Aug 27 '14 at 20:28
alright, so I guess I get 3^(k-1)+1) which is 3^k? @user133281 – gger234 Aug 27 '14 at 20:29
up vote 7 down vote accepted
  1. Show $3^{1-1}=\dfrac{3^1-1}{2}$

  2. Assume $\sum\limits_{k=0}^{n-1}3^k=\dfrac{3^n-1}{2}$

  3. Prove $\sum\limits_{k=0}^{n}3^k=\dfrac{3^{n+1}-1}{2}$:

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

    • $(\sum\limits_{k=0}^{n-1}3^k)+3^n=\dfrac{3^n-1}{2}+3^n$

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

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

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

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

Note that the induction-step is applied only at the second bullet.

share|cite|improve this answer
wow nice, could you please explain the second last line? thanks – gger234 Aug 27 '14 at 20:36
@gger234: I added a line explaining that; hope it helps... – barak manos Aug 27 '14 at 20:40
@gger234: Note that the induction step takes place only at the second bullet of section 2. – barak manos Aug 27 '14 at 20:42
@gger234: $X+2\cdot{X}=3X$ – barak manos Aug 27 '14 at 20:43
(Don't you also want to include the case $n=1$?) – user84413 Aug 27 '14 at 20:44

Suppose that $x \neq 1$. We wish to show by inducting on $n$ that $\sum\limits_{k=0}^{n-1}x^{k} = \frac{x^{n} - 1}{x-1}$.

Then $1 = \frac{x-1}{x-1}$ so that the formula holds for $n = 1$. Suppose that we have $\sum\limits_{k=0}^{n-1}x^{k} = \frac{x^{n} - 1}{x-1}$. We must show that $\sum\limits_{k=0}^{n}x^{k} = \frac{x^{n+1} - 1}{x-1}$.

We have $\sum\limits_{k=0}^{n}x^{k} = \sum\limits_{k=0}^{n- 1}x^{k} + x^{n} = \frac{x^{n} - 1}{x-1} + x^{n}\frac{x -1}{x-1} = \frac{x^{n} - 1 + x^{n+1} - x^{n}}{x - 1} = \frac{x^{n+1} - 1}{x-1}$

share|cite|improve this answer

For n+1 it is


$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{3\cdot 3^{n}-1}{2}$

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{(1+2)\cdot 3^{n}-1}{2}$

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\frac{1\cdot 3^{n}-1}{2}+\frac{2\cdot 3^{n}}{2}$

$\left( 1+3+3^2+\ldots +3^{n-1}\right) +3^n=\left( \frac{1\cdot 3^{n}-1}{2}\right) + 3^n$

share|cite|improve this answer

For the base case simply show that the premise is true for the smallest positive integer: $\mathsf P(1)$.

For the iterative case, you have to show that if the premise holds for $n$, then it is implied to hold for $n+1$.   $\mathsf P(n)\implies\mathsf P(n+1)$

Do that by substituting $n+1$ for $n$ and demonstrate that the left and right hand side both contain terms of the original premise and the same modifier.

Here we show that modifier is the addition of $3^n$.

$\begin{align} \text{Prove }\forall n\in \mathbb Z^+: \sum_{k=0}^{n-1} 3^k & = \frac {3^n-1}{2} & \text{premise } \\[3ex] 3^0 & = \frac{3^1-1}{2} & \text{base case} \\[3ex] 3^n + \sum_{k=0}^{n-1} 3^k & = \sum_{k=0}^{n} 3^k \\[1ex] 3^n+\frac {3^n-1}{2} & = \frac{3\cdot 3^n-1}{2} \\[2ex] \therefore \sum_{k=0}^{n-1} 3^k & = \frac {3^n-1}{2} \implies \sum_{k=0}^{n} 3^k = \frac{3^{n+1}-1}{2} &\text{iterative step } \\[2ex]\therefore \forall n\in\mathbb Z^+: \sum_{k=0}^{n-1} 3^k & = \frac {3^n-1}{2} & \text{by induction} \end{align}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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