Results 1 to 3 of 3

Math Help - Mathematical induction

  1. #1
    Junior Member pirateboy's Avatar
    Joined
    Jul 2010
    From
    Portland, OR
    Posts
    34

    Mathematical induction

    I have a two quick questions on mathematical induction. I'm new to it, so my answers seem a little shaky. I wanted to see what some of the you guys thought.

    Question 1


    We're asked to prove using mathematical induction that for all natural numbers n,
    \frac{1}{2!} + \frac{2}{3!}+\dots+\frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}

    Proof (?):

    Let k\in\mathbb{N}

    1. Base case: k=3:

    \begin{align*}  \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}&=\frac{1}{2}+\frac{2}{6}+\frac{3}{24}  \\&=\frac{23}{24}\\&=1-\frac{1}{(3+1)!}\end{align*}
    CHECK

    2. Assume \forall k\in\mathbb{N},
    \frac{1}{2!} + \frac{2}{3!}+\dots+\frac{k}{(k+1)!} = 1 - \frac{1}{(k+1)!}.

    Then,
    \begin{align*}\frac{1}{2!} + \frac{2}{3!}+\dots+\frac{k}{(k+1)!} + \frac{k+1}{(k+2)} &= 1 - \frac{1}{(k+1)!} + \frac{1}{(k+2)!}\\&=1 - \frac{1}{(k+1)!}\left(\frac{k+2}{k+2}\right) + \frac{k+1}{(k+2)!}\\&=1 - \frac{k+2}{(k+2)!} + \frac{k+1}{(k+2)!}\\&=1-\frac{1}{(k+2)!}\end{align*}

    3. Thus, by P.M.I. blah blah QED.

    Is this legit? It just seems strange to me since I'm working completely on the right side. Yet any other way I try to attempt seems to lead me down some crazy algebra path (I could very well be doing it wrong).

    Question 2
    Use generalized PMI principles of mathematical induction to prove
    n!>3n\quad\text{for}\quad n\geq 4

    Proof(?):
    First, we know that since we're taking a factorial that n must be an integer (this was not originally given to us, so I guess it's implied?).

    Let k\in\mathbb{Z},\quad k\geq 4
    (I guess that since k is greater than 4, I might rotate that Z pi radians and define k as a natural number?)

    1. Base case: k = 4

    4!=24>3\cdot4 = 12

    Good.

    2. Mathematical induction:
    Assume that for some integer k\geq 4 that k!>3k

    Note,
    3(k+1)=3k+3>3k

    Also note,
    k!\geq k(3!)>3(k+1)=3k+3

    And
    (k+1)!>k!
    (since k is always positive.)

    So,
    (k+1)!>k!>3(k+1)>3k

    3. by general PMI, i'm done?

    Again, this feels a bit shaky to me. Perhaps because I dealt with so many pieces individually before putting it all back together.

    So again, my question: Am I using mathematical induction properly here? Do my proofs prove what they are supposed to?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,404
    Thanks
    1293

    Re: Mathematical induction

    Wouldn't the base case be k = 1?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49

    Re: Mathematical induction

    Quote Originally Posted by pirateboy View Post
    1. Base case: k=3:
    Use k = 1 as Prove It said... I can see why it might look like that was out of the question, but... the formula tells you you're done as soon as you've written a term equal to

    \frac{n}{(n+1)!} ... and that's the case after the first term!

    Quote Originally Posted by pirateboy View Post
    2. Assume \forall k\in\mathbb{N},
    Not quite - you're assuming the formula true for some (any) particular k.

    Then you're ok.

    Quote Originally Posted by pirateboy View Post
    Is this legit? It just seems strange to me since I'm working completely on the right side.
    To get a handle on why your first proof is fine (... and the other one not) you need to meditate a little bit on what the 'blah blah' part is actually saying...



    So the body of your proof must show that 'true for k+1' follows inevitably from 'true for k'. So you need to be conscious of making a chain of sentences linked by 'implies' or 'therefore'.

    Not necessarily a chain of expressions linked by equals signs. (Though each sentence may well be such a chain.)

    Notice I've inserted one expression directly after the point where you say 'Then'. I wouldn't bother highlight this change except it bears on what I was just saying. Makes it clearer (though only slightly) that you are beginning a chain of expressions that says the original formula is true for k + 1.



    Quote Originally Posted by pirateboy View Post
    Note,
    3(k+1)=3k+3>3k

    Also note,
    k!\geq k(3!)>3(k+1)=3k+3

    And
    (k+1)!>k!
    (since k is always positive.)

    So,
    (k+1)!>k!>3(k+1)>3k

    3. by general PMI, i'm done?

    Again, this feels a bit shaky to me. Perhaps because I dealt with so many pieces individually before putting it all back together.
    Well, the way it has to fit together is in a chain of inevitable consequences starting just from k! > 3k.

    Your likely choice of a first step forward from that would, I guess, be k! > k(3!). Which is obviously true... but doesn't actually follow! At least not directly. Here's a chain that works...

    Last edited by tom@ballooncalculus; July 16th 2012 at 12:11 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical induction
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: February 18th 2011, 01:25 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 14th 2010, 02:42 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathematical induction
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: October 6th 2009, 06:44 AM
  5. Mathematical Induction
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 22nd 2009, 04:40 AM

Search Tags


/mathhelpforum @mathhelpforum