$\begingroup$

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$$

$\endgroup$ 1

2 Answers

$\begingroup$

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.

$\endgroup$ 2 $\begingroup$

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

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy