2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.