Results 1 to 4 of 4

Math Help - yet another Mathematical Induction question

  1. #1
    Newbie
    Joined
    Apr 2006
    From
    Sydney Australia
    Posts
    14

    yet another Mathematical Induction question

    Prove by mathematical Induction
    If two numbers are divisible by 3 then their sum is divisible by 6
    Any help is appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by delpin View Post
    Prove by mathematical Induction
    If two numbers are divisible by 3 then their sum is divisible by 6
    Any help is appreciated
    First a base case:

    If a and b are two numbers less than 1 both divisible by 3 then their sum
    is divisible by 3, since they are both zero.

    Now suppose that for some k>1 that for all pairs of integers

    (a,b; 3|a, 3|b, a<=k, b<=k)

    implies that 3|(a+b)

    Now consider a pair of (u,v;3|u, 3|v, u<=k+1, v<=k+1),

    then if u<=k and v<=k; 3|(u+v) by supposition.

    If k<u<=k+1, v<=k, then u=u'+3, u'<k, and so 3|(u'+v) which implies 3|(u+v)

    If u<=k, k<v<=k+1, then v=v'+3, v'<k, and so 3|(u+v') which implies 3|(u+v)

    If k<u<=k+1, k<v<=k+1, then u=u'+3, u'<k, and v=v'+3, v'<k, and so 3|(u'+v') which implies 3|(u+v)

    So if for some k>1 that for all pairs of integers (a,b; 3|a, 3|b, a<=k, b<=k) implies that 3|(a+b), then for all pairs of integers (a,b; 3|a, 3|b, a<=k+1, b<=k+1) implies that 3|(a+b). Which with the base case proves by induction
    that:

    If a and b are two numbers both divisible by 3 then their sum
    is divisible by 3

    This could probably be made neater by taking n=3 for the base case, and steping from
    k to k+3 in the inductive step.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, delpin!

    Is there a typo?
    . . The statement isn't true . . .


    Prove by mathematical induction:
    . . If two numbers are divisible by 3, then their sum is divisible by 6.

    Counter-example: .6 and 9 are divisible by 3,
    . . but 6 + 9 \:=\:15 is not divisible by 6.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    First a base case:

    If a and b are two numbers less than 1 both divisible by 3 then their sum
    is divisible by 3, since they are both zero.

    Now suppose that for some k>1 that for all pairs of integers

    (a,b; 3|a, 3|b, a<=k, b<=k)

    implies that 3|(a+b)

    Now consider a pair of (u,v;3|u, 3|v, u<=k+1, v<=k+1),

    then if u<=k and v<=k; 3|(u+v) by supposition.

    If k<u<=k+1, v<=k, then u=u'+3, u'<k, and so 3|(u'+v) which implies 3|(u+v)

    If u<=k, k<v<=k+1, then v=v'+3, v'<k, and so 3|(u+v') which implies 3|(u+v)

    If k<u<=k+1, k<v<=k+1, then u=u'+3, u'<k, and v=v'+3, v'<k, and so 3|(u'+v') which implies 3|(u+v)

    So if for some k>1 that for all pairs of integers (a,b; 3|a, 3|b, a<=k, b<=k) implies that 3|(a+b), then for all pairs of integers (a,b; 3|a, 3|b, a<=k+1, b<=k+1) implies that 3|(a+b). Which with the base case proves by induction
    that:

    If a and b are two numbers both divisible by 3 then their sum
    is divisible by 3

    This could probably be made neater by taking n=3 for the base case, and steping from
    k to k+3 in the inductive step.

    RonL
    Oppsss.. misread the problem, then went and proved something that was
    true even though more easiy proven by other methods.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 4th 2011, 06:30 PM
  2. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 29th 2010, 11:31 AM
  3. Mathematical Induction question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 26th 2009, 08:05 PM
  4. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 24th 2008, 05:11 AM
  5. Mathematical Induction Question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 23rd 2008, 10:40 PM

Search Tags


/mathhelpforum @mathhelpforum