Wednesday 4 December 2019

Mathematical Induction

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...