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?

  • $\begingroup$ Is this really algebra-precalculus? $\endgroup$ – Shahar Aug 27 '14 at 20:27
  • $\begingroup$ See the second answer here: math.stackexchange.com/questions/22599/… $\endgroup$ – user133281 Aug 27 '14 at 20:27
  • $\begingroup$ @Shahar Well, it's not calculus! But yes, I guess it'd appear in algebra $2$ in high school. $\endgroup$ – user122283 Aug 27 '14 at 20:27
  • $\begingroup$ @SanathDevalapurkar Not really calculus but I didn't learn this in algebra either. What should I tag this? $\endgroup$ – Shahar Aug 27 '14 at 20:28
  • $\begingroup$ alright, so I guess I get 3^(k-1)+1) which is 3^k? @user133281 $\endgroup$ – gger234 Aug 27 '14 at 20:29
  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.

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


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$


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


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.