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

Let $\displaystyle 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 $\displaystyle S(0)$ is true since

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

Now, we assume that $\displaystyle S(k)$ is true for some integer $k\geq 0$ and show that $\displaystyle S(k+1)$ is true. When $\displaystyle 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 $\displaystyle S(k+1)$ is true, we then notice that

${\begin{aligned}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{aligned}}$

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