Proving Mathematical Induction using 2^n>n, n≥1 | Homework Solution

[Physicsissuef]

Homework Statement

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

Homework Equations

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?

 

[mjsd]

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

 

[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:

The Attempt at a Solution

$$n=1$$

$$2^1>1$$

$$2>1$$

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.

$$n=k$$

$$2^k>k$$

Okay, we've assumed that it's true for n=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?

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...)

 

[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?

 

[Physicsissuef]

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?

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.

 

[belliott4488]

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.

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?

 

[Physicsissuef]

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?

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.

 

[HallsofIvy]

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.)

 

[Physicsissuef]

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.)

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

 

[Physicsissuef]

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.)

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

 

[HallsofIvy]

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

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

 

[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.

 

[Physicsissuef]

Any help?

 

[HallsofIvy]

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

 

[Physicsissuef]

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

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

 

[HallsofIvy]

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.

 

[Physicsissuef]

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

 

[HallsofIvy]

What are you referring to? It is true that for n any positive integer, 2ⁿ> 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 2¹= 2> 1.

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

 

[Physicsissuef]

What are you referring to? It is true that for n any positive integer, 2ⁿ> 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 2¹= 2> 1.

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

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

 

[Physicsissuef]

Any help, please?

 

[belliott4488]

I'm not sure how to make this clearer, but I'll try.

I think we're in agreement that you can show the following:

Case 1: $$n=1$$: $$2^1>1$$

Case k: $$n=k$$: assert that $$2^k>k$$

Case k+1:
$$2^{k+1}=2*2^k$$
$$2^{k+1}>2*k$$, by assertion
$$2^{k+1}>k+k$$

From the last line we can unambiguously conclude that
$$2^{k+1}>k+1$$
for any k greater than or equal to 1.

Is that not what you wanted to prove? Where does the ambiguity between "greater than" and "greater" enter?

It seems that you are asserting that
if $$a>b \geq c$$,
then $$a \geq c$$, which is not correct.
$$a>c$$ would be the correct conclusion.

 

[Physicsissuef]

I'm not sure how to make this clearer, but I'll try.

I think we're in agreement that you can show the following:

Case 1: $$n=1$$: $$2^1>1$$

Case k: $$n=k$$: assert that $$2^k>k$$

Case k+1:
$$2^{k+1}=2*2^k$$
$$2^{k+1}>2*k$$, by assertion
$$2^{k+1}>k+k$$

From the last line we can unambiguously conclude that
$$2^{k+1}>k+1$$
for any k greater than or equal to 1.

Is that not what you wanted to prove? Where does the ambiguity between "greater than" and "greater" enter?

It seems that you are asserting that
if $$a>b \geq c$$,
then $$a \geq c$$, which is not correct.
$$a>c$$ would be the correct conclusion.

$$a \geq c$$ wouldn't be correct?

 

[HallsofIvy]

Hmm. "a$\ge$c" includes "a> c" so I would say If it is true that a> c, then it is also true that a$\ge$ c. It is true that 5> 4 and also true that 5$\ge$4. It is not as "precise" as saying a> c but it is still true. Perhaps belliiott4488 would disagree with that.

 

[Physicsissuef]

why a>c is the correct conclusion? Can you give me some simplifed example, with real numbers?
Like when 5>4$\ge$3, then 5$\ge$3

 

[HallsofIvy]

Yes, 5> 4$\ge$ 3 tells you that 5$\ge$ 3. I think Belliott4488 is saying that 5> 3 would be more "precise" since it would give more information. But precisely because 5> 3, it is true that 5$\ge$ 3.

To get back to what you were doing, you were trying to prove, by induction, that 2ⁿ> n for all positive integers n.
Okay, if n= 1 that says 2¹= 2> 1 which is true.

Assume that 2^k> k for some k. Then 2^k+1= 2(2^k) and, since 2^k> k, that is greater than 2k. That was where you were stuck.

My point was that you can do another induction to show that, for any positive integer n, 2n$\ge$n+1. Here you must have "$\ge$" since, with n= 1, 2(1)= 2= 1+ 1, not ">". But then you have 2^k+1= 2(2^k)> 2k$\ge$k+1[/itex]. Because of the first ">", from that you can conclude either 2^k+1k+1 or 2^k+1$\ge$k+1; they are both true but it is the first you need because that was what you were trying to prove.