# Mathematical induction/recusive sequences - just need a hint

1. Sep 25, 2004

How do I prove by mathematical induction that the sequence given by

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

is increasing?

The difficulty in finding it myself is that recursive sequences are not familiar to me---i.e. usually, I am able do the following steps without a problem:

(A) Show n=1 gives a true statement.
(B) Assume it is true for n=k.
(C) Get to n=k+1 and complete the proof.

... but this is not a regular sequence. Can anyone give me a tip?

2. Sep 25, 2004

### Muzza

Not quite sure what kind of hint you're after... You wish to prove that a_(n + 1) > a_n for all n. The inductive step is basically showing that a_(k + 2) > a_(k + 1) if a_(k + 1) > a_k. If you work with the first inequality, you'll surely find something. Remember that you can relate a number in the sequence to its predecessor, e.g. a_(k + 2) = 3 - 1/a_(k + 1).

3. Sep 25, 2004

### arildno

At n=1, we find a(2)=2>1=a(1), that is, the first step is verified.

Assume a(k)>a(k-1)
Prove that a(k+1)>a(k):

a(k+1)-a(k)=3-1/a(k)-(3-1/a(k-1))=1/a(k-1)-1/a(k)>0, since a(k)>a(k-1)

4. Sep 25, 2004

Oh... I've got it. Thanks.

5. Sep 25, 2004

### modmans2ndcoming

have you shown n=1?also, how does your prof let you play with the equations, does he/she let you pretty much play with them any way that is algebraically sensical or do you have to take a more controlled approach like playing with one side only, etc.?

6. Sep 26, 2004

### arildno

What are you getting at?
I've solely used the definitions of the term in the sequence; I haven't presupposed anything that should be proven

7. Sep 28, 2004

### modmans2ndcoming

to use induction, you show that it it true for n=1 before any other step is taken.

8. Sep 28, 2004

### matt grime

erm, and he did show n=1 is ok, in fact that was the first sentence in his proof.

9. Sep 28, 2004

Sorry for the late reply---I didn't notice my notification was set to weekly.

Anyhow, I have simply shown what I intended to prove to be valid for:
n=1;
n=k;
n=k+1;
Then, it would be true for all n.