Question 773315
use mathematical induction to prove 7^n - 3^n is divisible by 4.
<pre>
It is true for n = 1 since 7<sup>1</sup> - 3<sup>1</sup> = 4 which
is divisible by 4.

We also need to show that it is true for n = 2 (which makes this 
proof a little different from most induction proofs as we will see.)

It is true for n = 2 since 7<sup>2</sup> - 3<sup>2</sup> = 49 - 9 = 40 which is
divisible by 4.

Assume for some k &#8807; 2 , that both 7<sup>k</sup> - 3<sup>k</sup> and 7<sup>k-1</sup> - 3<sup>k-1</sup> are divisible
by 4.  Therefore there exist integers p,q such that 

(A)   7<sup>k</sup> - 3<sup>k</sup> = 4p and 
(B)   7<sup>k-1</sup> - 3<sup>k-1</sup> = 4q

Multiply the left side of (A) by (7 + 3) and the right side by 10

(7 + 3)(7<sup>k</sup> - 3<sup>k</sup>) = 40p

FOIL the left side

7<sup>k+1</sup> - 7·3<sup>k</sup> + 3·7<sup>k</sup> - 3<sup>k+1</sup> = 40p

Factor 7·3 out of the two middle terms on the left:

7<sup>k+1</sup> + 7·3(-3<sup>k-1</sup> + 7<sup>k-1</sup>) - 3<sup>k+1</sup> = 40p

Reverse the terms inside the parentheses:

7<sup>k+1</sup> + 7·3(7<sup>k-1</sup> - 3<sup>k-1</sup>) - 3<sup>k+1</sup> = 40p

By (B) above we can replace the parentheses by 4q

7<sup>k+1</sup> + 7·3(4q) - 3<sup>k+1</sup> = 40p

7<sup>k+1</sup> + 84q - 3<sup>k+1</sup> = 40p

Rearrange the equation:

7<sup>k+1</sup> - 3<sup>k+1</sup> = 40p - 84q

7<sup>k+1</sup> - 3<sup>k+1</sup> = 4(10p - 21)q

The right side is divisible by 4, and therefore so is the left side.

QED

Edwin</pre>