Results 1 to 3 of 3

Math Help - Induction with divisibility

  1. #1
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599

    Induction with divisibility

    Define f: (N U {0}) -> N by f(n) = 10^n + 3*4^{n+2}+5 Prove that for all non-negative numbers, n, f(n) is divisible by 9.
    --------------------
    Ok so for this one P(n) is going to be the statement "f(n) is divisible by 9". P(0) holds and we can now assume that this holds true for all j<k.

    This part of induction always gets me, now I have to show P(j) -> P(k), or P(n) -> P(n+1).

    If 9 divides f(j), then there is some number, D, such that 9*D = 10^j + 3*4^{j+2}+5. Now I know there's some way to manipulate this to get what I need but I don't see it.

    Hints?
    Last edited by Jameson; April 28th 2008 at 09:32 AM. Reason: made a stupid mistake
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jameson View Post
    Define f: (N U {0}) -> N by f(n) = 10^n + 3*4^{n+2}+5 Prove that for all non-negative numbers, n, f(n) divides 9.

    --------------------
    Ok so for this one P(n) is going to be the statement "f(n) divides 9". P(0) holds and we can now assume that this holds true for all j<k.

    This part of induction always gets me, now I have to show P(j) -> P(k), or P(n) -> P(n+1).

    If f(j) divides 9, then there is some number, D, such that 9*D = 10^j + 3*4^{j+2}+5. Now I know there's some way to manipulate this to get what I need but I don't see it.

    Hints?
    Hint:
     f(n+1) - f(n) = (10^{n+1} + 3*4^{n+3}+5) - (10^n + 3*4^{n+2}+5)

    \Rightarrow f(n+1) - f(n) = 9(10^n + 4^{n+2})

    But 9|f(n) (by Induction Hypothesis)

    So............

    P.S: It should really be "9 divides f(n)", not vice versa
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by Isomorphism View Post
    Hint:
     f(n+1) - f(n) = (10^{n+1} + 3*4^{n+3}+5) - (10^n + 3*4^{n+2}+5)

    \Rightarrow f(n+1) - f(n) = 9(10^n + 4^{n+2})

    But 9|f(n) (by Induction Hypothesis)

    So............

    P.S: It should really be "9 divides f(n)", not vice versa
    Fixed the mistake. Great idea. I can usually get the proof once I see it, but coming up with that by myself seems like an unlikely event. That hint was exactly what I needed. Thank you again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction - Divisibility
    Posted in the Algebra Forum
    Replies: 11
    Last Post: December 24th 2011, 09:04 PM
  2. Divisibility by 6 Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2011, 04:40 PM
  3. Induction divisibility P1
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2010, 11:20 AM
  4. Induction divisibility P2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2010, 10:22 AM
  5. Prove divisibility by induction
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: July 30th 2008, 01:58 PM

Search Tags


/mathhelpforum @mathhelpforum