Question:
Prove by induction that 4^n + 6n + 8 is divisible by 9 for all positive integers n.
My attempted solution:
for n = 1
4^n + 6n + 8 = 4 + 6 + 8 = 18 = 9.2
so is divisible by 9 for n = 1.
Suppose true for n = k, k is a natural number
then 4^k + 6k + 8 = 9p, where p is an integer.
Consider when n = k + 1
then we have
4^(k + 1) + 6(k + 1) + 8
= 4.4^k + 6k + 6 + 8
= 3.4^k + 4^k + 6k + 8 + 6
= 3.4^k + 6 + 9p
Which can easily be shown to be divisible by 3 but not so easily for 9.
Any help/advice would be greatly appreciated.
Apologies for not using LATEX - it's been a few years since I used it and I couldn't make it work properly.
You could also use Induction over 2 stages...
(4)4^k+6k+6+8 is
(4^k+6k+8)+(3)4^k+6
You want to prove now that (3)4^k+6 is a multiple of 9
which is that 4^k+2 is a multiple of 3 hopefully.
Use Induction again on that....
4+2=6 is the base case.
P(k+1) second time around is (4)4^k+2 = (4^k+2)+(3)4^k
and this is certainly a multiple of 3 if 4^k+2 is.... QED
EDIT: Sorry, I hadn't spotted post 3.
Plato's method really is excellent.
If 4^k+6k+8 is divisible by 9
then 4(4^k+6k+8) will also be divisible by 9, from which the P(k+1) proposition can be extracted.
Hello, MrT83!
I have yet another approach . . .
You have: .9p + 3(4^k) + 6 .= .3(3p + 4^k + 2)
We must show that .3p + 4^k + 2 .is a multiple of 3,
. . that is, that .4^k + 2 .is a multiple of 3.
4^k + 2 .= .(2^2)^k + 2 ,= .2^{2k} + 2 .= .2(2^{2k-1} + 1)
The expression, 2^{2k-1} + 1, is one more than an odd power of 2.
Recall that, for odd n:
. . 2^n + 1 .= .(2 + 1)*(2^{n-1} - 2^{n-2} + 2^{n-3} - . . . - 2 + 1)
Q. E. D.