# Thread: Proof by Induction - Divisibility Proofs

1. ## 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.

2. ## 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$

3. ## Re: Proof by Induction - Divisibility Proofs

Thanks, I really appreciate it.

4. ## Re: Proof by Induction - Divisibility Proofs

Hello, GrigOrig99!

$\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).$