The sequence is defined as $d_n = 1$ if $n = 0$, $\frac{n}{d_{n-1}}$ otherwise. The goal is to prove $$\forall n \in \mathbb{Z^+}, d_{2n-1} \leq \sqrt{2n-1}$$ using induction. I successfully proved the base case, and laid out the induction step: assume $$d_{2k-1} \leq \sqrt{2k-1}$$ prove $$d_{2k+1} \leq \sqrt{2k+1}$$ But I am now struggling to algebraically prove the later inequality. I expressed $d_{2k+1}$ in terms of $d_{2k-1}$:
$$d_{2k+1} = \frac{(2k+1)d_{2k-1}}{2k}$$ But I do not see any steps I can take from here. Any help is appreciated! I am new to this resource, please let me know if I formatted anything incorrectly!
Answer
Starting from
$$d_{2k-1} \leq \sqrt{2k-1}$$
multiply both sides with $2k+1$ and you will get
$$2k\cdot d_{2k+1} = (2k+1)d_{2k-1} \leq (2k+1)\sqrt{2k-1}$$
Divide both sides by $2k$:
$$d_{2k+1} \le \sqrt{2k+1} \frac{\sqrt{(2k-1)(2k+1)}}{2k} \leq \sqrt{2k+1} \sqrt{\frac{4k^2-1}{4k^2}} \le \sqrt{2k+1}$$
No comments:
Post a Comment