Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.