Show that $x_{n+2} = x_{n+1} + \frac{x_n}{2^n}$ is a bounded sequence

Question

Given a sequence: $$ \begin{cases} x_{n+2} = x_{n+1} + \frac{x_n}{2^n}\\ x_1 = 1\\ x_2 = 1 \\ n \in \mathbb N \end{cases} $$ Show that $\{x_n\}$ is a bounded sequence.

This recurrence feels like a bad joke for precalculus level. Is it possible to show that it is bounded and find some estimations for the bounds. Clearly $x_n$ is greater than $0$. ${1\over 2^n}$ coefficient makes it hard to find closed form of the recurrence.

I've expanded a few first terms to find a pattern but it doesn't look like it exists:

$$ x_n = {1}, {1}, {3\over 2}, {7\over 4}, {31\over 16}, {131\over 64}, {1079\over 512}, {8763\over 4096}, \ {141287\over 65536}, {2269355\over 1048576} \dots $$

Denominator is in some form of $2^{k_n}$ from which i've figured out $k_n$ is in the form:

$$ k_n = \left\lfloor {n^2\over 4}\right\rfloor $$

So the denominator is in the form:

$$ d_n = 2^{\left\lfloor {n^2\over 4} \right\rfloor} $$

The sequence seems to be bounded since computing a few terms shows it tends to some number:

$$ M = 2.1726687\dots $$

I have these questions in mind regarding the given sequence:

1. What is the kind of the sequence to understand how to search for its kind on the internet (linear/non-linear, homogenous/non-homogenous, ...)
2. How do i show that it is bounded using precalculus maths only?
3. Is it possible to find its closed form?

Please note this problem is in precalculus even before limits are defined.

Answer 1

It is clear that $\forall n\geq 1, x_n\geq 0$. Since $\displaystyle \forall n\geq 1, x_{n+2} = x_2+\sum_{k=1}^n \frac{x_k}{2^k}$, it suffices to prove that $\displaystyle \sum_{k}\frac{x_k}{2^k}$ converges. Because of the $2^n$ in the denominator, any crude polynomial bound on $x_n$ will do.

Let us prove by strong induction that $\forall n\geq 1, x_n\leq n$. It's trivial for $n=1,2$. Assume that for all $k\leq n-1, x_k\leq k$. For $n\geq 3$, $$x_n=1+\sum_{k=1}^{n-2} \frac{x_k}{2^k}\leq 1+\max_{i\leq n-2}x_i \sum_{k=1}^{n-2} \frac{1}{2^k} \leq 1+\max_{i\leq n-2}x_i\leq 1+n-2\leq n$$

This bound yields convergence of $\displaystyle \sum_{k}\frac{x_k}{2^k}$, which in turn implies that $x_n$ converges (hence it's bounded).

---

For a precalculus-friendly version, it suffices to prove that $\displaystyle \sum_{k=1}^n \frac{x_k}{2^k}$ is bounded in $n$, and by what precedes, it suffices to prove that $\displaystyle \sum_{k=1}^n \frac{k}{2^k}$ is bounded above in $n$. The elementary Bernoulli's inequality yields $k\leq 2\left( \left(1+\frac 12 \right)^k-1\right)\leq 2 \left(1+\frac 12 \right)^k$. Thus $$\sum_{k=1}^n \frac{k}{2^k}\leq 2 \left( \sum_{k=1}^n \left(\frac{3}{4}\right)^k\right)\leq 2\cdot 3\leq 6$$

Answer 2

First, note that $$f(u)=e^{-u}\left(1+u\ e^{-2u}\right)$$ satisfies $f(u)\leq 1$ for all $u\geq 0$. This is because $$e^{u}\geq 1+u \geq 1+u\ e^{-2u}$$ for every $u\geq 0$. Note that $x_1=1=e^{2-\frac{4}{2^1}}$ and $x_2=1<e=e^{2-\frac{4}{2^2}}$. Now, for $n\geq 3$, suppose that $x_k<e^{2-\frac{4}{2^k}}$ for all $k=1,2,\ldots,n-1$. Then, $$x_{n}=x_{n-1}+\frac{x_{n-2}}{2^{n-2}}<e^{2-\frac{4}{2^{n-1}}}+\frac{e^{2-\frac{4}{2^{n-2}}}}{2^{n-2}}=e^{2-\frac{4}{2^n}}e^{-\frac{4}{2^n}}\left(1+\frac{1}{2^{n-2}}e^{-\frac{8}{2^n}}\right),$$ so $$x_n<e^{2-\frac{4}{2^n}}f\left(\frac{4}{2^n}\right)<e^{2-\frac{4}{2^n}}.$$ In particular, we have $x_n<e^2$ for every $n$. (We can also show that $x_n\leq e^{1-\frac{4}{2^n}}$ for all $n\geq 2$. So, in fact, $x_n<e$ for all $n$.)

Answer 3

Consider the auxillary sequence $\displaystyle\;y_n = \frac{x_n}{1-2^{2-n}}$ defined for $n >2$.

It is clear all $y_n$ are positive. Notice

$$\begin{align} y_{n+2} &= \frac{1}{1-2^{-n}}\left[(1-2^{1-n})y_{n+1} + 2^{-n}(1 - 2^{2-n}) y_n\right]\\ &\le \frac{1}{1-2^{-n}}\left[(1-2^{1-n})y_{n+1} + 2^{-n} y_n\right]\\ &\le \frac{1}{1-2^{-n}}\left[(1-2^{1-n}) + 2^{-n}\right]\max( y_n, y_{n+1} )\\ & = \max(y_n,y_{n+1}) \end{align} $$ We find for all $n > 4$, $$x_n < y_n \le \max(y_{n-1},y_{n-2}) \le \max(y_{n-2},y_{n-3}) \le \cdots \le \max(y_3,y_4) = 3$$ Since $x_1,x_2,x_3,x_4 < 3$, we find $x_n < 3$ for all $n$.