Induction: Prove 6(7^n) - 2(3^n) is div. by 4 for n>=1

[solomon_13000]

I am having problems understanding the next step in my solution.


6 x 7 power n - 2 x 3 power n divisible 4 where n >= 1

Assume n = p
the next step is n = p + 1

solution:

6 x 7 power (p+1) - 2 x 3 power (p+1)
6 x 7 power p x 7 power 1 - 2 x 3 power p x 3 power 1
42 x 7 power p - 6 x 3 power p

now the next step is:

(24 + 18)7 power p - 3(2 x 3 power p)
24 x 7 power p + 18 x 7 power p - 6 x 3 power p
24 x 7 power p + 3(6 x 7 power p - 2 x 3 power p) - final solution


How is the next step achieved?

Regards.[/img][/code]

 

[pka]

Did you first prove it is true for n=1?
If it is true for P>1 then show it is true for P+1.

If 4 divides \(\displaystyle \left[ {6\left( {7^P } \right) - 2\left( {3^P } \right)} \right]\) then consider:
\(\displaystyle \begin{array}{rcl}
\left[ {6\left( {7^{P + 1} } \right) - 2\left( {3^{P + 1} } \right)} \right] & = & \left[ {6\left( {7^{P + 1} } \right) - \left( 7 \right)\left( 2 \right)\left( {3^P } \right) + \left( 7 \right)\left( 2 \right)\left( {3^P } \right) - 2\left( {3^{P + 1} } \right)} \right] \\
& = & 7\left[ {6\left( {7^P } \right) - \left( 2 \right)\left( {3^P } \right)} \right] - \left( 2 \right)\left( {3^P } \right)\left[ {\left( 7 \right) - \left( 3 \right)} \right] \\
\end{array}\).

Do you see how to finish.

 

[solomon_13000]

I was told to prove this way:

p = 1

24 x 7 power p = 168/4

3(6 x 7 power p - 2 x 3 power p) = 108/4

which is true.

 

[pka]

I was told to prove this way:

p = 1

24 x 7 power p = 168/4

3(6 x 7 power p - 2 x 3 power p) = 108/4

which is true.

Good. Now finish it off.
Assume it is true for n=P and show it is true for P+1.

 

[solomon_13000]

But under what condition did 42 x 7 power p was broken down into (24 + 18)7 power p?

 

[pka]

But under what condition did 42 x 7 power p was broken down into (24 + 18)7 power p?

May I ask: What are you talking about?
Do you understand induction proofs?

It is true for p=1: 6(7)-2(3)=36.
If we KNOW that it is true for p the based on that show it is true for p+1.
Now I have given all the steps above. Now use them.

 

[solomon_13000]

I manage to figure it out. Thanks for the hint.

 

[soroban]

Re: Induction: Prove 6(7^n) - 2(3^n) is div. by 4 for n>=

Hello, solomon_13000!

You used some Olympic-level gymnastics . . . great work!
. . I'll modify your proof to my "language".

Prove: \(\displaystyle \:6\cdot7^n\,-\,2\cdot3^n\) is divisible 4 for \(\displaystyle n\,\geq\,1\)

Verify \(\displaystyle S(1):\;6\cdot7^1\,-\,2\cdot3^1\:=\:42\,-\,6\:=\:36\) ... yes, divisible by 4.

Assume \(\displaystyle S(k):\;6\cdot7^k\,-\,2\cdot3^k\) is divisible by 4.

We want to prove: \(\displaystyle \;6\cdot7^{k+1}\,-\,2\cdot3^{k+1}\) is divislble by 4.


We have: \(\displaystyle \:6\cdot7^{k+1}\,-\,2\cdot3^{k+1}\)

. . \(\displaystyle =\:6\cdot7^k\cdot7\,-\,2\cdot3^k\cdot3\)

. . \(\displaystyle = \:42\cdot7^k\,-\,6\cdot3^k\)

. . \(\displaystyle =\24\,+\,18)\cdot7^k\,-\,3(2\cdot3^k)\)

. . \(\displaystyle = \:24\cdot7^k\,+\,18\cdot7^k\,-\,6\cdot3^k\)

. . \(\displaystyle = \:\underbrace{24\cdot7^k}\,+\,3\underbrace{(6\cdot7^k\,-\,2\cdot3^k)}\)
. = . . . \(\displaystyle \uparrow\) . . . . - . . .\(\displaystyle \uparrow\)
. . . div. by 4 . . \(\displaystyle S(k)\) says this is div. by 4


Therefore: \(\displaystyle \:6\cdot7^{k+1}\,-\,2\cdot3^{k+1}\) is divisible by 4.
. . The induction proof is complete.