Thread: Proof by induction: 4^n + 6n + 8 is divisible by 9.

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.

Originally Posted by MrT83

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.

Hint: Expand 3*4^k = 3*(3 + 1)^k via the binomial theorem. Each term is divisible by 9 except for the last one 3*1 = 3. But you have that 6 to add to it...

-Dan

A solution would be to show using induction that 4^k+2 is divisible by 3.

Originally Posted by MrT83

Question:
Prove by induction that 4^n + 6n + 8 is divisible by 9 for all positive integers n.

Suppose that 4^K +6k +8 is divisible by 9.

Look at 4^{K+1}+6(K+1)+8=4(4^K+6K+8)-18K-18.

Originally Posted by MrT83

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.

Have you seriously considered reply #4?