Thread: Induction with divisibility

Define f: (N U {0}) -> N by 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 . Now I know there's some way to manipulate this to get what I need but I don't see it.

Hints?

Originally Posted by Jameson

Define f: (N U {0}) -> N by 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 . Now I know there's some way to manipulate this to get what I need but I don't see it.

Hints?

Hint:




But (by Induction Hypothesis)

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

P.S: It should really be "9 divides f(n)", not vice versa

Originally Posted by Isomorphism

Hint:




But (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.