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

Proof by induction

  1. Dec 11, 2009 #1
    1. The problem statement, all variables and given/known data

    prove by induction that
    [tex]\frac{1}{n^2} < \frac{1}{n(n-1)}[/tex]

    2. Relevant equations

    n/a

    3. The attempt at a solution

    Let
    [tex]P(n):\frac{1}{n^2} < \frac{1}{n(n-1)}[/tex]

    Since P(1) is undefined, the base case is P(2)
    [tex]P(2) = \frac{1}{2^2} < \frac{1}{2(2-1)}[/tex]
    [tex]P(2) = \frac{1}{4} < \frac{1}{2}[/tex]

    Therfore P(n) is true for all n>1

    Inductive Step
    Assume [tex]P(k)[/tex] is true.

    [tex]P(k):\frac{1}{k^2} < \frac{1}{k(k-1)}[/tex]

    I know what I need my inequality to look like for [tex]k+1[/tex] I am just having problems getting there. my [tex]k+1[/tex] will look like:
    [tex]P(k+1):\frac{1}{(k+1)^2} < \frac{1}{(k+1)[(k+1)-1]}[/tex]
    after simplification:
    [tex]P(k+1):\frac{1}{(k+1)^2} < \frac{1}{(k+1)(k)}[/tex]
    So I know where I need to be. Consider this is just side work.

    So for [tex]k+1[/tex] I can rewrite an expansion on the LHS as:
    [tex]\frac{1}{k^2+2k+1}[/tex]
    And based on my inductive step the RHS of the inequality is:
    [tex]\frac{1}{[k(k-1)]+2k+1}[/tex]

    And this is where I am hitting the block. Try as I might, I can't see any steps to take to make [tex]\frac{1}{[k(k-1)]+2k+1}[/tex] equivalent to [tex]\frac{1}{(k+1)(k)}[/tex]

    I am worried that I may have set up my induction incorrectly though.
     
    Last edited: Dec 11, 2009
  2. jcsd
  3. Dec 11, 2009 #2

    Mark44

    Staff: Mentor

    The line above isn't true. All you have done is establish that the proposition is true for your base case.
    I would approach this in a different way. 1/k^2 < 1/((k -1)k) is equivalent to k^2 > k(k - 1). We can safely assume that all factors are nonnegative. If you can prove by induction that k^2 > k(k - 1), then you will have proved the equivalent statement, the one in your problem.
     
  4. Dec 11, 2009 #3
    Thanks, that does make it rather easy.
    Just so I am sure I can write this correctly, the justification for equating the two identical inequalities is that k(k-1) > 0 Is that because of the base case starting with n>1 or because induction is on [tex]\mathbb{N}[/tex]
     
  5. Dec 11, 2009 #4

    Mark44

    Staff: Mentor

    If a < b, and both a and b are positive, then 1/a > 1/b. For your original inequality it's reasonable to assume that n > 1 (and hence positive); otherwise you would be dividing by 0 when n = 1. For your induction proof, you are proving it for all n >= 2.

    Generally speaking (but with caveats) if a < b, then 1/a > 1/b. The caveat is that both a and b have to be the same sign. For example, 2 < 3 and 1/2 > 1/3. OTOH, -1 < 2, but 1/(-1) > 1/2 is not true.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook