Prove that $7 \mid 11^n - 4^n$ with mathematical induction I want to prove that $7 \mid 11^n - 4^n$ with mathematical induction. This is what I wrote:

*

*For $n = 1$, we have $7 \mid 11^1 - 4^1 \Rightarrow 7 \mid 7$ which is obviously true. $\checkmark$


*Assume that the statement is true for $n = k$. So: $7 \mid 11^k - 4^k$ and therefore there is an integer such that $m$ such that: $11^k - 4^k = 7m$. Thus: $4^k = 11^k - 7m$.


*Now we prove its truth for $n = k + 1$. So we want to prove that $7 \mid 11^{k + 1} - 4^{k + 1}$. We can write this like this: $7 \mid \big(11\cdot11^k\big) - \big(4\cdot4^k\big)$ and since $4^k = 11^k - 7m$, so in fact we have to prove: $7 \mid \big(11 \cdot11^k\big) - \big(4\cdot(11^k - 7m)\big) \Longrightarrow 7 \mid 11\cdot11^k - 4\cdot11^k + 7(4m) \Longrightarrow 7 \mid 7\cdot11^k + 7(4m) \Longrightarrow 7 \mid 7(11^k + 4m)$.
But from here you can clearly see that $7(11^k + 4m)$ is divisible by 7. So according to the principle of mathematical induction, the statement is proved. $\blacksquare$
Now my question is, is this proof correct? And is there another way to prove this statement by mathematical induction?
 A: By modulo
$$
\begin{aligned}
& \therefore 11^n-4^n \equiv 4^n-4^n \equiv 0 \quad(\bmod 7) \\
& \therefore 7 | 11^n-4^n
\end{aligned}
$$
A: A more general way would be to prove that $a^n-b^n=(a-b)(a^{n-1}+ba^{a-2}+\cdots+b^{n-1}a+ b^{n-1})$.
Another way would be to prove the binomial theorem $(a+b)^n=\sum_{n\ge i\ge 0}\binom{n}{i}a^ib^{n-i}$ and then expand $11^n=(7+4)^n$.
A third and alternate (unnecessary) way is to notice that $11^n-4^n$ is the number of ways of giving one of $11$ candies $\lbrace c_1,\cdots,c_{11}\rbrace$ to $n$ children such that not all of them get one of $c_1,c_2,c_3$ or $c_4$. No matter the distribution of candies, there is at least one kid who has only $7$ options for candy. So, $11^n-4^n$ is always divisible by $7$.
A: Let's modify your induction proof so that we directly use the induction hypothesis that $7 \mid 11^k - 4^k$ for some positive integer $k$.
Let $P(n)$ be the the statement that $7 \mid 11^n - 4^n$.
You handled the $n = 1$ case correctly.
Since the statement $7 \mid 11^n - 4^n$ holds for $n = 1$, we may assume $P(k)$ holds for some positive integer $k$.  That is, $7 \mid 11^k - 4^k$ holds for some positive integer $k$.  Then there exists an integer $m$ such that $7m = 11^k - 4^k$.
Thus far, I have essentially reformulated what you said in your proof.  Now, we will express $11^{k + 1} - 4^{k + 1}$ in terms of $11^k - 4^k$ so that we can use the induction hypothesis in the induction step.
Let $n = k + 1$.  Then
\begin{align*}
11^{k + 1} - 4^{k + 1} & = 11 \cdot 11^k - 4 \cdot 4^{k}\\
                       & = (7 + 4)11^k - 4 \cdot 4^k\\
                       & = 7 \cdot 11^k + 4 \cdot 11^k - 4 \cdot 4^k\\
                       & = 7 \cdot 11^k + 4(11^k - 4^k)\\
                       & = 7 \cdot 11^k + 4 \cdot 7m && \text{by the induction hypothesis}\\
                       & = 7(11^k + 4m)
\end{align*}
Since $11^k + 4m$ is an integer, $7 \mid 11^{k + 1} - 4^{k + 1}$.  Thus, $P(k) \implies P(k + 1)$ for each positive integer $k$.  Since $P(1)$ holds and $P(k) \implies P(k + 1)$ for each positive integer $k$, $P(n)$ holds for each positive integer $n$ by the Principle of Mathematical Induction.
