Inductive problem $\sqrt{k+1} -1\le \frac{a_{k-1}}{a_k}\le\sqrt{k}$

Question

I am trying to solve this, using Inductive tools. any suggestions?

Given: $$(k+1)\cdot a_{k+1}=a_k+a_{k-1}\qquad a_1=1 ,\, a_0=0 $$

Need to prove: $$\sqrt{k+1} -1\le \frac{a_{k-1}}{a_k}\le\sqrt{k}$$

Answer 1

We can prove the slightly stronger case where both inequalities are strict.

Taking $a_0 = 0, a_1 = 1$, and $a_{k+1} = \frac1{k+1}(a_k + a_{k-1})$, the upper bound (R.H.S) is false for $k = 2$ and $k= 4$, while the lower bound (L.H.S) is false for $k = 1$ and $k = 3$.

The first term where both bounds are true is at $ k = 5$ when $\sqrt{6}-1 < \dfrac{ 1/4 }{3/20} < \sqrt{5}$.

This $k = 5$ is the initial case for induction on $\sqrt{k+1}-1<S_k<\sqrt{k}$ with both sides strict, where

$$S_k \equiv \frac{a_{k-1}}{a_k}~,\qquad \text{such that}~~S_{k+1} = \frac{a_k }{a_{k+1} } = \frac{ a_k }{ (a_k + a_{k-1})/(k+1) } = \frac{ k+1 }{ 1+ S_k }$$

Suppose for some $n > 5$, $$\sqrt{n+1}-1<S_n<\sqrt{n}\tag{1} \label{Eq_if_n_is_true}$$

The R.H.S. (upper bound) for the desired $(n+1)$th case is easily given by the L.H.S. (lower bound) of the induction hypothesis Eq\eqref{Eq_if_n_is_true}:

$$\begin{align} \sqrt{n+1} < 1 + S_n \implies \frac1{ 1+ S_n } < \frac1{\sqrt{n+1}} &\implies \frac{n+1}{ 1+ S_n } < \sqrt{n+1} \\ &\implies S_{n+1} < \sqrt{n+1} \tag{2.R} \label{Eq_RHS_for_n+1} \end{align}$$

---

The L.H.S. (lower bound) of the desired $(n+1)$th case requires

$$\sqrt{n+2} -1 \overset{?}{<} S_{n+1} \quad \Longleftrightarrow \quad \sqrt{n+2} \overset{?}{<} 1 + \frac{ n + 1}{ 1 + S_n } \tag{2.L.a} \label{Eq_LHS_for_n+1} $$

Now, the R.H.S. of the induction hypothesis Eq\eqref{Eq_if_n_is_true} gives

$$\begin{alignat}{3} S_n < \sqrt{n} &\implies 1 + S_n < 1 + \sqrt{n} &&&&\\ &\implies \frac1{1 + \sqrt{n} } < \frac1{ 1 + S_n } &&\implies 1 + \frac{ n + 1}{ 1 + \sqrt{n} } < 1 + \frac{ n + 1}{ 1 + S_n } \\ &&&\implies \frac{ n + \sqrt{n} + 2}{ 1 + \sqrt{n} } < 1 + \frac{ n + 1}{ 1 + S_n } \tag{1.R} \label{Eq_RHS_for_n_push} \end{alignat}$$ This suggests that we would like to push Eq\eqref{Eq_LHS_for_n+1} in its the new form (on the right) by squeezing in the term from Eq\eqref{Eq_RHS_for_n_push} as the following: $$ \sqrt{n+2} \overset{?}{<}\frac{ n + \sqrt{n} + 2}{ 1 + \sqrt{n} } < 1 + \frac{ n + 1}{ 1 + S_n } \tag{2.L.b} \label{Eq_LHS_for_n+1_push}$$ Multiply the whole expression by $1 + \sqrt{n}$ then square both sides. We will see the terms cancel and it becomes trivially true:

$$\left( 1 + \sqrt{n} \right)^2 (n+2) \overset{?}{<} \left( n + \sqrt{n} + 2 \right)^2 \quad \Longleftrightarrow \quad 0 \overset{?}{<} 2(n+1) \tag{2.L.c} \label{Eq_LHS_for_n+1_final} $$

Summary

Given the induction hypothesis Eq\eqref{Eq_if_n_is_true} being true at some $n > 5$, the case for $n+1$

$$\sqrt{n+2} - 1 < S_{n+1} < \sqrt{n+1} $$

is true because the R.H.S. is taken care of by Eq\eqref{Eq_RHS_for_n+1}, while the L.H.S. becomes to Eq\eqref{Eq_LHS_for_n+1} that is pushed to Eq\eqref{Eq_LHS_for_n+1_push}, which in turn is equivalent to Eq\eqref{Eq_LHS_for_n+1_final} that is true.$~~$Q.E.D.