Proof by Induction - Divisibility Proofs

**GrigOrig99** · September 20th 2011, 11:50 AM

Q. Prove by induction that...

Please see attachment.

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.

**ebaines** · September 20th 2011, 12:30 PM

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$

**GrigOrig99** · September 20th 2011, 01:38 PM

Thanks, I really appreciate it.

**Soroban** · September 20th 2011, 04:29 PM

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

Thread: Proof by Induction - Divisibility Proofs

LinkBack

Thread Tools

Display

Proof by Induction - Divisibility Proofs

Re: Proof by Induction - Divisibility Proofs

Re: Proof by Induction - Divisibility Proofs

Re: Proof by Induction - Divisibility Proofs

Similar Math Help Forum Discussions

Proof by Induction - Divisibility Proofs

Induction Proof - Divisibility

Proof by Induction (Divisibility)

Question on the principle of induction. Proof of divisibility

[SOLVED] Proof of divisibility by Induction

Search Tags