# Mathematical induction

1. Feb 23, 2008

### Physicsissuef

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

$$2^n>n , n\geq 1$$

2. Relevant equations

3. The attempt at a solution

$$n=1$$

$$2^1>1$$

$$2>1$$

$$n=k$$

$$2^k>k$$

$$n=k+1$$

$$2^k^+^1=2^k*2>2k=k+k>k+1$$

$$2^k^+^1>k+1$$

Ok, I don't understand the part k+k>k+1
If I get k=1 (from the $$k\geq 1$$)
1+1>1+1
2>2 which is not actually correct. Any help?

2. Feb 23, 2008

### mjsd

what you should have is
$$k+k\geq k+1, \quad k\geq 1$$
then your first ">" will give you the desire relationship

3. Feb 23, 2008

### belliott4488

It looked to me like you were on your way to solving this correctly, so my guess is that you've just misunderstood either what you're supposed to do (which happens a lot when people learn induction) or that you haven't recognized what you've done.

Let's spell out what you've done:
Okay, that's step 1: show that what you're trying to prove is true for one specific case (n=1). Now you go to step 2, i.e. show that if it's true for some value of n, say, n=k, then it must also be true for the next value, n=k+1.
Okay, we've assumed that it's true for n=k ...
Now here's where you lost me. You're attempting to show that for n=k+1 you get
$$2^{k+1}>k+1$$,
given your assumption that $$2^k>k$$.

You've got that
$$2^k^+^1=2^k*2$$
and since by assumption
$$2^k>k$$
you know that
$$2^k*2>k*2$$,
which means (combining these expressions)
$$2^k^+^1>k*2$$.
So, the question boils down to this: is $$k*2>k+1$$, which would give you what you're trying to prove?

Is it?

(I still don't understand your question about the n=1 case, but maybe it's moot now...)

4. Feb 23, 2008

### belliott4488

Oh! Now I see what you were asking! You're not sure if you can make the final jump for the case k=1.

Keep in mind that what you're really trying to show is that $$2^{k+1}>k*2$$ ... will that still be true in this case?

5. Feb 23, 2008

### Physicsissuef

This is standard principle for solving tasks like this. So, yes, will it be still true? As far as I know, it wouldn't be true. So it must be, $$k+k\geq k+1, \quad k\geq 1$$, which is not what my "book result" says. Maybe its their typo fault.

6. Feb 23, 2008

### belliott4488

I'm not sure I understand. The problem states that the relation should be true for $$n\geq1$$, so finding that the inductive relation works for $$k\geq1$$ is consistent with that, isn't it? In other words, you've shown that:
1. The relation is true for n = 1.
2. If the relation holds for some value of $$n=k$$, $$k\geq1$$, then it also hold for $$n=k+1$$.

Doesn't that do what you want?

7. Feb 24, 2008

### Physicsissuef

Do you look the part k+k>k+1 ?? Try to do k=1, you'll get 1+1>1+1, which is not actually correct.

8. Feb 24, 2008

### HallsofIvy

Staff Emeritus
What I would do is use a separate induction:
if n>1 then n+n> n+1.

If n= 2 then n+n= 2+ 2= 4> 3= 2+ 1= n+1

Assume that, for a fixed k> 1, k+ k> k+1

Then (k+1)+ (k+1)= k+ k+ 2> (k+1)+ 2> (k+ 1)+ 1 because 2> 1.

(k+ k$\ge$ k+ 1 is true for all positive integers.)

9. Feb 24, 2008

### Physicsissuef

Is it correct, like I wrote on the first post?
Is it correct, if I write k+ k$\ge$ k+ 1?

10. Feb 24, 2008

### Physicsissuef

But shouldn't it be $$k\geq1$$, so $$k+k\geq$$ $$k+1$$ ?

11. Feb 24, 2008

### HallsofIvy

Staff Emeritus
That's what I said, isn't it? That k+ k$\ge$ k+ 1 for all positive integers?

12. Feb 28, 2008

### Physicsissuef

If we take, $$k+k\geq$$ $$k+1$$
Than it should be:
$$2^k^+^1 \geq k+1$$
from:
$$2^k^+^1=2^k*2>2k=k+k \geq k+1$$
which is not completely true.
Because also
$$2^k^+^1 > k+1$$ is correct.

13. Mar 2, 2008

### Physicsissuef

Any help?

14. Mar 2, 2008

### HallsofIvy

Staff Emeritus
If it is true that A> B then it is certainly true that A$\ge$ B!

15. Mar 2, 2008

### Physicsissuef

But we need to prove that A>B and not A$\ge$B.

16. Mar 2, 2008

### HallsofIvy

Staff Emeritus
Now, I understand. It was a typo error on my part.

I had stated at the beginning that you could do a separate induction to prove "if n>1 then n+n> n+1" which has ">" and that was what I proved. Unfortunately, I then wrote "$\ge$" in the last line when I didn't mean to.

17. Mar 2, 2008

### Physicsissuef

So, in my book, is not correct at all, right?

18. Mar 2, 2008

### HallsofIvy

Staff Emeritus
What are you referring to? It is true that for n any positive integer, 2n> n. What I have been talking about was the "part" of that I proved: If n> 1, then 2n= n+ n> n+ 1. In fact, what I started to prove, and then confused myself about, was that if n is any integer, 2n$\ge$ n+ 1.

To prove THAT: If n= 1, 2n= 2= n+1 so it is true.

If it is true for any k, then 2(k+ 1)= 2k+ 2> (2k+1)+ 1> 2k so 2(k+1)$\ge$(k+1)+ 1 and we are done.

Now for your original problem (which has been going on long enough!):
If n= 1, then 21= 2> 1.

Assume that 2k> k for some k. Then 2k+1= 2(2k)> 2k $ge$ k+1 and we are done.

19. Mar 3, 2008

### Physicsissuef

But if we say that 2k+1= 2(2k)> 2k $\ge$ k+1
then 2k+1 $\ge$ k+1,
and what the original problem is 2k+1 > k+1
Do you understand what I mean?

20. Mar 6, 2008