Prove that $4^{2n} + 10n -1$ is a multiple of 25

Here is a proof by induction. Suppose $4^{2n}+10n-1=25k$.

$$4^{2(n+1)}+10(n+1)-1$$ $$=16\cdot 4^{2n}+10n+9$$ $$=16\cdot 4^{2n}+160n-16-150n+25$$ $$=16(4^{2n}+10n-1)-150n+25$$ $$=16(25k)-25\cdot 6n+25$$ $$=25(16k-6n+1)$$


1) Proof by induction:

Set $4^{2n}+10n-1=25k$ and use this to replace the term $4^{2(n+1)}$ in your expression.

It remains to show that 25 divides $16(1-10n)+10(n+1)-1$ which is obviously true.

2) Shorter proof without induction: Expand $(5-1)^{2n}$ using the binomial theorem.


Here are the details to complete the induction argument you started. There are better ways than induction.

By the induction hypothesis, $4^{2n}+10n-1$ is a multiple of $25$. So it is enough to prove that $$\left(4^{2n+2}+10(n+1)-1\right)-\left(4^{2n}+10n-1\right)\tag{$1$}$$ is a multiple of $25$.

Expression $(1)$ simplifies to $4^{2n+2}-4^{2n}+10$. But $4^{2n+2}=(16)4^{2n}$, so we want to prove that $(15)4^{2n}+10$ is a multiple of $25$.

It is enough to prove that $(3)4^{2n}+2$ is a multiple of $5$. We have $4\equiv -1\pmod{5}$, so $4^{2n}\equiv 1\pmod{5}$, and therefore $(3)4^{2n}+2\equiv 5\equiv 0\pmod{5}$.

(If you don't know about congruences, we can note that the decimal representation of $4^{2n}$ ends in $6$, since $4^2=16$, and conclude that the decimal representation of $(3)4^{2n}+2$ ends in $0$.)

Tags:

Induction