Results 1 to 7 of 7

Math Help - Proof by induction: 4^n + 6n + 8 is divisible by 9.

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    3

    Proof by induction: 4^n + 6n + 8 is divisible by 9.

    Question:
    Prove by induction that 4^n + 6n + 8 is divisible by 9 for all positive integers n.

    My attempted solution:

    for n = 1
    4^n + 6n + 8 = 4 + 6 + 8 = 18 = 9.2

    so is divisible by 9 for n = 1.

    Suppose true for n = k, k is a natural number
    then 4^k + 6k + 8 = 9p, where p is an integer.

    Consider when n = k + 1
    then we have
    4^(k + 1) + 6(k + 1) + 8
    = 4.4^k + 6k + 6 + 8
    = 3.4^k + 4^k + 6k + 8 + 6
    = 3.4^k + 6 + 9p

    Which can easily be shown to be divisible by 3 but not so easily for 9.

    Any help/advice would be greatly appreciated.

    Apologies for not using LATEX - it's been a few years since I used it and I couldn't make it work properly.
    Last edited by mr fantastic; April 19th 2011 at 04:02 PM. Reason: Title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,817
    Thanks
    316
    Awards
    1
    Quote Originally Posted by MrT83 View Post
    Question:
    Prove by induction that 4^n + 6n + 8 is divisible by 9 for all positive integers n.

    My attempted solution:

    for n = 1
    4^n + 6n + 8 = 4 + 6 + 8 = 18 = 9.2

    so is divisible by 9 for n = 1.

    Suppose true for n = k, k is a natural number
    then 4^k + 6k + 8 = 9p, where p is an integer.

    Consider when n = k + 1
    then we have
    4^(k + 1) + 6(k + 1) + 8
    = 4.4^k + 6k + 6 + 8
    = 3.4^k + 4^k + 6k + 8 + 6
    = 3.4^k + 6 + 9p

    Which can easily be shown to be divisible by 3 but not so easily for 9.

    Any help/advice would be greatly appreciated.

    Apologies for not using LATEX - it's been a few years since I used it and I couldn't make it work properly.
    Hint: Expand 3*4^k = 3*(3 + 1)^k via the binomial theorem. Each term is divisible by 9 except for the last one 3*1 = 3. But you have that 6 to add to it...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    A solution would be to show using induction that 4^k+2 is divisible by 3.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by MrT83 View Post
    Question:
    Prove by induction that 4^n + 6n + 8 is divisible by 9 for all positive integers n.
    Suppose that 4^K +6k +8 is divisible by 9.

    Look at 4^{K+1}+6(K+1)+8=4(4^K+6K+8)-18K-18.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by MrT83 View Post
    Question:
    Prove by induction that 4^n + 6n + 8 is divisible by 9 for all positive integers n.

    My attempted solution:

    for n = 1
    4^n + 6n + 8 = 4 + 6 + 8 = 18 = 9.2

    so is divisible by 9 for n = 1.

    Suppose true for n = k, k is a natural number
    then 4^k + 6k + 8 = 9p, where p is an integer.

    Consider when n = k + 1
    then we have
    4^(k + 1) + 6(k + 1) + 8
    = 4.4^k + 6k + 6 + 8
    = 3.4^k + 4^k + 6k + 8 + 6
    = 3.4^k + 6 + 9p

    Which can easily be shown to be divisible by 3 but not so easily for 9.

    Any help/advice would be greatly appreciated.

    Apologies for not using LATEX - it's been a few years since I used it and I couldn't make it work properly.
    You could also use Induction over 2 stages...

    (4)4^k+6k+6+8 is

    (4^k+6k+8)+(3)4^k+6

    You want to prove now that (3)4^k+6 is a multiple of 9

    which is that 4^k+2 is a multiple of 3 hopefully.

    Use Induction again on that....

    4+2=6 is the base case.

    P(k+1) second time around is (4)4^k+2 = (4^k+2)+(3)4^k

    and this is certainly a multiple of 3 if 4^k+2 is.... QED



    EDIT: Sorry, I hadn't spotted post 3.

    Plato's method really is excellent.

    If 4^k+6k+8 is divisible by 9

    then 4(4^k+6k+8) will also be divisible by 9, from which the P(k+1) proposition can be extracted.
    Last edited by Archie Meade; April 20th 2011 at 04:04 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,659
    Thanks
    600
    Hello, MrT83!

    I have yet another approach . . .


    You have: .9p + 3(4^k) + 6 .= .3(3p + 4^k + 2)


    We must show that .3p + 4^k + 2 .is a multiple of 3,

    . . that is, that .4^k + 2 .is a multiple of 3.


    4^k + 2 .= .(2^2)^k + 2 ,= .2^{2k} + 2 .= .2(2^{2k-1} + 1)


    The expression, 2^{2k-1} + 1, is one more than an odd power of 2.


    Recall that, for odd n:

    . . 2^n + 1 .= .(2 + 1)*(2^{n-1} - 2^{n-2} + 2^{n-3} - . . . - 2 + 1)


    Q. E. D.

    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Have you seriously considered reply #4?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by induction 5^n-1 is divisible by 4
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2011, 09:54 AM
  2. Replies: 8
    Last Post: July 3rd 2011, 03:55 PM
  3. Replies: 5
    Last Post: November 14th 2009, 03:20 AM
  4. divisible by 11 proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2008, 08:49 AM
  5. [SOLVED] [SOLVED] Proof divisible by 64
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 22nd 2005, 05:12 AM

Search Tags


/mathhelpforum @mathhelpforum