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

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$$

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$.)

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$.