Prove that 9 is a factor of...

• April 9th 2011, 04:13 PM
mushroom
Prove that 9 is a factor of...
Prove that 9 is a factor of:
P(n): $10^(^n^+^1^) + 3 * 10^n + 5$ for all positive integer n

Using the induction method,
I have proven P(1) to be true

P(k): $10^k (10+3) + 5 = 9a$
P(k+1): $10^(^k^+^1^) (10+3) + 5 = ?$

How do I continue? I am new at doing proofs (Worried)
• April 9th 2011, 04:31 PM
LoblawsLawBlog
Do you have to use induction? Sometimes that's tedious for problems like this. I would try to rewrite 10 as 9+1 and then use the binomial theorem.
• April 9th 2011, 04:33 PM
mushroom
Yes, unfortunately it is required to use the induction method.
• April 9th 2011, 05:54 PM
topsquark
Quote:

Originally Posted by mushroom
Prove that 9 is a factor of:
P(n): $10^(^n^+^1^) + 3 * 10^n + 5$ for all positive integer n

Using the induction method,
I have proven P(1) to be true

P(k): $10^k (10+3) + 5 = 9a$
P(k+1): $10^(^k^+^1^) (10+3) + 5 = ?$

How do I continue? I am new at doing proofs (Worried)

$10^{k + 1} (10 + 3) + 5$

$= 10 \cdot 10^k (10 + 3) + 5$

Now use the P(k) step in the form of $10^k(10 + 3) = 9a - 5$
$= 10 (9a - 5) + 5$

And I'm sure you can take it from here.

-Dan
• April 9th 2011, 08:49 PM
Soroban
Hello, mushroom!

Quote:

$\text{Prove that 9 is a factor of: }\:10^{n+1} + 3\!\cdot\!10^n + 5\,\text{ for all positive integers }n$

$\text{Verify }S(1)\!:\; 10^2 + 3\!\cdot10 + 5 \:=\:135,\,\text{ a multiple of 9 . . . True!}$

$\text{Assume }S(k)\!:\;10^{k+1} + 3\!\cdot\!10^k + 5 \:=\:9a\,\text{ for some integer }a$

$\text{Add }(9\!\cdot\!10^{k+1} + 27\!\cdot\!10^k)\,\text{ to both sides:}$

. . $10^{k+1} + {\bf9\!\cdot\!10^{k+1}} + 3\!\cdot\!10^k + {\bf27\!\cdot\!10^k} + 5 \;=\;9a + {\bf9\!\cdot\!10^{k+1}} + {\bf27\!\cdot\!10^k}$

. . . . . . . . $10^{k+1}(1 + 9) + 3\!\cdot\!10^k(1+9) + 5 \;=\;9a + 9\!\cdot\!10^{k+1} + 27\!\cdot\!10^k$

. . . . . . . . . . . . $10^{k+1}\cdot 10 + 3\!\cdot\!10^k\!\cdot\!10 + 5 \;=\;9\left(a + 10^{k+1} + 3\!\cdot\!10^k\right)$

. . . . . . . . . . . . . . . . $10^{k+2} + 3\!\cdot\!10^{k+1} + 5 \;=\;\underbrace{9\left(a + 10^{k+1} + 3\!\cdot\!10^k\right)}_{\text{a multiple of 9}}$

We have proved statement $S(k+1).$

The inductive proof is complete.