Proving that a sequence is decreasing How could I prove the following statement without using induction? I've been staring at this for the better part of an hour. (To be fair, I'm not very good at proof writing) Thanks in advance!
Define a sequence $a_n, n \ge 0,$ inductively by $a_0 = 2,$ and for all $n \ge 0, a_{n+1} = \sqrt{a_n + 1}.$
Using the fact that the polynomial $x^2 - x - 1 < 0$ if and only if $\frac{1-\sqrt{5}}{2} < x < \frac{1+\sqrt{5}}{2}$, prove that for every $n \ge 0, a_n > a_{n+1}.$
 A: Since you’re dealing with non-negative number, $a_{n+1}>a_n$ if and only if $a_{n+1}^2>a_n^2$. But $a_{n+1}^2=a_n+1$, so $a_{n+1}>a_n$ if and only if $a_n+1>a_n^2$, i.e., if and only if $a_n^2-a_n-1<0$. In other words, your sequence decreases from $a_n$ to $a_{n+1}$, which you don’t want, if and only if $a_n^2-a_n-1<0$. The last line of the problem reminds you of just when this is true. Can you now show that it’s never true?
You will actually be using induction: you’ll be showing that if $a_{n+1}\not> a_n$, then $a_{n+2}\not>a_{n+1}$.
A: Since $a_n>0$ for all $n$, it is enough to show that $a_n^2>a_{n+1}^2$. But this is equivalent to $a_{n}^2-a_{n+1}^2>0$, and we see that $a_{n}^2-a_{n+1}^2=a_n^2-a_n-1$, so we need only show that $a_n>\frac{1+\sqrt 5}{2}$. This is easy to show using induction, since $a_0>\frac{1+\sqrt 5}{2}$ and if $a_n>\frac{1+\sqrt 5}{2}$ then
$$a_{n+1}>\sqrt{\frac{1+\sqrt 5}{2}+1}=\frac{1+\sqrt 5}{2}$$
so by induction it is true for all $n$. Induction is definitely the right technique to use, since your sequence is defined inductively.
