Results 1 to 6 of 6

Math Help - Another proof by induction.

  1. #1
    Newbie
    Joined
    Feb 2010
    From
    Canada
    Posts
    15

    Another proof by induction.

    I was looking over this problem and im pretty sure you use induction.. but what would your base case be and when subing (k+1) for n, what is the inital formula we want to achieve? I dont exactly know how to approach this problem.
    Last edited by mr fantastic; July 14th 2010 at 02:23 AM. Reason: Restored deleted question (or part thereof).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jess0517 View Post
    I was looking over this problem and im pretty sure you use induction.. but what would your base case be and when subing (k+1) for n, what is the inital formula we want to achieve? I dont exactly know how to approach this problem.

    Attachment 18183
    http://www.mathhelpforum.com/math-he...tml#post534980
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello jess0517

    We have to prove that \displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n is an integer for all \displaystyle n \in \mathbb{N}.

    First we factorise:

    \displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n=\tfrac16n(2n^2+3  n+1)
    \displaystyle =\tfrac16n(n+1)(2n+1)
    So we must prove that \displaystyle n(n+1)(2n+1) is a multiple of 6; in other words, that it is a multiple of 2 and of 3.

    First, note that one of \displaystyle n and \displaystyle (n+1) is even. So \displaystyle n(n+1)(2n+1) is even.

    Next, note that \displaystyle n is either a multiple of 3, in which case there is nothing left to prove; or it leaves a remainder 1 or 2 when divided by 3.

    Case I: \displaystyle n leaves a remainder 1; in which case \displaystyle n = 3m + 1, m \in \mathbb{N}. Therefore
    \displaystyle 2n+1 = 6m + 3
    and is therefore a multiple of 3.

    Case II: \displaystyle n leaves a remainder 2; in which case \displaystyle n = 3m +2, m \in \mathbb{N}. Therefore
    \displaystyle n+1 = 3m + 3
    and is therefore a multiple of 3.

    This concludes the proof.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2010
    From
    Canada
    Posts
    15
    Quote Originally Posted by Grandad View Post
    Hello jess0517

    We have to prove that \displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n is an integer for all \displaystyle n \in \mathbb{N}.

    First we factorise:

    \displaystyle \tfrac13n^3+\tfrac12n^2+\tfrac16n=\tfrac16n(2n^2+3  n+1)
    \displaystyle =\tfrac16n(n+1)(2n+1)
    So we must prove that \displaystyle n(n+1)(2n+1) is a multiple of 6; in other words, that it is a multiple of 2 and of 3.

    First, note that one of \displaystyle n and \displaystyle (n+1) is even. So \displaystyle n(n+1)(2n+1) is even.

    Next, note that \displaystyle n is either a multiple of 3, in which case there is nothing left to prove; or it leaves a remainder 1 or 2 when divided by 3.

    Case I: \displaystyle n leaves a remainder 1; in which case \displaystyle n = 3m + 1, m \in \mathbb{N}. Therefore
    \displaystyle 2n+1 = 6m + 3
    and is therefore a multiple of 3.

    Case II: \displaystyle n leaves a remainder 2; in which case \displaystyle n = 3m +2, m \in \mathbb{N}. Therefore
    \displaystyle n+1 = 3m + 3
    and is therefore a multiple of 3.

    This concludes the proof.

    Grandad
    Thank u soo much i finally see where i went wrong in my thinking process
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
      \sum\limits^n_{k=0} k^2=\frac{n(n+1)(2n+1)}{6}

    summation of integer( k^2) is integer
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by jess0517 View Post
    I was looking over this problem and im pretty sure you use induction.. but what would your base case be and when subing (k+1) for n, what is the inital formula we want to achieve? I dont exactly know how to approach this problem.

    Attachment 18183
    P(k)

    \frac{1}{3}k^3+\frac{1}{2}k^2}+\frac{1}{6}k is an integer ?

    P(k+1)

    \frac{1}{3}(k+1)^3+\frac{1}{2}(k+1)^2+\frac{1}{6}(  k+1) is also an integer ?

    Try to prove that P(k) being true causes P(k+1) to be true.

    Proof

    \frac{1}{3}(k+1)^3+\frac{1}{2}(k+1)^2+\frac{1}{6}(  k+1)=\frac{1}{3}\left(k^3+3k^2+3k+1\right)+\frac{1  }{2}\left(k^2+2k+1\right)+\frac{1}{6}\left(k+1\rig  ht)

    =\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\  right)+\left(k^2+k+\frac{1}{3}+k+\frac{1}{2}+\frac  {1}{6}\right)

    =\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\  right)+\left(k^2+2k+\frac{2}{6}+\frac{3}{6}+\frac{  1}{6}\right)

    =\left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\  right)+\left(k^2+2k+1\right)

    \left(\frac{1}{3}k^3+\frac{1}{2}k^2+\frac{1}{6}k\r  ight)+\left(k+1)^2

    If k is an integer, so is k+1 and (k+1)(k+1).

    Hence, if P(k) is true, it causes P(k+1) to be true.

    All that remains is to test the proposition P(k) for the first integer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 15th 2010, 07:45 PM
  2. Proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 06:01 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum