Q.Use induction to prove that $5^{n+1}+4\times 6^n$ when divided by 20 leaves a remainder 9, for all natural numbers $n$.

Step 1. Base case. $P(1)$: $5^2+4\times6=25+24=49=20\times2+9$. True (remainder $9$).

Step 2. Inductive hypothesis. Assume $P(k):5^{k+1}+4\times6^k=20\lambda+9$.

Step 3. Inductive step. $5^{k+2}+4\times6^{k+1}=5\times5^{k+1}+6\times4\times6^k$. Using $5^{k+1}=20\lambda+9-4\times6^k$ from the hypothesis: $=5\big(20\lambda+9-4\times6^k\big)+6\times4\times6^k=100\lambda+45-20\times6^k+24\times6^k=100\lambda+45+4\times6^k=20(5\lambda+2)+5+4\times6^k$. Alternatively, more directly: $5^{k+2}+4\times6^{k+1}=5\times5^{k+1}+4\times6^k\times6=5\times5^{k+1}+5\times4\times6^k+4\times6^k=5\big(5^{k+1}+4\times6^k\big)+4\times6^k=5(20\lambda+9)+4\times6^k=100\lambda+45+4\times6^k$. Since $6^k=(5+1)^k\equiv1\pmod5$ is not needed here — instead note $4\times6^k\equiv4\pmod{20}$ can be verified by induction too, but more simply: $100\lambda+45+4\times6^k=20(5\lambda+2)+5+4\times6^k$, and …

• Forgetting that $6^k\equiv1\pmod5$ (needed to absorb the leftover $4\times6^k$ term …