1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by induction
  1. Induction Proof (Replies: 7)

  2. Induction proof (Replies: 1)

  3. Proof By Induction (Replies: 2)

  4. Proof by induction (Replies: 1)

  5. Proof by Induction (Replies: 3)

Loading...