# proof by induction 5^n-1 is divisible by 4

• Nov 28th 2011, 06:25 PM
Jskid
proof by induction 5^n-1 is divisible by 4
Use mathematical induction to prove that the assertion is true for \$\displaystyle n\ge 1\$. \$\displaystyle 5^n-1\$ is divisible by \$\displaystyle 4\$.

basis \$\displaystyle n_{o}=1\$ then \$\displaystyle 5^1-1=4\$ is divisible by \$\displaystyle 4\$.

IH let \$\displaystyle 1\le l<k\$ and assume \$\displaystyle 5^l-1\$ is divisible by \$\displaystyle 4\$.

Induction Step
\$\displaystyle 5^{k}-1=(5)5^{k-1}-1\$
Since \$\displaystyle 5^{k-1}-1\$ is divisble by \$\displaystyle 4\$ (by the induction hypothesis) then \$\displaystyle (5)5^{k-1}-1\$ is also divisible by \$\displaystyle 4\$

Is this right?
What is wrong with the latex
• Nov 28th 2011, 06:32 PM
pickslides
Re: proof by induction 5^n-1 is divisible by 4
The induction step should have n = k+1
• Nov 29th 2011, 09:54 AM
Annatala
Re: proof by induction 5^n-1 is divisible by 4
Quote:

IH let \$\displaystyle 1\le l<k\$ and assume \$\displaystyle 5^l-1\$ is divisible by \$\displaystyle 4\$.
If this is a proof by induction you need to go a step at a time, not prove it for all numbers at once.

I'd say this. "Assume \$\displaystyle 4 |(5^k-1)\$. We want to show \$\displaystyle 4|( 5^k^+^1-1)\$."

Quote:

Since \$\displaystyle 5^{k-1}-1\$ is divisble by \$\displaystyle 4\$ (by the induction hypothesis) then \$\displaystyle (5)5^{k-1}-1\$ is also divisible by \$\displaystyle 4\$
Not quite, no. You have the formula wrong, and you need to show your work; how do you know 4 divides \$\displaystyle 5^k^+^1-1\$ for certain?