Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 5 Marks

Year: Dec 2015

Step1: Basis of induction

For n=1

We have

$6^{n+2} + 7^{2n+1} = 6^3 + 7^3 =559$ is divisible by 43

Step2: Induction step: Assume that $6^{k+2} - 7^{2k+1}$ is divisible by 43. Then we have

$6^{k+3} - 7^{2k+2}$ $=6^{k+2}. 6 -7^{2k+2} \\ =6^{k+2}.(14-7) -7^{2k+2} \\ =14(6^{k+2})-7(6^{k+2})- 7^{2k+2} \\ =14(6^{k+2})-7(6^{k+2}+ 7^{2k+1})$

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