# A tough Sequence

1. May 20, 2008

### Shing

$$a_{n+1}=3-\frac{1}{a_n}$$
$$a_1=1$$

How should I prove that $$a_{n+1}>a_n$$
for all n, ?
I have tired to use counter example,
assuming
$$a_n>a_{n+1}$$
but I found that what I was doing is just to counter "for all n"

How should I prove that
$$a_{n+1}>a_n$$ ,for all n ?

2. May 20, 2008

### gunch

Induction seems to be the obvious choice. Try working backwards by assuming:
$$a_{n+1} > a_n$$
and then showing that it implies $$a_n > a_{n-1}$$. You should then be able to reverse the steps, prove $$a_2 > a_1$$ and the induction is complete.

3. May 21, 2008

### Shing

probably I got it now,
thanks!

Last edited: May 21, 2008
4. May 21, 2008

### rock.freak667

Well if I had to do this in an exam, I wouldn't use induction,too much for me to write and I don't like to write.

$$a_{n+1}=3-\frac{1}{a_n}$$

$-a_n$ i.e. minus a_n from both sides of the equation.

$$a_{n+1}-a_n =3-\frac{1}{a_n} -a_n$$

Bring the right side to the same denominator and see what happens.From the expression for $a_{n+1}$ and $a_1=1$, what does that say for $a_n$?

5. May 22, 2008

### Shing

If you mean $a_{n+1}-a_n$ is positive as $\frac{{a_n}^2+3a_n-1}{a_n}$ is positive and that implies $a_{n+1}>a_n$

but how do you know that $\frac{{a_n}^2+3a_n-1}{a_n}$ is positive?
or ${a_n}^2+3a_n>1$?

6. May 22, 2008

### gunch

If you want to avoid typing out an inductive argument, simply assume the minimality of n.

Assume for contradiction that there exist at least one n such that $a_{n} \leq a_{n+1}$. Let $m$ be the smallest integer such integer. Then:
$$a_{m} \leq a_{m+1} \Rightarrow 3-\frac{1}{a_{m-1}} \leq 3-\frac{1}{a_m} \Rightarrow a_{m-1} \leq a_m$$
This contradicts the minimality of m.

7. May 22, 2008

### Shing

What is the minimality of n?
I checked this in the Internet, is it something about Strong minimality theory??

8. May 22, 2008

### gunch

No it's simply a way to say that m is the least possible. We assumed that $m$ was the smallest value for which the original statement was false, but we showed that this implies that $m-1$ makes the original statement false. There exist a value smaller than m even though we assumed m was the smallest, therefore there can't exist a smallest element.

9. May 22, 2008

### Kurret

edit: Sorry, was wrong :)

10. May 22, 2008

### sennyk

Direct Proof?

$$a_{n+1}=3-\frac{1}{a_n}$$
$$a_1=1$$

Prove: $a_{n+1}>a_n$ for all n?

Let's use a direct comparison:

$$a_{n+1} > a_n$$
$$3 - \frac{1}{a_n} > a_n$$
$$\frac{a_n^2-3a_n+1}{a_n} < 0$$

This is zero or undefined for $a_n = \frac{3 \pm \sqrt{5}}{2}, 0$

The solution to this inequality is $a_n < \frac{3 - \sqrt{5}}{2} \cup 0 < a_n < \frac{3 + \sqrt{5}}{2}$.

Since $a_1$ is in the solution set, this is shown to be true.

Now we have to show that you can't jump boundaries for $a_1 = 1$.

Last edited: May 22, 2008
11. May 22, 2008

### sennyk

I made a mistake in my initial reply here it is fixed.

$$a_{n+1}=3-\frac{1}{a_n}$$
$$a_1=1$$

Prove: $a_{n+1}>a_n$ for all n?

Let's use a direct comparison:

$$a_{n+1} > a_n$$
$$3 - \frac{1}{a_n} > a_n$$
$$\frac{a_n^2-3a_n+1}{a_n} < 0$$

This is zero or undefined for $a_n = \frac{3 \pm \sqrt{5}}{2}, 0$

The solution to this inequality is $a_n < 0 \cup \frac{3 - \sqrt{5}}{2} < a_n < \frac{3 + \sqrt{5}}{2}$.

Since $a_1$ is in the solution set, this is shown to be true.

Now we have to show that you can't jump boundaries for $a_1 = 1$.

12. May 22, 2008

### sennyk

Since $a_1 = 1$ lies in the second boundary, we will only work with that boundary.

Next we have to find all values for $a_n$ that will allow $\frac{3-\sqrt{5}}{2} < 3 - \frac{1}{a_n} < \frac{3+\sqrt{5}}{2}$ to be true.

$$\frac{3-\sqrt{5}}{2} < 3 - \frac{1}{a_n}$$
$$a_n < 0 \cup a_n > \frac{3-\sqrt{5}}{2}$$

$$\frac{3+\sqrt{5}}{2} > 3 - \frac{1}{a_n}$$
$$0 < a_n < \frac{3+\sqrt{5}}{2}$$

The intersection of those intervals yields: $\frac{3-\sqrt{5}}{2} < a_n < \frac{3+\sqrt{5}}{2}$

Since $a_1=1$ is in our interval we know that $a_{n+1}$ will not jump out of the good interval.

Is this good enough?

Last edited: May 22, 2008