Help with induction equation - please?

Question

Use induction to show that the sum of the first $n$ power of $3$ is less than the new power:

$$\forall n \ge 1:\ 3^1 + 3^2 + \cdots + 3^n < 3^{n+1}$$

Make sure to show all steps of the inductive argument.

To be clear - I did not mean to ask that someone answer this for me - I thought the site was used for people to help you work through a problem? Not necessarily give me the answer?

I have struggled with inductions and do not understand the logic behind the steps, even reading examples from texts and other websites. I guess I would like someone to help explain the steps to me (in plain non-math saavy English?) so that I will be able to answer this question?

Answer 1

I'll give you a similar problem with a hint: Prove that $2^1 + 2^2 + \cdots + 2^n < 2^{n+1}$.

Hint: $2^1 + 2^2 + \cdots + 2^k + 2^{k+1} = (2^1 + 2^2 + \cdots + 2^k) + 2^{k+1} < (2^{k+1}) + 2^{k+1} = 2*2^{k+1} = 2^{k+2}$.

Answer 2

You'll need to understand inequalities. It is typical, especially in real analysis, to replace smaller quantities by larger ones. I'll walk you through the induction step, as this is key.

Suppose the assertion holds for all $n \leq k$. For $n = k+1$ we have the following:

$$\sum_{j = 1}^{k+1} 3^j = 3^{k+1} + \sum_{j = 1}^k 3^j$$

Here we're just peeling off the $(k+1)$st term. This is common in induction arguments with sums.

$$ \ldots < 3^{k+1} + 3^{k+1} $$

Now we're using the induction hypothesis. I can bound the sum of the first $k$ powers of $3$ by the next power of $3$. In doing this, replace the sum with $3^{k+1}$.

$$ \ldots = 2(3^{k+1}) $$

Well, there's two of those things.

$$ \ldots < 3^{k+2} $$

The trick: Two is smaller than three, so replace the two out front by a three. Well, $3 = 3^1$, and we get $3^{k+2}$, which is what we needed. Try to run through this yourself and get a cleaner write-up.