mathematical induction/recusive sequences - just need a hint

[thiago_j]

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?

[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).

[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)

[thiago_j]

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

[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.?

[arildno]

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.?
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 :confused:

[modmans2ndcoming]

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

[matt grime]

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

[thiago_j]

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.

Well, The difficulty I had has already been resolved with your assistance, guys.

Thank you very much indeed. :smile: