Mathematical Induction to Prove 21 Divides (4^{n-1} 5^{2n-1})

In this article, we will use mathematical induction to prove that 21 divides the expression (4^{n-1} 5^{2n-1}) for all integers (n geq 1). This proof highlights the power of mathematical induction in verifying complex number relationships.

Step 1: Base Case

To begin with, let's check the base case where (n 1): (4^{1-1} 5^{2 cdot 1 - 1} 4^0 5^1 1 cdot 5 5) However, we need to evaluate correctly:
(4^{1-1} 5^{2 cdot 1 - 1} 4^0 5^1 1 cdot 5 5) (4^2 5^1 16 cdot 5 80) (4^2 5^1 - 5 80 - 69 21) Since 21 divides 21, the base case holds.

Step 2: Induction Hypothesis

Next, we assume that the statement is true for some integer (k), i.e., we assume: (4^{k-1} 5^{2k-1} equiv 0 pmod{21}) This means that 21 divides (4^{k-1} 5^{2k-1}).

Step 3: Induction Step

Now, we need to prove the statement for (n k 1): (4^{(k 1)-1} 5^{2(k 1)-1} 4^k 5^{2k 1}) Using the property of exponents: (4^k 4 cdot 4^{k-1}) We can express our goal as: (4^k 5^{2k 1} 4 cdot 4^{k-1} 5^{2k 1}) Now, relate this to the induction hypothesis: (4 cdot 4^{k-1} 5^{2k 1} 4 cdot 4^{k-1} 5^2 cdot 5^{2k-1}) Next, rewrite (5^{2k 1}): (5^{2k 1} 5^2 cdot 5^{2k-1} 25 cdot 5^{2k-1}) Combing the terms: (4 cdot 4^{k-1} 25 cdot 5^{2k-1} 4 cdot 4^{k-1} 25 cdot 5^{2k-1})

Step 4: Modulo 21

We want to show that:

(4 cdot 4^{k-1} 25 cdot 5^{2k-1} equiv 0 pmod{21})

We can reduce 25 modulo 21:

(25 equiv 4 pmod{21})

Thus, we rewrite our expression:

(4 cdot 4^{k-1} 4 cdot 5^{2k-1} 4 cdot 4^{k-1} 5^{2k-1})

By the induction hypothesis, we know that (4^{k-1} 5^{2k-1} equiv 0 pmod{21}).

Therefore:

(4 cdot 4^{k-1} 5^{2k-1} equiv 4 cdot 0 equiv 0 pmod{21})

Conclusion:

Since we have shown that if the statement holds for (n k) it also holds for (n k 1), and we established the base case by mathematical induction, we conclude that:

21 divides (4^{n-1} 5^{2n-1}) for all integers (n geq 1).

Proof Without Induction

Another way to prove this is through specific algebraic manipulations and modular arithmetic:

Let (S 4^{n-1} 5^{2n-1}).

First, evaluate (S mod 7) and (S mod 3).

Modulo 7:

(2^2 4)

(2^{2n} equiv 4^n equiv 5^{2n} pmod{7})

(S mod 7 4^{n-1} 4 cdot 5^{2n-1} mod 7)

Given (5 equiv -2 pmod{7}), the modular inverse of 5 under mod 7 is 3.

(4 cdot 5 equiv -8 equiv -1 equiv 6 pmod{7})

(S mod 7 4 cdot 6^{2n-1} equiv 0 pmod{7})

Modulo 3:

(2 equiv -1 pmod{3})

(2^{2n} equiv 1 pmod{3})

(5 equiv 2 pmod{3})

(5^{2n} equiv 1 pmod{3})

(S mod 3 4 cdot 1 equiv 0 pmod{3})

Since (S) is divisible by both 3 and 7, it must be divisible by 21.