Prove that $4^{2n} + 10n -1$ is a multiple of 25 Prove that if $n$ is a positive integer then $4^{2n} + 10n - 1$  is a multiple of $25$
I see that proof by induction would be the logical thing here so I start with trying $n=1$ and it is fine. Then assume statement is true and substitute $n$ by $n+1$ so I have the following:
$4^{2(n+1)} + 10(n+1) - 1$
And I have to prove that the above is a multiple of 25. I tried simplifying it but I can't seem to get it right. Any ideas? Thanks.
 A: 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.
A: 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$.)
A: $\rm\displaystyle 25\ |\ 10n\!-\!(1\!-\!4^{2n}) \iff 5\ |\ 2n - \frac{1-(-4)^{2n}}{5}.\ $ Now via $\rm\ \dfrac{1-x^k}{1-x}\, =\, 1\!+\!x\!+\cdots+x^{k-1}\ $ 
$\rm\displaystyle we\ easily\ calculate\ that, \  mod\ 5\!:\, \frac{1-(-4)^{2n}}{1-(-4)\ \ \,}\, =\, 1\!+\!1\!+\cdots + 1^{2n-1} \equiv\, 2n\ \ $ by $\rm\: -4\equiv 1$
A: Another solution, via congruences mod. $25$. First note $16\bmod 25$ generates a cyclic group of order $5$:
$$16^2\equiv 6,\quad16^3\equiv 6\cdot 16\equiv-4,\quad16^4\equiv6^2\equiv 11, \quad 16^5\equiv6\cdot-4\equiv1\mod25.$$
So let's examine each case:


*

*If $n\equiv 0\mod 5$, $\;16^n+10n-1\equiv1+0-1=0$.

*If $n\equiv 1\mod 5$, $\;16^n+10n-1\equiv16+10-1=25\equiv 0$.

*If $n\equiv 2\mod 5$, $\;16^n+10n-1\equiv 6+20-1=25\equiv 0$.

*If $n\equiv 3\mod 5$, $\;16^n+10n-1\equiv -4+30-1=25\equiv 0$.

*If $n\equiv 4\mod 5$, $\;16^n+10n-1\equiv 11+40-1=50\equiv 0$.


Thus in each case,  $\;16^n+10n-1$ is divisible by $25$.
A: 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)$$
A: This is an interesting property, so can we precisely describe when it is true? The answer is yes:

Theorem: In an arbitrary ring, $q^n$ is an affine function of $n$ if and only if $(q-1)^2=0$. We then have $q^n=1+n(q-1)$.

Proof: If $q^n=a+bn$, by taking $n=0$ and $n=1$ we see that $a=1$ and $b=q-1$. Taking $n=2$ results in $q^2=2q-1$, that is $(q-1)^2=0$.
Conversely, when $(q-1)^2=0$, it is easy to prove the relation by induction:
$$q^0=1$$
$$q^{n+1}=q(1+n(q-1))=nq^2-q(n-1)=1+(n+1)(q-1)$$
There is also a direct proof by seeing that $q^n=(1+(q-1))^n=\sum_{i=0}^n \tbinom{n}{i} (q-1)^i=1+n(q-1)$.

Application: in $\mathbb Z/25\mathbb Z$, if $q=4^2$, $(q-1)^2=15^2=0$, so $4^{2n}=1+15n$, or equivalently $4^{2n}+10n-1=0$.
A: Let $S$ be the shift operator on sequences: $Sa_n=a_{n+1}$. Then
$$
\color{#C00}{(S-16)}\color{#090}{(S-1)^2}\left(\color{#C00}{16^n}\color{#090}{-1+10n}\right)=0\tag1
$$
Since $(x-16)(x-1)^2=x^3-18x^2+33x-16$, our sequence satisfies
$$
a_n=18a_{n-1}-33a_{n-2}+16a_{n-3}\tag2
$$
Note that
$$
\begin{array}{c|c}
n&16^n-1+10n&\bmod{25}\\\hline
0&0&0\\
1&25&0\\
2&275&0
\end{array}\tag3
$$
$(2)$ and $(3)$ show inductively that, for $n\ge0$,
$$
16^n-1+10n\equiv0\pmod{25}\tag4
$$
