Question

using induction, prove that 10n + 3.4n+2 + 5 is divisible by 9

Answer 1

☆☆ranshsangwan☆☆


For n = 0, we have: 

10^n + 3 * 4^(n + 2) + 5 
= 10^0 + 3 * 4^(0 + 2) + 5 
= 54 

which is divisible by 9. Thus, it works at least for n = 0. Suppose it works for some n = k .That is, the expression: 

10^k + 3 * 4^(k + 2) + 5 

is divisible by 9, i.e. there exists some M such that: 

10^k + 3 * 4^(k + 2) + 5 = 9M 

Then, consider the n = k + 1 case: 

10^(k + 1) + 3 * 4^(k + 3) + 5 
= 10 * 10^k + 12 * 4^(k + 2) + 5 

We need to find the expression 10^k + 3 * 4^(k + 2) + 5 in there. This is always the hardest part of these proofs. Basically, what happens is we choose one of these terms and try to pull out as many copies of 10^k + 3 * 4^(k + 2) + 5 out of it as possible. I'm going to pick the 12 * 4^(k + 2) term. There are 4 copies of the 3 * 4^(k + 3) term in there, so lets pull out 4 copies of 10^k + 3 * 4^(k + 2) + 5 from the entire expression: 

10 * 10^k + 12 * 4^(k + 2) + 5 
= 4 * 10^k + 4 * 3 * 4^(k + 2) + 4 * 5 + 6 * 10^k - 15 
= 4 * (10^k + 3 * 4^(k + 2) + 5) + 6 * 10^k - 15 
= 4 * 9M + 6 * 10^k - 15 

Notice now that 4 * 9M is divisible by 9. We just need to show 6 * 10^k - 15 is divisible by 9. We can take out a factor of 3, and we can therefore see that we need to show that: 

2 * 10^k - 5 

is divisible by 3 for k >= 0. If k = 0, then it certainly is divisible by 3. If k > 0, then: 

2 * 10^k - 5 
= 20 * 10^(k - 1) - 5 
= 5(4 * 10^(k - 1) - 1) 

Now, notice that: 

10 = 1 (mod 3) 
===> 10^(k - 1) = 1^(k - 1) = 1 (mod 3) 
===> 4 * 10^(k - 1) - 1 = 4 * 1 - 1 = 3 = 0 (mod 3)
===> 5 * (4 * 10^(k - 1) - 1) = 5 * 0 = 0 (mod 3) 

If you don't like modulo arithmetic, the above can be proven by a separate induction argument. Thus 2 * 10^k - 5 is divisible by 3, as we needed. Therefore: 

10^(k + 1) + 3 * 4^(k + 3) + 5 = 4 * 9M + 6 * 10^k - 15 

is divisible by 9, and so 10^n + 3 * 4^(n + 2) + 5 is divisible by 9 for all n.