# Using induction to prove an inequality for a sequence of numbers

We have the sequence $$d_n = \begin{cases} 1 &\text{ if } n=0 \\ \frac{n}{d_{n-1}} &\text{ if } n>0 \end{cases}$$

for all natural numbers $$n$$. ($$d_{n-1}$$ is the previous number of the sequence.)

examples: $$d_0 = 1$$, $$d_1 = 1$$, $$d_2 = 2$$, $$d_3 = \frac{3}{2}$$, $$d_4 = \frac{8}{3} \dots$$

I have to prove using induction that $$\forall n \in \mathbb N \setminus \{0\}$$, $$d_{2n-1}$$ $$\leq$$ $$\sqrt{2n-1}$$.

so far, I've figured out the pattern that for every n greater than or equal to $$2$$, $$d_{2n-1} = d_{2n-3} \, \frac{2n-1}{2n-2}$$.
i.e. $$d_5 = d_3 \, \frac{5}{4}$$

In the hints section, they told me to write $$d_{2k+1}$$ in terms of $$d_{2k-1}$$ and to use the difference of squares: $$(2k-1)(2k+1) = 4k^2 - 1$$ for the induction step.

Any hints/tips/advice on how to solve this problem is much appreciated! Thank you!

Your observation $$d_{2n-1} = d_{2n-3} \, \frac{2n-1}{2n-2}$$ is homologous with $$d_{2k+1} = d_{2k-1} \, \frac{2k+1}{2k}.$$
\begin{align} d_{2k-1} \, \frac{2k+1}{2k} &\le \sqrt{2k-1} \, \frac{\bbox[yellow, 2px]{2k+1}}{2k} \tag{induction hypothesis}\\ &\le \color{blue}{\sqrt{2k-1}} \, \frac{\bbox[yellow, 2px]{\color{blue}{\sqrt{2k+1}}}}{2k} \, \bbox[yellow, 2px]{\sqrt{2k+1}} \\ &\le \frac{\color{blue}{\sqrt{4k^2-1}}}{2k} \sqrt{2k+1} \tag{hint} \\ &\le 1 \cdot \sqrt{2k+1} = \sqrt{2k+1} \tag*{\square} \end{align}