2

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

user926356
  • 1,250
  • 10
    Hint: $5^n=(4+1)^n$ – saulspatz Jul 21 '20 at 20:21
  • 2
    Of course $0$ is divisible by $16$, so, the statement is true for $n=1$. Now suppose that the statement is true for some arbitrary $n$, and, with this, show that the statement is true for $n+1$. – azif00 Jul 21 '20 at 20:23
  • 2
    A Combinatorial Proof. Consider the set $S$ of arrays $(x_1,x_2,\ldots,x_n)$ where $x_i\in{0,1,2,3,4}$ such that there are at least two indices $k\in{1,2,\ldots,n}$ such that $x_k\neq 0$. Let $f:S\to{1,2,\ldots,n}^2$ which sends each $(x_1,x_2,\ldots,x_n)\in S$ to $(i,j)$, where $i$ and $j$ are the smallest indices $i$ and $j$ such that $i<j$, $x_i\neq 0$, and $x_j\neq 0$. Prove that the number of elements of $S$ which is mapped under $f$ to the same value $(i,j)\in{1,2,\ldots,n}^2$ such that $i<j$ is a multiple of $16$. – Batominovski Jul 21 '20 at 20:29

4 Answers4

2

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

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • I scratched out a proof similar to this one, but couldn't type quickly enough to post. The only difference was that I used saulspatz's hint to show $5^n-1=(4+1)^n-1$ is divisible by $4$. $(4+1)^n$ is a multiple of $4$ plus $1$, so ... .. – Chris Leary Jul 21 '20 at 20:46
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$.

Bernard
  • 175,478
2

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$

J. W. Tanner
  • 60,406
0

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

user2314737
  • 115