# Proof by Induction that $16 \mid 5^n - 4n - 1$

Using induction, prove that $16\mid 5^n - 4n - 1$ for $n$ in $\mathbb{N}$

Here's what I have and what I'm stuck on:

basis: $n = 1$, $5 - 4(1) - 1 = 0$ and $16\mid 0$.

Hypothesis: Assume true for all $n \le k$

$$5^{k+1} - 4(k + 1) - 1 = 5\times5^k - 4k - 5$$

• For $n\in\mathbb{P}$, is that n is a prime? If so, the base case isn't 1. Commented Oct 29, 2014 at 2:38

Assume it is true for all $n\in\mathbb{N}$ with $n\leq k$

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

Now you can use the induction hypothesis and finish the proof.

As for the likely typo of using $\mathbb{P}$ as mentioned in comments above., as it turns out it is true for all natural numbers. Primes are a subset of the natural numbers. Since it is true for all nat's, it is true for all primes as well.

• Always try to force a large chunk of it to look like the induction hypothesis. Seeing that we had a $5\cdot 5^k$ suggested that we should try to force it to be a $5\cdot($induction hypothesis), which is why I picked to add and subtract $16k$. You are always allowed to add or subtract zero, just like you are always allowed to multiply by one. The tricky thing is what those "zeroes" and "ones" look like. Commented Oct 29, 2014 at 2:43
• Thank you very much. This was extremely helpful. I will keep in mind your suggestion of adding and subtracting 0. I'm sure something similar will come up on my next midterm. :) Commented Oct 29, 2014 at 2:50

By the binomial theorem, $5^{n}=(4+1)^{n}=4^2a+\binom{n}{1}4+1=16a+4n+1$, hence the result.

• Induction appears in the binomial theorem...
– lhf
Commented Oct 29, 2014 at 2:46