# Proof by Induction - Divisibility Proofs

• Sep 20th 2011, 11:50 AM
GrigOrig99
Proof by Induction - Divisibility Proofs
Q. Prove by induction that...

The end result should be divisible by 6, but it hasn't worked out that way for me. Can someone help me spot where I've gone wrong? Thanks.
• Sep 20th 2011, 12:30 PM
ebaines
Re: Proof by Induction - Divisibility Proofs
Your error is in saying that $7^{k+1} + 4^{k+1} + 1 = 7 +4(6Z-1)$ That's incorrect. Try this:

$7^{k+1} + 4^{k+1} + 1 = 7(7^k + 4^k + 1) -3 \cdot 4^k -6$

Note that $3 \cdot 4^k -6$ is divisible by 6. So if $7^{k+1} + 4^{k+1} + 1$ is divisible by 6, then then so is $7^{k+1} + 4^{k+1} + 1$
• Sep 20th 2011, 01:38 PM
GrigOrig99
Re: Proof by Induction - Divisibility Proofs
Thanks, I really appreciate it.
• Sep 20th 2011, 04:29 PM
Soroban
Re: Proof by Induction - Divisibility Proofs
Hello, GrigOrig99!

Quote:

$\text{Prove by induction: }\:7^n + 4^n + 1\,\text{ is divisible by 6 for }n \in N.$

I prefer to do it like this . . .

Verify $S(1)\!:\;\;7^1 + 4^1 + 1 \,=\,12\:\hdots \text{ divisible by 6}$

Assume $S(k)\!:\;\;7^k + 4^k + 1 \:=\:6m\,\text{ for some integer }m.$

Add $6\!\cdot\!7^k + 3\!\cdot\!4^k$ to both sides:

- - . . $7^k + 4^k + 1 + 6\!\cdot\!7^k + 3\!\cdot\!4^k \;=\;6m + 6\!\cdot\!7^k + 3\!\cdot\!4^k$

. . $(7^k + 6\!\cdot\!7^k) + (4^k + 3\!\cdot\!4^k) + 1 \;=\;6m + 6\!\cdot7^k + 3\!\cdot\!(2^2)^k$

- - - . $7^k(6+1) + 4^k(3+1) + 1\;=\;6m + 6\!\cdot\!7^k + 3\!\cdot\!2^{2k}$

. . . . . . . . . . . $7^k\!\cdot\!7 + 4^k\!\cdot\!4 + 1 \;=\;6m +6\!\cdot\!7^k + 3\!\cdot\!2\!\cdot\!2^{2k-1}$

. . . . . . . . . . . $7^{k+1} + 4^{k+1} + 1 \;=\;6m + 6\!\cdot\!7^k + 6\!\cdot\!2^{2k-1}$

. . . . . . . . . . . $7^{k+1} + 4^{k+1} + 1 \;=\;6\bigg[m + 7^k + 2^{2k-1}\bigg]$

And we have proved $S(k+1).$