I have to prove my mathematical induction that $5^n - 1$ is divisible by 4. for all non negative $n ≥ 0$. My solution is the following.
Base case: When $n = 0,
5^n-1 = 5^0-1 = 0$.
Base case holds for $n = 0.$
Induction Hypothesis: Assume the property holds for $n = k$, i.e. $5^k-1$ is divisible by $4$.
Induction Step: When $n = k + 1$, we must prove that $5^{k+1}-1$ is divisble by $4$.
$5^{k+1}-1 = 5 * 5^k-1$
From the hypothesis we know that $5^k-1$ is divisible by $4$. Any number divisible by $4$ and multiplied by $5$ is divisible by $4$.
Thus $5^{k+1}-1$ is divisible by $4$.
The actual answer booklet offers a solution that seems unnecessarily complex.
$5^{k+1} -1 = 5*5^{k-1}$
$= 5 *(5^k-1+1)-1$
$= 5 * (5^k - 1 ) + 5 - 1$
$= 5 * (5^k - 1) + 4$
By the induction hypothesis, $5k - 1$ is divisible by $4$. Clearly $4$ is also divisible by $4$ and therefore $5 ∗ (5 k − 1) + 4$ is divisible by $4$ and the induction step is proven.
Is my way of doing it correct or is it not complete enough?
Thanks.
No comments:
Post a Comment