Take the 2-minute tour ×
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.

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

4 Answers 4

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

For n+1 it is

$1+3+3^2+\ldots+3^{n-1}+3^n=\frac{3^{n+1}-1}{2}$

$\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|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|improve this answer

Your Answer

 
discard

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.