Science:Math Exam Resources/Courses/MATH220/December 2011/Question 06 (b)/Solution 1

First, we prove the claim true when $n = 1$ . In this case,

1 2^{2 n - 1} + 1 1^{n + 1} = 1 2^{2 (1) - 1} + 1 1^{1 + 1} = 12 + 121 = 133

which is clearly divisible by 133. We assume the claim is true for $n = k$ . For $n = k + 1$ , we have

\begin{aligned} 1 2^{2 (k + 1) - 1} + 1 1^{(k + 1) + 1} & = 1 2^{2 k + 1} + 1 1^{k + 2} \\ = 1 2^{2} \cdot 1 2^{2 k - 1} + 11 \cdot 1 1^{k + 1} \\ = 144 \cdot 1 2^{2 k - 1} + 11 \cdot 1 1^{k + 1} \\ = (133 + 11) 1 2^{2 k - 1} + 11 \cdot 1 1^{k + 1} \\ = 133 \cdot 1 2^{2 k - 1} + 11 \cdot 1 2^{2 k - 1} + 11 \cdot 1 1^{k + 1} \\ = 133 \cdot 1 2^{2 k - 1} + 11 (1 2^{2 k - 1} + 1 1^{k + 1}) \end{aligned}

Now, in the last line, the first summand is divisible by 133 and the second summand is also divisible by 133 by the induction hypothesis. Hence we must have that $1 2^{2 (k + 1) - 1} + 1 1^{(k + 1) + 1}$ is divisible by 133 as required.