2 replies to this topic

[lethalwire]

I'm learning some basic mathematical induction and I'm having an issue with the following:
Prove n < 2^n using mathematical induction for n > 0.

Basis Step:

• 1 < 2^1
  
• 1 < 2

Next, the Inductive step.
The Inductive Hypothesis P(k) is k < 2^k for any arbitrary k > 0.
I must now try to show that p(k+1) is true when p(k) is true.
p(k+1) is (k+1) < 2^(k+1)

I add 1 to both sides of p(k) to obtain:
k+1 < 2^(k) + 1.
So the left side of the inequality looks fine to me because it matches the left side of p(k+1) but I need to solve the right side now.

This is where my problems arises. I'm trying to show that
2^(k)+1 < 2^(k+1). (which is what my book did/didn't do?)

But I'm looking in my book and they seemingly randomly state that 1 <= 2^k.
Then follow with:

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

I understand all of this except where <= 2^(k) + 2^(k) was thrown into the inequality.

Can anyone help me understand this.

[WingedPanther]

k < 2^k : given
k+1 < 2^k + 1 : add 1 to both sides
2^k + 1 <= 2^k + 2^k : because 1<=k < 2^k, or we wouldn't be at this point, now would we?
2^k + 2^k = 2(2^k) : by definition of "multiply by 2"
2(2^k) = 2^(k+1) : by definition of powers

The step in question (3 in this presentation) is just thrown in to allow you to get to the power representation in the next two steps. Since you have inequalities in the same direction, or equalities, then you can assert the overall inequality that k+1 < 2^(k+1)

[lethalwire]

I think I've got it now.
It seems you've added 2^(k) to both sides of 1 <= 2^k.
Which then gives
2^k + 1 <= 2^k + 2^k = 2^(k+1).