Show that $x_{n+2} = x_{n+1} + \frac{x_n}{2^n}$ is a bounded sequence 
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:


*

*What is the kind of the sequence to understand how to search for its kind on the internet (linear/non-linear, homogenous/non-homogenous, ...)

*How do i show that it is bounded using precalculus maths only?

*Is it possible to find its closed form?


Please note this problem is in precalculus even before limits are defined.
 A: 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$$
A: 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$.)
A: 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$.
