1

I am trying to learn a lot of this on my own but I have never tried proving something through mathematical induction. Here is the problem below.

$$1+3+3^2 + \cdots + 3^n = \frac{3^{(n+1)}-1}{2}$$

for all $n\in\mathbb{N}_0$, using mathematical induction. Note that here $\mathbb{N}_0$ means all integers $n \geq 0$.

I need to start with the basis step which would be:

If $n = 0$ then $3^0 = 1$, and $1 = 3^{0+1} = 3 - 1 = 2$, and then $2/2 = 1$. So I have proved the basis step but how do I do the inductive step for this?

P..
  • 14,929
Carl T.
  • 11

3 Answers3

1

You say that you only need help with the inductive step. For simplicity, set $n = k$, where $k \geq 0$. We have that

$$1+3+3^2 + ... + 3^k = \frac{3^{k+1}-1}{2}$$

Now, let's look at the same scenario, except that we add the next part of the sequence, thus we are calculating for $k+1$:

$$1+3+3^2 + ... + 3^k+3^{k+1} = \frac{3^{k+2}-1}{2}$$

Note that we already have a formula for the first parts of the sequence (up to and including $3^k$):

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

If you are able to show that this last statement is true, you are done.

Andrew Thompson
  • 4,431
1

This is call perturbation method, from $\mathit{Concrete \ Mathematics}$ by Graham, Knuth and Patashnik. Denote $S_n=\sum_{k=0}^{n}3^k$. You get: $$ S_n = \sum_{k=0}^{n}3^k\\ S_n + 3^{n+1}=\sum_{k=0}^{n}3^k +3^{n+1}\\ S_{n}+ 3^{n+1} = 1+3\sum_{k=0}^{n}3^k\\ \text{a bit of algebra here}\\ S_n=\frac{3^{n+1}-1}{2} $$

Alex
  • 19,262
0

For the inductive step, assume your claim holds for $n$ and then try to prove it for $n+1.$ That is,

Assume: $1+3+3^2+...+3^n=\frac{3^{n+1}-1}{2}$.

Then see if you can prove that $1+3+3^2+...+3^n+3^{n+1}=\frac{3^{(n+1)+1}-1}{2}$.

How to do this? Start by transforming the left hand side using what you already know:

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

Now combine these fractions and see if you can massage them into $\frac{3^{(n+1)+1}-1}{2}$.

That is: $\frac{3^{n+1}-1}{2}+3^{n+1}=\frac{3^{n+1}-1+2(3^{n+1})}{2}=\frac{3(3^{n+1})-1}{2}=\frac{3^1(3^{n+1})-1}{2}=\frac{3^{(n+1)+1}-1}{2}.$

  • So what do I exactly do? I have never done this before. I need to combine 3^n+3^(n+1)? Then that combination needs to somehow look like the right hand side in order to be proved? – Carl T. Dec 08 '13 at 16:49
  • Here's the idea of induction: you want to prove something for all $n$. You can list $n$ explicitly as: $0,1,2,3....$. But obviously you can't actually prove that your claim holds for each $n$ individually, because there are infinite $n$'s. Instead what you do is prove the first $n$, which you did. And then you prove that: if my claim holds for any particular $n$, it holds for $n+1$ as well. So you've proved the first one explicitly and hence you know your claim holds for $n=0$. Well now you know it holds for $n=0+1=1$. And since you know it holds for $n=1,$ it holds for $n=1+1=2.$ And so on... –  Dec 08 '13 at 17:00
  • To prove "true for $n$" $\implies$ "true for $n+1$". You need to assume that your claim is true for $n$. Then based on that assumption, prove that your claim is also true for $n+1$. I gave your assumption and what you need to prove. Did that make sense? Then you can just substitute $\frac{3^{n+1}-1}{2}$ for $1+3+3^2+...+3^n$ as per your assumption. Then you should be able to show that claim is true. I'll do it explicitly for you if need be. –  Dec 08 '13 at 17:05
  • Yes, I think if you could, try to show how it would be done. I understand what you are saying but its hard to get it going, also I just want to be sure that I can work with something that is right in the future to have a sort of guide line reference. – Carl T. Dec 08 '13 at 17:39
  • I completed the proof on the last line. –  Dec 08 '13 at 17:50