Mathematical Induction

Apr 2010
7
0
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
 
Apr 2010
7
0
...sorry the first bullet should be 5^n+1 - 4(n+1) -1 = ....
 
Apr 2010
7
0
damn, and the second one should be 5^n+1 - 4n + 3
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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:
Sep 2009
502
39
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.