If you find any mistakes, please make a comment! Thank you.

Using the principle of mathematical induction to show divisibility I


Solution: The $n$-th proposition is
$$
P_n: \quad 7 \text{ divides } 11^n-4^n.
$$ Clearly, $P_1$ is true because $11^1-4^1$ is exactly 7. We have the induction basis.

Now we assume $P_n$ is true, that is $7$ divides $11^n-4^n$. We would like to show $P_{n+1}$ is true based on $P_n$. Note that we have
\begin{align*}
11^{n+1}-4^{n+1}=&\ 11^{n+1}-4\cdot 11^n+4\cdot 11^n -4^{n+1}\\
=&\ (11\cdot 11^n-4\cdot 11^n)+(4\cdot 11^n -4^{n+1})\\
=&\ 7\cdot 11^n+4(11^n-4^n).
\end{align*} Since $7$ divides $11^n-4^n$ by $P_n$, we have $7\cdot 11^n+4(11^n-4^n)$ is divisible by $7$. By the equation above, we conlude that $11^{n+1}-4^{n+1}$ is divisible by 7. Therefore $P_{n+1}$ is true if $P_n$ is true. By the principle of mathematical induction, we make the conclusion that $P_n$ is true for all positive integers $n$.

This statement also follows from the following well-known formula,
$$
x^n-y^n=(x-y)(x^{n-1}+x^{n-2}\cdot y+\cdots x\cdot y^{n-2}+y^{n-1}).
$$ Let $x=11$ and $y=4$, we have
$$
11^n-4^n=7(11^{n-1}+4\cdot 11^{n-2}+\cdots + 4^{n-2}\cdot 11+4^{n-1}).
$$


Leave a Reply

Close Menu