Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by mathematical Induction: Divisibility

  1. Oct 23, 2005 #1
    The question is: Prove by mathematical Induction that
    [tex] f(n) \equiv 2^{6n}+3^{2n-2} [/tex] is divisible by 5. This is what I did:
    Suppose that the given statement is true for [tex]n=k[/tex]
    Since the[tex] f(k)[/tex] is divisible by 5,
    [tex]f(k)=5A[/tex] (where A are is a constant.)
    Also, from the given statement:
    [tex] f(k)=2^{6k}+3^{2k-2} [/tex]
    To prove that the given statement is also true for n=k+1:
    [tex] f(k+1)-f(k) [/tex]
    [tex]=2^{6k+6}+3^{2k} - (2^{6k}+3^{2k-2})[/tex]
    [tex]=2^{6k}(63)+3^{2k-2}(8)[/tex]
    After this I'm stuck! I know that I have to write it in the form of [tex]5B[/tex](where B is a constant) but I cant. This is because if I do take 5 common I get fractions in the above expression.
    Thanks in advance for any help.
     
    Last edited: Oct 23, 2005
  2. jcsd
  3. Oct 23, 2005 #2
    You should really start with a specific case. The statement is true for n = 1 since 2^6 + 3^0 = 65 is divisible by 5.
    I find that the easiest approach for this problems is to start with the "n+1" expression where you replace n by n+1 and manipulate the expression to get it into the appropriate form.
    [tex]
    f\left( {n + 1} \right) = 2^{6n + 6} + 3^{2n}
    [/tex]

    We want something with 2^6n or 3^(2n-2). The former is clearly the easier of the two to incorporate into the above expression so try to get that in there first.
    [tex]
    = 2^6 \left( {2^{6n} } \right) + 3^{2n}
    [/tex]

    But you don't just want 2^6n in there somewhere do you? You'd much prefer to have 2^6n + 3^(2n-6) in there as well. So just add a 3^(2n-6) in the parenthesis with the 2^6n. Of course now you'll need to substract the relevant expression to maintain equality. From there it's just algebra, as with many questions of this type.
     
    Last edited: Oct 23, 2005
  4. Oct 24, 2005 #3
    You are almost there!
    Benny is suggesting to use a very powerful solving technique: compare where you are to what result you need to get, and think of what would be nice to have as a stepping stone to close a gap.
    Benny's solution mght be a little shorter, but since you've already come close to solution, let's continue.
    Borrowing Benny's expression, you'd much prefer to see
    [tex]2^{6k}+3^{2k-2}[/tex] in your
    [tex]2^{6k}(63)+3^{2k-2}(8)[/tex].
    Maybe, [tex]c(2^{6k}+3^{2k-2})[/tex], where c is a constant?
    Say, [tex]c=63[/tex] (why?).
    [tex]63(2^{6k}+3^{2k-2})=2^{6k}(63)+3^{2k-2}(63)[/tex].
    It's not your [tex]2^{6k}(63)+3^{2k-2}(8)[/tex] yet, but you can make some adjustments.
    [tex]f(k+1)-f(k)=63(2^{6k}+3^{2k-2})-?=63(5A)-?=5B[/tex]

    Now, I am not sure why you started with
    [tex] f(k+1)-f(k) [/tex].
    You could:
    [tex] f(k+1)=2^{6k+6}+3^{2k}=2^{6k}(64)+3^{2k-2}(9)= 64(2^{6k}+3^{2k-2}) - ? = 64(5A) - ? = 5B[/tex]
     
    Last edited: Oct 24, 2005
  5. Nov 5, 2007 #4
    Good day sir's , ireally want to understand the mathematical induction in your site.I really need your help to accomplish my course for four years.I hope my request wont be denied.Thank you very much
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by mathematical Induction: Divisibility
Loading...