$5^n -4n-1$ is divisible by 16

Question

Checking the notes of a proof-based course I encountered this exercise. $5^n -4n-1$ is divisible by $16$ for every natural $n>0$.

I'm stuck with this problem. Help me, please

---

Update: I already solved this problem

Answer 1

Hint: the step from $\;n\;$ to $\;n+1\;$ :

$$5^{n+1}-4(n+1)-1=5\cdot5^n-4n-4-1=(5^n-4n-1)+4\cdot5^n-4=$$

$$=(5^n-4n-1)+4\left(5^n-1\right)$$

All that is left to prove is that $\;5^n-1\;$ is divisible by $\;4\;$ , but

$$5^n-1=(5-1)(5^{n-1}+5^{n-2}\ldots+5^2+5+1)$$

Answer 2

Hint:

Use congruences: by Euler's theorem, the order of $5$ modulo $16$ is a divisor of $\varphi(16)=8$, and you readily can check it has order $4$. Also $4n\equiv 4\cdot (n\bmod 4) \mod{16}$ since $4^2\equiv 0\mod 16$.

Therefore you only have to check that $\;5^n -4n-1\equiv 0\mod 16$ for each of the congruence classes modulo $4$, i.e. for $n=0,1,2,3$.

Answer 3

Alternative hint for the step from $n$ to $n+1$ in a proof by induction:

$5^{n+1}-4(n+1)-1=5\cdot(5^n-4n-1)+16n$

Answer 4

Base case: $n=1$ It's easy to see that $5^n -4n-1$ is divisible by $16$ because for $n=1$: $$5^n -4n-1 = 5 - 4 - 1 = 0$$ and $0$ is divisible by $16$.

Induction hypothesis: assume now that $5^n -4n-1$ is divisible by $16$ for an arbitrary $n$

Induction step: prove that from the induction hypothesis it follows that $5^{(n+1)} -4(n+1)-1$ is divisible by $16$.

Since $5^n -4n-1$ is divisible by $16$ can write $5^n -4n-1 = 16k$ for some natural number $k>0$. This can be also written as (moving the $4n$ to the right): $$5^n -1 = 16k +4n$$

Now $5^{(n+1)} -4(n+1)-1=5^{(n+1)} -4n -4 -1 = 5^{(n+1)} -4n -5 = 5(5^n)-4n-5 = 5(5^n-1)-4n$

But since by the induction hypothesis $5^n -1 = 16k +4n$ we can write: $$5(5^n-1)-4n=5(16k +4n) -4n= 16(5k)+20n-4n=16(5k)+16n=16(5k+n)$$

which is a multiple of $16$.