1. ## 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?

2. Originally Posted by Jameson
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

3. Originally Posted by Isomorphism
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.
The text passage contains a mathematical question related to proving a statement about divisibility using mathematical induction. The question is presented in the form of a proof problem, and hints and a solution approach are provided in the subsequent parts of the text.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
1. ## 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?

2. Originally Posted by Jameson
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

3. Originally Posted by Isomorphism
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.
user
The text passage contains a mathematical question related to proving a statement about divisibility using mathematical induction. The question is presented in the form of a proof problem, and hints and a solution approach are provided in the subsequent parts of the text.

TYPE: SINGLE_QUESTION_WITH_ANSWER