Can anyone explain an interesting induction result I got

[cnwilson2010]

Homework Statement

n²<=2ⁿ
n is a natural number

For what values of n is the statement true and prove by induction.

Homework Equations

The Attempt at a Solution

I tried 1 and it worked, I tried 2 and it worked, just for fun I tried 3 and it didn't work, so I assumed the opposite and went to town but could never get the (k+1) portion to make any sense, so after hours and hours, I tried n=4 and it worked, then n=5 works, etc. Why doesn't n=3 work and all the others do? And how do you phrase this in proof language?

 

[Mark44]

Homework Statement

n²<=2ⁿ
n is a natural number

For what values of n is the statement true and prove by induction.

Homework Equations

The Attempt at a Solution

I tried 1 and it worked, I tried 2 and it worked, just for fun I tried 3 and it didn't work, so I assumed the opposite and went to town but could never get the (k+1) portion to make any sense, so after hours and hours, I tried n=4 and it worked, then n=5 works, etc. Why doesn't n=3 work and all the others do? And how do you phrase this in proof language?

It looks like the statement to prove is this:
Show that for any integer n, where n >= 4, that n² <= 2ⁿ

Your base case would need to be at least 4.

As to why this inequality isn't true for n = 3, look at the graphs of y = x² and y = 2^x, for x >= 0. The two graphs intersect at (1, 1) and (2, 4), and (4, 16). Between x = 2 and x = 3, the graph of the quadratic is above the graph of the exponential. After the graphs cross again at (4, 16), the exponential grows more steeply than the quadratic, and the two never cross again. That's essentially what you're proving by induction.

1. Start with a base case of n = 4.
2. Assume that the statement is true for n = k.
3. Show that the statement being true for n = k implies that the statement is also true for n = k + 1.

 

[hunt_mat]

The proof by induction of this inequality is quite fun and I suggest that you play with it some more. I will also provide the small hint that at some point you will need to show that $2k+1<k^{2}$ at some point.