We are tasked with proving by induction that $9^n - 5^n - 4^n$ is divisible by 20 for all $n \geq 1$. In other words, we need to show that $9^n - 5^n - 4^n \equiv 0 \pmod{20}$ for all $n \geq 1$.

Step 1: Base Case $n = 1$

First, we check if the statement holds true for $n = 1$:

$9^1 - 5^1 - 4^1 = 9 - 5 - 4 = 0$

Clearly, $0$ is divisible by 20. Hence, the base case is true.

Step 2: Inductive Hypothesis

Assume that the statement holds for some arbitrary $n = k$, i.e.,

$9^k - 5^k - 4^k \equiv 0 \pmod{20}$

This means that $9^k - 5^k - 4^k$ is divisible by 20, or equivalently:

$9^k - 5^k - 4^k = 20m$

for some integer $m$.

Step 3: Inductive Step

We need to show that the statement holds for $n = k + 1$, i.e.,

$9^{k+1} - 5^{k+1} - 4^{k+1} \equiv 0 \pmod{20}$

Using the properties of exponents, we rewrite the expression:

$9^{k+1} - 5^{k+1} - 4^{k+1} = 9 \cdot 9^k - 5 \cdot 5^k - 4 \cdot 4^k$

We aim to prove that this expression is divisible by 20. To do this, we will analyze each term modulo 20.

Step 3.1: Modulo 20 Patterns for Powers of 9, 5, and 4

• Powers of 9 modulo 20:

The powers of 9 modulo 20 repeat in a cycle of length 2:

$9^1 \equiv 9 \pmod{20}, \quad 9^2 \equiv 1 \pmod{20}, \quad 9^3 \equiv 9 \pmod{20}, \quad 9^4 \equiv 1 \pmod{20}, \quad \dots$

• Powers of 5 modulo 20:

Since $5^n \equiv 5 \pmod{20}$ for all $n \geq 1$, powers of 5 remain constant:

$5^1 \equiv 5 \pmod{20}, \quad 5^2 \equiv 5 \pmod{20}, \quad \dots$

• Powers of 4 modulo 20:

The powers of 4 modulo 20 repeat in a cycle of length 2:

$4^1 \equiv 4 \pmod{20}, \quad 4^2 \equiv 16 \pmod{20}, \quad 4^3 \equiv 4 \pmod{20}, \quad 4^4 \equiv 16 \pmod{20}, \quad \dots$

Step 3.2: Applying the Modulo 20 Cycles

Let's consider $n = k+1$ and simplify the expression $9^{k+1} - 5^{k+1} - 4^{k+1} \mod 20$:

• If $k$ is odd, then: $9^k \equiv 9 \pmod{20}, \quad 5^k \equiv 5 \pmod{20}, \quad 4^k \equiv 4 \pmod{20}$ Thus, the next powers are: $9^{k+1} \equiv 1 \pmod{20}, \quad 5^{k+1} \equiv 5 \pmod{20}, \quad 4^{k+1} \equiv 16 \pmod{20}$ Therefore, $9^{k+1} - 5^{k+1} - 4^{k+1} \equiv 1 - 5 - 16 = -20 \equiv 0 \pmod{20}$

• If $k$ is even, then: $9^k \equiv 1 \pmod{20}, \quad 5^k \equiv 5 \pmod{20}, \quad 4^k \equiv 16 \pmod{20}$ Thus, the next powers are: $9^{k+1} \equiv 9 \pmod{20}, \quad 5^{k+1} \equiv 5 \pmod{20}, \quad 4^{k+1} \equiv 4 \pmod{20}$ Therefore, $9^{k+1} - 5^{k+1} - 4^{k+1} \equiv 9 - 5 - 4 = 0 \pmod{20}$

Step 4: Conclusion

In both cases (whether $k$ is odd or even), we have shown that $9^{k+1} - 5^{k+1} - 4^{k+1} \equiv 0 \pmod{20}$. Therefore, by the principle of mathematical induction, the expression $9^n - 5^n - 4^n$ is divisible by 20 for all $n \geq 1$.

Would you like more details on any step or have further questions?

Here are some related questions to explore:

1. Can we apply a similar approach to prove divisibility by 10 or 5?
2. How do different moduli affect the proof structure in modular arithmetic?
3. How does the cycle length of powers of integers modulo different bases change?
4. Can we prove divisibility using other methods besides induction?
5. What happens if we change the base numbers in the expression $9^n - 5^n - 4^n$?

Tip: When proving divisibility via induction, focus on simplifications that involve modular arithmetic properties for efficiency.