Induction inequality problem - is my work correct?

[fonzo1979]

Hi all,

I'm trying to tutor a friend in discrete math so he can pass his class, but it's been a long time since I graduated college and I can't recall exactly how to solve some of these problems. In particular, I'm having trouble with the following:

Prove that:
2n + 1 <= 2^n for n >= 3

My first step is to verify that the inequality is true when n=3. This turns out to be true.

The second step is to substitute all the n's with (k+1). This gives me:

2(k+1) + 1 <= 2^(k+1)

After distributing the 2 on the left hand side, I get:

2k + 2 + 1 <= 2^(k+1)

Subtracting 2 from both sides leaves me with:

2k + 1 <= 2^(k+1) - 2

And at this point, I assume the original inequality to be true and substitute (2k+1) completely with 2^k. I don't know if this step is correct, but here's what I get:

2^k <= 2^(k+1) - 2

Now I simplify a bit

2^k <= 2*(2^k) - 2

Divide by 2^k to get:

1 <= 2 - 2/(2^k)

And more simplifying and manipulating...

2/(2^k) <= 1

And more simplifying and manipulating...

2 <= 2^k

And that statement looks obviously true for the specified condition of k >= 3

But is all this correct? Something about it looks wrong to me... does anyone know if I did this correctly?

 

[Odie_33]

2^k>= 2k+ 1 as starters and therefore you need to prove that when the integer is added by one :

2^(k+1) >= 2(k+1) + 1.

Need to somehow show that 2^(k+1) >= 2k + 3

Lets start with the 2^k >= 2k + 1

In order to get to the result on the Left hand side, we need to multiply both sides by 2^1 (i.e. 2)

2.2^k >= 2(2k + 1)

so looking at the right hand side, 2(2k + 1) = 4k + 2 or 2k + (2k + 2)

Obviously for values of k, (2k + 2) > 3 and therefore 2.2^k >= 2k + 3

I wonder if this is an even more stranger deduction?

 

[daon]

it can be a little "easier"

2^k >= 2k+1 if and only if
2^k+2^k >= (2k+1)+(2k+1) = 2k+(2k+2) > 2k+(2+1) = 2(k+1)+1 if and only if
2^(k+1) > 2(k+1)+1

 

[Deleted member 4993]

Hi all,

I'm trying to tutor a friend in discrete math so he can pass his class, but it's been a long time since I graduated college and I can't recall exactly how to solve some of these problems. In particular, I'm having trouble with the following:

Prove that:
2n + 1 <= 2^n for n >= 3

My first step is to verify that the inequality is true when n=3. This turns out to be true.

The second step is to substitute all the n's with (k+1).

2[sup:ruh6r2xp]k+1[/sup:ruh6r2xp] = 2 * 2[sup:ruh6r2xp]k[/sup:ruh6r2xp] => 2*(2k+1) = 4k + 2 = 2(k+1) +1 +(2k -1) => 2(k+1) + 1




This gives me:

2(k+1) + 1 <= 2^(k+1)

After distributing the 2 on the left hand side, I get:

2k + 2 + 1 <= 2^(k+1)

Subtracting 2 from both sides leaves me with:

2k + 1 <= 2^(k+1) - 2

And at this point, I assume the original inequality to be true and substitute (2k+1) completely with 2^k. I don't know if this step is correct, but here's what I get:

2^k <= 2^(k+1) - 2

Now I simplify a bit

2^k <= 2*(2^k) - 2

Divide by 2^k to get:

1 <= 2 - 2/(2^k)

And more simplifying and manipulating...

2/(2^k) <= 1

And more simplifying and manipulating...

2 <= 2^k

And that statement looks obviously true for the specified condition of k >= 3

But is all this correct? Something about it looks wrong to me... does anyone know if I did this correctly?