Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Can anyone explain an interesting induction result I got

  1. Jun 16, 2011 #1
    1. The problem statement, all variables and given/known data
    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. jcsd
  3. Jun 16, 2011 #2


    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.

    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.
  4. Jun 17, 2011 #3


    User Avatar
    Homework Helper

    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 [itex]2k+1<k^{2}[/itex] at some point.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook