$a_n>\sqrt{2n}$ for recursive sequence

Question

Suppose $a_1=1$, $a_2=2$, and $a_{n+1}=\frac{a_na_{n-1}+1}{a_{n-1}}$ for $n \ge 2$. Prove that for any positive integer $n \ge 3$, we have $a_n > \sqrt{2n}$.

I tried using induction on this. The base case is $n=3$, and we have $a_3=\frac{a_2a_1+1}{a_1}=3>\sqrt{6}$, which is true.

For the inductive step, we need to prove that $a_{n+1}>\sqrt{2(n+1)}$ given $a_n>\sqrt{2n}$. I'm not sure how to show this. Could someone help?

Try plugging in your inductive hypothesis into the recurrence. — Doug, Sep 07 '22 at 16:12
It's false. Just try plotting the two sides of the inequality. Perhaps you made a small typo. — Doug, Sep 07 '22 at 16:37
Oops, I made a mistake. I just redid it and now I have to show $$\sqrt{4n(n-1)}+1>\sqrt{4(n^2-1)}$$. How can I do this? — , Sep 07 '22 at 16:42

score 1 · Answer 1 · answered Sep 07 '22 at 16:50

To show $\sqrt{4n(n-1)}+1>\sqrt{4(n^2-1)}$, square both sides to get $4n(n-1)+2\sqrt{4n(n-1)}+1>4(n^2-1)$ or $4n^2-4n+1+2\sqrt{4n(n-1)}>4n^2-4$ or $2\sqrt{4n(n-1)}>4n-5$.

Squaring again, this becomes $4(4n(n-1))>16n^2-40n+25$ or $16n^2-16n>16n^2-40n+25$ or $24n > 25$ which is true for $n\gt 1$.

$a_n>\sqrt{2n}$ for recursive sequence

1 Answers1