# Homework Help: Proof by induction example

1. Sep 25, 2009

### zeion

1. The problem statement, all variables and given/known data

We'll show that, if x => -1, then (1 + x)^n => 1 + nx for all positive integers n.

Solution ...
The text goes on to explain that if n = 1 is true, we assume n = k is true, and n = k + 1 is true.

I understand everything until this part:

Since

(1 + x)^k+1 = (1 + x)^k(1 + x) => (1 + kx)(1 + x)

How does 1 + nx where n = (k+1) become (1 + kx)(1 + x)?

2. Relevant equations

3. The attempt at a solution

2. Sep 25, 2009

### LCKurtz

"The text goes on to explain that if n = 1 is true, we assume n = k is true, and n = k + 1 is true."

That shows a confused understanding of what your text is doing. You don't "assume n = k is true". You assume the proposition you are trying to prove is true for n = k. Then what you are trying to prove is that the proposition is true for k + 1.

So your assumption is: (1 + x)k ≥ 1 + kx

What you are trying to prove is: (1 + x)k+1 ≥ 1 + (k+1)x

So you might start by multiplying both sides of your assumption by (1 + x). That will get you the left side of what you are trying to prove and it is your job to show what you have satisfies the right side.

3. Sep 25, 2009

### zeion

So I need to show that

(1 + kx)(1 + x) = 1 + (k+1)x

4. Sep 25, 2009

### VietDao29

Well,

(1 + x)k + 1 = (1 + x)k(1 + x), right?

And from your Induction Hypothesis, we have: (1 + x)k >= 1 + kx, right? So, in conclusion:

(1 + x)k + 1 = (1 + x)k(1 + x) >= (1 + kx)(1 + x).

5. Sep 25, 2009

### LCKurtz

You can't show that because those aren't equal. But wouldn't ≥ do? Can you show that? Then write the full inequality up nice.

6. Sep 25, 2009

### zeion

Assume:
(1 + x)^k >= (1 + kx)
Then:
(1 + x)^k+1 which equals to (1 + x)^k(1 + x) >= (1 + kx)(1 + x)
since I multiplied (1 + x) to (1 + x)^k to make (1 + x)^k+1, I have to do the same to the other side.

So I have to show that
(1 + kx)(1 + x) >= 1 + (k+1)x

1 + x + kx + kx^2 >= 1 + (k+1)x
1 + (1 + k)x + kx^2 >= 1 + (k+1)x

So the left side is +kx^2 more than the right side

7. Sep 25, 2009

### LCKurtz

Yes. You now have the argument down and understand the steps. And you have what I would call a good "scratch paper" writeup. Having that all figured out, a nice writeup of the induction step argument you have would be to write:

Assume (1 + x)k ≥ 1 + kx

Then:

(1 + x)(k+1) = (1 + x)k(1+x) ≥ (1 + kx)(1 + x)

= 1 + x + kx + x2 = 1 +(k + 1)x + kx2

≥ 1 + (k + 1)x

And you might want to note why it is important x > -1.

8. Sep 25, 2009

### zeion

Ok thanks for the help.