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}


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.