Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 5 Marks

Year: May 2014

Step1: Basis of induction

For n=1

We have

$8^n - 3^n = 8-3=5$ is divisible by 5

Step2: Induction step: Assume that $8^k - 3^k$ is divisible by 5. Then we have

$8^{k+1} - 3^{k+1} =8^k.8 -3^k.3 \\ =8^k.(5+3) -3^{k+1} \\ =5(8^k)+3(8^k)- 3^{k+1} \\ =5(8^k)+3(8^k- 3^k)$

Since both forms in this sum are multiples of 5 (the first because it is 5 times an integer and the second by the assumption of the induction step), it follows that $8^{k+1} - 3^{k+1}$ is also multiple of 5. Thus, by the principle of mathematical induction, $8^n — 3^n$ is a multiple of 5.