Subjects number theory

Induction Divisibility

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Induction Divisibility


1. **State the problem:** We want to prove by mathematical induction that the number $$U_n = 2^{6n} + 3^{2n-2}$$ is divisible by 5 for all positive integers $n$. 2. **Base case ($n=1$):** Calculate $$U_1 = 2^{6\cdot1} + 3^{2\cdot1 - 2} = 2^6 + 3^0 = 64 + 1 = 65.$$ Since 65 is divisible by 5, the base case holds. 3. **Inductive hypothesis:** Assume that for some positive integer $k$, $$U_k = 2^{6k} + 3^{2k-2}$$ is divisible by 5. That is, $$U_k \equiv 0 \pmod{5}.$$ 4. **Inductive step:** We need to prove that $$U_{k+1} = 2^{6(k+1)} + 3^{2(k+1)-2} = 2^{6k+6} + 3^{2k}$$ is divisible by 5. 5. **Rewrite $U_{k+1}$:** $$U_{k+1} = 2^{6k} \cdot 2^6 + 3^{2k} = 2^{6k} \cdot 64 + 3^{2k}.$$ 6. **Consider modulo 5:** We analyze powers modulo 5. - Since $2^4 \equiv 1 \pmod{5}$, then $2^{6} = 2^{4} \cdot 2^{2} \equiv 1 \cdot 4 = 4 \pmod{5}$. - Also, $2^{6k} = (2^6)^k \equiv 4^k \pmod{5}$. - For powers of 3 modulo 5, note that $3^4 \equiv 1 \pmod{5}$. - Then $3^{2k} = (3^2)^k = 9^k \equiv 4^k \pmod{5}$ because $9 \equiv 4 \pmod{5}$. 7. **Substitute modulo 5:** $$U_{k+1} \equiv 2^{6k} \cdot 64 + 3^{2k} \equiv 4^k \cdot 4 + 4^k = 4^k (4 + 1) = 4^k \cdot 5 \equiv 0 \pmod{5}.$$ 8. **Conclusion:** Since $U_1$ is divisible by 5 and $U_{k+1}$ is divisible by 5 whenever $U_k$ is, by induction, $U_n$ is divisible by 5 for all positive integers $n$. **Final answer:** $U_n = 2^{6n} + 3^{2n-2}$ is divisible by 5 for all positive integral values of $n$.