<s>[INST] 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!
 [/INST] 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}
</s>