Science:Math Exam Resources/Courses/MATH220/December 2009/Question 05 (b)/Solution 1

Let $S(n)$ be the statement that

$5^n+2(11^n)$

is a multiple of 3. We prove this statement is true for all nonnegative integers $n$ using mathematical induction. Notice that $S(0)$ is true since

$5^0+2(11^0)=1+2(1)=3=3(1).$

Now, we assume that $S(k)$ is true for some integer $k\ge 0$ and show that $S(k+1)$ is true. When $n=k+1$, we can start with the induction hypothesis

$5^k+2(11^k)=3m.$

for some integer $m$. The induction hypothesis is equivalent to $5^k=3m-2(11^k)$. To see that $S(k+1)$ is true, we then notice that

$\begin{array}{rl}{5}^{k+1}+2(11^{k+1})& =5(5^k)+2(11^{k+1})\\ & =5(3m-2(11^k))+2(11^{k+1})\\ & =15m-10(11^k)+22(11^k)\\ & =15m+12(11^k)\\ & =3(5m+4(11^k)),\end{array}$

which shows that $S(k+1)$ is true. Hence $S(n)$ is true for all nonnegative integers $n$ by the principle of mathematical induction.