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:

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.

• I've updated my answer with something truly precalculus-friendly. Commented Nov 1, 2018 at 9:58
• @MartinR I cannot see how that question was solved by this "duplicate", which seems to only prove the existence of a limit but not give its value. Commented Apr 12, 2023 at 13:59
• @KratosTheFarmer same comment as the previous one + here is a second "false duplicate" (both found using Approach$0$). Commented Apr 12, 2023 at 14:01

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

• Thank you for your answer. Could you please explain why $\sum_{k=1}^n {k \over 2^k} < M \implies \sum_{k=1}^n {x_k \over 2^k} < M$. And also how you then switch to Bernoulli's. I've just found $\sum_{k=1}^n {k \over 2^k} = \frac{2^{n+1}-2 -n}{2^n}$ but don't see how it is followed with Bernoulli's Commented Nov 1, 2018 at 10:50
• @roman Since $\forall k, x_k\leq k$, $\sum_{k=1}^n {x_k \over 2^k}\leq \sum_{k=1}^n {k \over 2^k} < M$. Bernoulli's inequality says that $\left(1+\frac 12\right)^k\geq 1+\frac k2$. Since thr RHS is greater than $\frac k2$ you get the bound I used. Commented Nov 1, 2018 at 11:13
• Thanks, now i understand what $x_k \le k$ implies. But how you arrived at $k \le 2\left(\left(1+{1\over 2}^k\right) - 1 \right)$? Commented Nov 1, 2018 at 11:19
• Oh, you've expressed $k$ from the inequality... Commented Nov 1, 2018 at 11:20
• @roman $k \le 2\left(\left(1+{1\over 2}\right)^k - 1 \right)$ is obtained from $\left(1+\frac 12\right)^k\geq 1+\frac k2$. Commented Nov 1, 2018 at 11:27

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. Now, for $$n\geq 3$$, suppose that $$x_k for all $$k=1,2,\ldots,n-1$$. Then, $$x_{n}=x_{n-1}+\frac{x_{n-2}}{2^{n-2}} so $$x_n In particular, we have $$x_n 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 for all $$n$$.)

• I don't think you can show $e^u \geq 1+u$ without calculus or limits as the OP is asking for Commented Nov 1, 2018 at 9:27
• $e^u$ is defined as $1+u+\frac{u^2}{2!}+\ldots$, so it is certainly $\geq 1+u$ for $u\geq 0$. I don't need anything apart from the definition of $e^u$.
– user593746
Commented Nov 1, 2018 at 9:29
• @Zvi Isn't this definition derived from Taylor expansion which is after definition of limits and derivatives? Commented Nov 1, 2018 at 9:31
• In most books I use, $e^u$ is a priori defined as that series. Then, you show that this series obeys certain laws you know for taking powers, like $e^{a+b}=e^ae^b$.
– user593746
Commented Nov 1, 2018 at 9:33

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

• How did you come up with this $y_n$ ? Commented Nov 1, 2018 at 11:37
• @GabrielRomon $x_n$ is increasing towards some bound and the error behaves like $2^{-n}$. So I attempt to find a bound for $x_n$ of the form $M (1 - a 2^{-n})$. After I work out what $a$ should be and simplify the proof, the $y_n$ falls out during the process. Commented Nov 1, 2018 at 11:42