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!

Prove divisibility, mathematical induction

  1. Nov 6, 2016 #1
    I'm still learning English, had to use dictionary and translator, so I'm sorry if its unclear, i will try to explain it more if needed.

    1. The problem statement, all variables and given/known data
    For n belonging to N when n is even and n > 3, prove that
    (4^(n-3) + 5^(n-3) + 9) is divisible by 9

    2. Relevant equations
    3. The attempt at a solution

    P(n) = 4^(n-3) + 5^(n-3)+9
    for n = 4 :
    P(4) = 4^1 + 5^1 + 9 = 18, divisible by 9

    Now assume that n=k, P(k) = 4^(k-3) + 5^(k-3)+9 is div by 9, then solve it for P(k+2) = 4^(k-1) + 5^(k-1)+9

    And here is the problem, i know that i should use assumption from n=k, but i really don't know how. I have problem with rearranging things to involve it...this is what i tried to use somehow, but always get stuck without any clear step forward
    4^(k-3) + 5^(k-3)+9 = 4^(-2)*4^(k-1)+5^(-2)*5^(k-1)+9 = 9m
    Somehow i wanted to get that (k-1) exponent from it, but i cant deal with multipliers there
     
  2. jcsd
  3. Nov 6, 2016 #2
    You should be working the other way around: try to rewrite P(k+2) in terms of quantities that you know are divisible by ##9##. Here's a good starting point: ##4^{k-1} + 5^{k-1} = 16\left(4^{k-3}\right) + 25 \left(5^{k-3}\right)##
    and note that by our inductive hypothesis, ##4^{k-3} + 5^{k-3}## is divisible by ##9##.
     
  4. Nov 6, 2016 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    First, the question seems strange, as the ##+9## isn't doing anything and why start with ##n = 4## then use ##n-3##? Why not just start with ##n = 1## and prove it for odd ##n##?

    Anyway, have you thought of using ##mod \ 9##?
     
  5. Nov 6, 2016 #4
    The task is more complicated, at start i had a story about hero who fights a hydra, and each "round" he cut off all her heads, except black, and after that more heads of different colours grow up. Long story short, after little programming and some assuming i made this formula and domain of a function myself. 9 is number of black heads that can not be cut down, and i start at n = 4 because its first round when number of head is divisible by 9
     
  6. Nov 6, 2016 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, perhaps don't worry about that! See post #2.
     
  7. Nov 6, 2016 #6
    Hypotesis is that 4k−3+5k−3 + 9 is div by 9, so i want to ask, is it mathematicaly correct to assume that (number divisible by 9) + 9 is still divisible by 9? I know it might sound stupid, but our math proffesor is really...i can't find a word for it, just if i do any little mistake or something which is ilogical, i will be eaten alive.
    And if yes, can i just write it without that 9? Or should i point it out somehow. Thanks for starting point anyway, I think I'm getting it now.
     
  8. Nov 6, 2016 #7
    There is no need to assume - it is a given fact (that if you want to be rigorous, follows from division being right-distributive over addition and subtraction i.e. ##(a+b)/c = a/c + b/c##). Just let (number divisible by 9) be some integer multiple ##\lambda## of 9 and clearly adding 9 to it results in a multiple of 9.
     
  9. Nov 6, 2016 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If a number is divisible by ##9## and you add or subtract ##9## then the result is divisible by ##9##.

    A useful way to express divisibility - in this case by ##9## - is:

    ##n## is divisible by ##9## if and only if ##n = 9k## for some integer ##k##

    You could use this to prove the statement above formally.
     
  10. Nov 6, 2016 #9
    Thank you, both of you really helped me to solve this, now i just add some small details and homework is complete :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove divisibility, mathematical induction
Loading...