# Proof that a sequence is bounded

I would like to show that the following sequence is bounded: $$c_{n+1}=c_{n-1}+\frac{c_n}{2^{\frac{n}{2}-1}},$$ with $c_0=1$, $c_1=2^{3/4}$. I don't think the initial values are important in any way; I mention them for completeness. I am also interested, rather generally, in the situation where $$c_{n+1}=c_{n-1}+\frac{c_n}{f_n}.$$ That is, what kind of restrictions on $f_n$ force $c_n$ to be bounded?

Any help would be appreciated.

-

For $n\geq 6$ we have $2^{n/2-1} \geq 4$ so $c_{n+1}\leq c_{n-1} + c_n/4.$ We only care about proving boundedness so the first few terms don't matter, assume this inequality holds from the start. Then certainly $c_n\leq a_n$ where $a_n$ is the sequence with the same initial conditions but where we define $a_{n+1}=a_{n-1}+a_n/4$, i.e where the inequality is precise. This is of the form of a first order linear homogeneous recurrence, which has many elementary methods of solution. We see $$a_n = \alpha \left( \frac{1-\sqrt{65}}{8} \right)^n + \beta \left( \frac{1+\sqrt{65}}{8} \right)^n$$

where $\alpha$ and $\beta$ are some (irrelevant) constants determined by the initial conditions. $|1-\sqrt{65}|<8$ so the first term eventually becomes $0$ and $(1+\sqrt{65})/8 < 5/4$ so eventually $c_n\leq a_n < (5/4)^n.$

This means that $c_{n+1} < c_{n-1} + 2 \gamma^n$ where $\gamma = \frac{5}{4\sqrt{2}} <1.$

Repeatedly applying this gives $$c_{n+1} < c_{n-1} + 2 \gamma^n$$ $$< c_{n-3} + 2\gamma^{n-2} + 2\gamma^n$$

$$< c_{n-5}+2(\gamma^{n-4}+\gamma^{n-2}+\gamma^n)$$

$$\vdots$$

$$< c_0 +2M$$

where $M$ is finite because the $\gamma$ sum is a geometric progression with ratio less than $1.$

So $c_n$ is bounded.

-
This proves that is bounded from above... I'm not sure if this argument would work for the lower bound. I have to think about it. – bartgol Jul 3 '12 at 12:41
Bounded from below by zero, no? – Gerry Myerson Jul 3 '12 at 12:42
@bartgol If both initial terms are positive, the recurrence shows every term must be positive, so bounded from below by 0. If both initial terms are negative, simply switching $c_n$ to $-c_n$ and applying the same argument shows $c_n$ will be bounded from below by some negative number and from above by $0$. If the initial terms are of opposite signs, some more elementary but annoying similar estimates to the ones I've made will show the sequence is bounded from below by some negative number and from above by some positive number. – Ragib Zaman Jul 3 '12 at 12:50
@Zaman: you are right. – bartgol Jul 3 '12 at 13:12

Initial values ARE important. Think of this as a (time-discrete) dynamical system. The system might be globally asymptotically stable for some choices of $f_n$, but not for others. Now, in your first example, the exponential behavior of $f_n$ actually makes the sequence bounded.

For the general case, I would like to use induction. It would be great to be able to prove that if $M_1\leq c_i \leq M_2$, $i=n,n-1$, then $M_1\leq c_{n+1} \leq M_2$. By induction, this would give the boundedness of the whole sequence. Unfortunately I don't think this is possible, since one of the bounds would require $f_n<0$ and the other $f_n>0$.

But we can try this way. Assume again $M_1\leq c_i \leq M_2$ for $i=n,n-1$. If we can prove that

$$M_1-a_n\leq c_{n+1}\leq M_2+b_n$$

with $a_n,b_n\geq 0$

$$\sum_{n=0}^\infty a_n<\infty\qquad \sum_{n=0}^\infty b_n<\infty$$

then we still have boundedness for the sequence. If you do the calculations, you find out that what you need is

$$-a_n\leq\frac{1}{f_n}\leq b_n$$

So we can say that the sequence is bounded if

$$\sum_{n=0}^\infty \frac{1}{f_n}$$ is absolutely convergent. I don't know if this condition is also necessary. My guess is that this condition is necessary if you want global convergence (that is, regardless of the initial condition), while it might not be necessary for some $f_n$ and some particular choice of the initial conditions.

-
Thanks. My comment on the insignificance of the initial values was meant only for this particular choice of $f_n$, i.e. $f_n=2^{-1+\frac{n}{2}}$. I think whatever the initial values are in this case (both positive), it will turn out that $c_n$ is bounded. – the_fox Jul 3 '12 at 13:34
It is, since the series of $2^{-1+n/2}$ is absolutely convergent. – bartgol Jul 4 '12 at 13:37

Let's rewrite the original sequence as follows:

$$(c_{n+1}-c_{n}) + (c_{n}-c_{n-1}) =\frac{c_n}{f_n}$$

Let's denote an asymptotic term of this sequence by $y\sim c_n \,(\text{as}\,n \to \infty )$. Then we can write the following approximate differential equation:

$$2\frac{dy}{dn}=\frac{y}{f_n}$$ A general solution of this diff.eq. is

$$c_n\sim y=const\,e^{\int\frac{dn}{2f_n}}$$ In the particular case $f_n=2^{\frac{n}{2}-1}$ we have:

$$c_n\sim y= const\,e^{-\frac{1}{2^{\frac{n}{2}-1}\ln 2}}$$ So, in given case, $c_n$ is bounded, indeed.

-
That's a nice argument! – the_fox Jul 5 '12 at 21:42