So I found this exercise in my Analysis book:
For each sequence {$a_n$} defined recursively, determine the limiting value, provided that it exists. Prove your conclusion.
(a) $a_1=1$ and $a_{n+1}=3a_n-1$
(b) $a_1=2$ and $a_{n+1}=\frac{1}{a_n^2}$
Now take a look at (a): Clearly {$a_n$} is increasing (can be proven by induction). However it seems that {$a_n$} will diverge to infinity.
I've considered various ways of proving this but I think they're all a bit messy.
1) Notice that the difference $a_n-a_{n-1}$ is a positive integer value, and therefore greater or equal to 1 for every step. That means that we state a contradiction proof for the unboundedness of {$a_n$}. Namely: state that there is an $M$ such that every $a_n \le M$. Then take $c=M-a_n$. Since $a_n-a_{n-1} \ge 1$, we can state $a_{n+c+1} \ge a_n+c+1 = M+1 > M$ and that therefore there is no upperbound $M$ and $a_n-a_{n-1}$ diverges.
I found this proof to be a bit messy and I don't think it can be used very generally, since the increasement between steps doesn't always have to be so constant.
2) Perhaps one can find a closed expression for {$a_n$}? I've tried but could not come up with one.
3) Taking limits gives us the the equation: $A=3A-1$ which leads us to a limit $A=1/2$. Now since {$a_n$} is increasing, and $1/2$ is smaller than the smallest term, that sounds very wrong of course. Perhaps this could be used to prove that there is no value $A$ to which {$a_n$} converges, and that therefore {$a_n$} diverges?
Now for my other question (b): Writing out the first values of {$a_n$} leads me to think that {$a_n$} is oscillating, and diverging to infinity. However, the oscillating makes that {$a_n$} is not monotone. It seems that the odd values of {$a_n$} diverge into infinity and the even values of {$a_n$} diverge to 0. Should I proof these two separately and then conclude that {$a_n$} as a whole diverges, because 'a part of {$a_n$}' diverges? And if so, how would I write this out formally?
Thanks in advance for your help.
For (a), we can set up an induction. We have $a_1\ge 1.$ Suppose $a_n \ge n.$ Then
$$a_{n+1} = 3a_n — 1 \ge 3n -1.$$
Verify that $3n -1 \ge n+1$ for all $n$ (you don't need induction for that). So we have $a_{n+1}\ge n+1.$ Thus, by induction, we have $a_n \ge n$ for all $n.$ This shows $a_n \to \infty.$
Hint for (b): From $a_{n+1} = a_n^{-2},$ verify that $a_n = 2^{(-2)^{n-1}}$ for every $n.$ See where that takes you.