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
    Hint:
    [itex]4^k=(3+1)^k[/itex]
     
  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

    HallsofIvy

    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

    Mentallic

    User Avatar
    Homework Helper

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

    [tex]3(4^k)[/tex]
    [tex]=3(3+1)^k[/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]

    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

    eumyang

    User Avatar
    Homework Helper

    No, it's not. Mentallic had it right.
    [tex]=3(4)^k[/tex]
    [tex]=3(3+1)^k[/tex]
    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

    Mentallic

    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.
    [tex]\binom{n}{0}=\binom{n}{n}=1[/tex]
    [tex]a^{n-n}=a^0=b^0=1[/tex]
    [tex]a^{n-(n-k)}=a^k[/tex]

    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