# Mathematical Induction

#### luckyNUM7

8 divides $$\displaystyle 5^n-4n-1$$ for all integers n greater than or equal to 1.

Proof:
Basis step:
n = 1

$$\displaystyle 5^1-4(1)-1$$ = 0
0/8 = 0
8 divides $$\displaystyle 5^n-4n-1$$ if n=1

Induction step:
Assume $$\displaystyle 5^n-4n-1$$ is divisible by 8 (induction hypothesis)
[show 5^(n+1) - 4(n+1) - 1 is divisible by 8]

• $$\displaystyle 5^(n+1) - 4(n+1) - 1 = 5^n+1 - 4n + 4 - 1$$
• $$\displaystyle = 5^n+1 - 4n +3$$
• $$\displaystyle =5^n *5^1 - 4n +3$$
...now im not sure where to go

#### luckyNUM7

...sorry the first bullet should be 5^n+1 - 4(n+1) -1 = ....

#### luckyNUM7

damn, and the second one should be 5^n+1 - 4n + 3

#### undefined

MHF Hall of Honor
A few points.

1. You can use the "Edit" feature rather than posting multiple times, it will keep the thread cleaner.

2. You made a silly error of not distributing the -4 properly, so you should have -5 where you currently have +3.

3. I think the problem can be solved by considering that when n is odd, 4n+1 is congruent to 5 (mod 8), and when n is even, 4n+1 is congruent to 1 (mod 8). That is, we have by induction hypothesis

$$\displaystyle 5^n-(4n+1)\equiv0\ (\text{mod}\ 8)$$

and so we can find out what $$\displaystyle 5^n$$ is (mod 8), by considering the two cases, n odd or even.

4. The way to get exponents with more than one character in LaTeX is like this (hover mouse over it to see the code): $$\displaystyle x^{12345}$$.

Edit: I had a typo; the -4 in red above used to say -1.

Last edited:

#### novice

8 divides $$\displaystyle 5^n-4n-1$$ for all integers n greater than or equal to 1.

Proof:
Basis step:
n = 1

$$\displaystyle 5^1-4(1)-1$$ = 0
0/8 = 0
8 divides $$\displaystyle 5^n-4n-1$$ if n=1

Induction step:
Assume $$\displaystyle 5^n-4n-1$$ is divisible by 8 (induction hypothesis)
[show 5^(n+1) - 4(n+1) - 1 is divisible by 8]
Since $$\displaystyle 5^n-4n-1$$ is divisible by 8, then $$\displaystyle 5^n-4n-1=8x, x\in \mathbb{Z}$$

Multiply through by 5

$$\displaystyle 5\cdot 5^n-5\cdot 4n-5\cdot 1=5\cdot 8x$$

$$\displaystyle 5^{n+1}-4n-16n-4-1=5\cdot 8x$$

Move $$\displaystyle -16n$$ to RHS

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

$$\displaystyle 5^{n+1}-4(n+1)-1=8(2n+5x)$$

Since $$\displaystyle 2n+5x$$is an integer, $$\displaystyle 5^{n+1}-4(n+1)-1$$ is divisible by 8.