Recursive sequence problem: proofs by mathematical induction

Guys,

I'm trying to prove by induction that the sequence given by
[tex] a_{n+1}=3-\frac{1}{a_n} \qquad a_1=1 [/tex] is increasing and [tex] a_n < 3 \qquad \forall n .[/tex]

Is the following correct? Thank you. :smile:

Task #1.
[tex] n = 1 \Longrightarrow a_2=2>a_1 [/tex] is true.
We assume [tex] n = k [/tex] is true. Then,
[tex] 3-\frac{1}{a_{k+1}} > 3-\frac{1}{a_k} [/tex]
[tex] a_{k+2} > a_{k+1} [/tex] is true for [tex] n=k+1 [/tex].
This shows, by mathematical induction, that
[tex] a_{n+1} > a_{n} \qquad \forall n . [/tex]

Task #2
We already know that
[tex] a_1 < 3 [/tex] is true.
We assume [tex] n=k [/tex] is true. Then,
[tex] a_k < 3 [/tex]
[tex] \frac{1}{a_k} > \frac{1}{3} [/tex]
[tex] -\frac{1}{a_k} < -\frac{1}{3} [/tex]
[tex] 3-\frac{1}{a_k} < 3-\frac{1}{3} [/tex]
[tex] a_{k+1} < \frac{8}{3} < 3 [/tex]
[tex] a_{k+1} < 3 [/tex] is true for [tex] n = k+1 [/tex]. Thus,
[tex] a_{n} < 3 \qquad \forall n . [/tex]
 
Last edited by a moderator:

fresh_42

Mentor
Insights Author
2018 Award
10,413
7,110
This is not written very well and some indices are wrong.
For the first step with ##n=1## we have ##3 > 2 = a_2 = 3- \frac{1}{a_1} > 1 = a_1 > 0##.
Let us next assume we have shown ##3 > a_n > a_{n-1} > 0##.

[Here we have to write the calculation 'backwards'.]
$$
3 > 3- \frac{1}{a_n} = a_{n+1} \stackrel{(1)}{>} 3 - \frac{1}{a_{n-1}} = a_n > 0
$$
where ##(1)## follows from: ##a_n > a_{n-1} \Longrightarrow \frac{1}{a_{n-1}} > \frac{1}{a_n} \Longrightarrow -\frac{1}{a_n} > -\frac{1}{a_{n-1}}##
 
32,487
4,222
In addition to fresh_42's comments, this line:
We assume [itex] n=k [/itex] is true. Then,
[itex] a_k < 3 [/itex]
You don't "assume" that n = k is true -- you assume that the proposition ##a_n < 3## is true for n = k.
 

Want to reply to this thread?

"Recursive sequence problem: proofs by mathematical induction" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top