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!

Homework Help: Mathematical induction

  1. Jul 26, 2012 #1
    Prove that f(n) = 4^n + 6n - 1 is divisible by 9 for all positive integers of n.

    I've proved this by considering that f(k) is divisible by 9, i.e f(k) = 4^k + 6k -1 = 9m where m is some integer. Rearranging to give 4^k = 9m - 4k + 1 and then considering f(k+1) = 4^(k+1) + 6(k+1) - 1 then substituting 4^k and showing it is divisible by 9, which works.

    I've been trying to do it another way i.e by considering f(k+1) - f(k), doing so I get

    [itex] f(k+1) -f(k) = 4^{k+1} + 6k + 6 -1 -4^k -6k + 1 [/itex]
    and then going on to get [itex] f(k+1) -f(k)= 3(4^k) + 6 [/itex]

    however i'm stuck here, I can obviously see that this is divisible by 9, but how can I show it?

    EDIT: Similarly how do I show that 120(2^(4k)) + 78(3^(3k)) is divisible by 11?
    Last edited: Jul 26, 2012
  2. jcsd
  3. Jul 26, 2012 #2
  4. Jul 26, 2012 #3
    I still can't seem to get it, i've expanded with the binomial expansion.
  5. Jul 26, 2012 #4


    User Avatar
    Science Advisor

    First, of course, [itex]f(0)= 4^0+ 6(0)- 1= 0= 9(0)[/itex].

    Now assume that, for some k, [itex]f(k)= 4^k+ 6k- 1[/itex] is a multiple of 9 and look at
    [itex]f(k+ 1)= 4^{k+1}+ 6(k+ 1)- 1= 4(4^k)+ 6k+ 5[/itex].

    Looking at that 4 times [itex]4^k[/itex], it occcurs to me to write 6k= 24k- 18k= 4(6k)- 18k and 5= -4+ 9.

    Do you see why?
    [itex]f(k+1)= 4^{k+1}- 6(k+1)- 1= 4(4^k+ 6k- 1)- 18k+ 9[/itex]
    Last edited by a moderator: Jul 27, 2012
  6. Jul 26, 2012 #5
    woah that's pretty smart, though I don't particularly think I could get to that step on my own.
  7. Jul 27, 2012 #6
    [itex]3\cdot (3+1)^k+6=3\cdot\sum_{m=0}^k {k\choose m}3^m+6=3\cdot \sum_{m=1}^k {k\choose m}3^m+3+6=9\cdot \sum_{m=1}^k {k\choose m}3^{m-1}+9[/itex]
  8. Jul 30, 2012 #7
    I'm not really familiar on your notation, heres how I expanded:

    [itex]3(3^k + \displaystyle \binom{k}{1}3^{k-1} + \displaystyle \binom{k}{2}3^{k-2}+...)[/itex]
  9. Jul 30, 2012 #8


    User Avatar
    Homework Helper

    Right, and what happens at the end of that expansion? It comes down to,

    [tex]=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3+1\right)[/tex]
    [tex]=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k-1}3\right)+3[/tex]

    Can you carry on from here?
  10. Jul 30, 2012 #9
    No, I can't.

    I thought the last term would be [tex]=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k}3\right)+3[/tex]

    I don't know how to proceed either way.
  11. Jul 30, 2012 #10


    User Avatar
    Homework Helper

    No, it's not. Mentallic had it right.
    I'll insert a step here:
    [tex]=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3^1+\displaystyle \binom{k}{k}3^0\right)[/tex]
    [tex]=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3+1\right)[/tex]
    [tex]=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k-1}3\right)+3[/tex]
  12. Jul 30, 2012 #11


    User Avatar
    Homework Helper

    The binomial expansion is as follows:

    [tex](a+b)^n=\sum_{k=0}^n \binom{n}{k}a^{n-k}b^k[/tex]

    Or if we express that sum the long way, we get

    [tex]\binom{n}{0}a^{n-0}b^0+\binom{n}{1}a^{n-1}b^1+\binom{n}{2}a^{n-2}b^2+ .... +\binom{n}{n-2}a^{n-(n-2)}b^{n-2}+\binom{n}{n-1}a^{n-(n-1)}b^{n-1}+\binom{n}{n}a^{n-n}b^{n}[/tex]

    Now, there's a lot of simplifications we can do on the very left and right-hand sides.

    After applying all these simplifications, the binomial expansion becomes
    [tex]a^n+\binom{n}{1}a^{n-1}b+\binom{n}{2}a^{n-2}b^2+ .... +\binom{n}{n-2}a^2b^{n-2}+\binom{n}{n-1} ab^{n-1}+b^n[/tex]

    Applying a=3 and b=1 gives us something much simpler because all of the b terms essentially vanish since bk=1.

    [tex]3^n+\binom{n}{1} 3^{n-1}+\binom{n}{2}3^{n-2}+ .... +\binom{n}{n-2}3^2+\binom{n}{n-1}3+1[/tex]

    Now multiply the whole expression by 3, and remove the +1 term from the sum out of the brackets.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook