# 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}.$

-
Why don't you want to use induction? Can you see how to do it using induction? –  Ben Millwood Sep 19 '12 at 1:07
The hint will actually be used in the induction step. –  Brian M. Scott Sep 19 '12 at 1:11
Really? Well, thank you for clarifying that before I set out to solve this! I actually wasn't aware that we had to use it here at all. –  user41419 Sep 19 '12 at 1:12

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}$.
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.