I have to prove my mathematical induction that 5n−1 is divisible by 4. for all non negative n≥0. My solution is the following.
Base case: When n=0,5n−1=50−1=0.
Base case holds for n=0.
Induction Hypothesis: Assume the property holds for n=k, i.e. 5k−1 is divisible by 4.
Induction Step: When n=k+1, we must prove that 5k+1−1 is divisble by 4.
5k+1−1=5∗5k−1
From the hypothesis we know that 5k−1 is divisible by 4. Any number divisible by 4 and multiplied by 5 is divisible by 4.
Thus 5k+1−1 is divisible by 4.
The actual answer booklet offers a solution that seems unnecessarily complex.
5k+1−1=5∗5k−1
=5∗(5k−1+1)−1
=5∗(5k−1)+5−1
=5∗(5k−1)+4
By the induction hypothesis, 5k−1 is divisible by 4. Clearly 4 is also divisible by 4 and therefore 5∗(5k−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