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.
 A: 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.
A: 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. 
A: 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. 
