# Can anyone explain an interesting induction result I got

1. Jun 16, 2011

### cnwilson2010

1. The problem statement, all variables and given/known data
n2<=2n
n is a natural number

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

2. Relevant equations

3. 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?

2. Jun 16, 2011

### Staff: Mentor

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

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 = x2 and y = 2x, 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.

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.