7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I've updated my answer with something truly precalculus-friendly. $\endgroup$ Commented Nov 1, 2018 at 9:58
  • $\begingroup$ @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. $\endgroup$ Commented Apr 12, 2023 at 13:59
  • $\begingroup$ @KratosTheFarmer same comment as the previous one + here is a second "false duplicate" (both found using Approach$0$). $\endgroup$ Commented Apr 12, 2023 at 14:01

3 Answers 3

5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – roman
    Commented Nov 1, 2018 at 10:50
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Nov 1, 2018 at 11:13
  • $\begingroup$ 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)$? $\endgroup$
    – roman
    Commented Nov 1, 2018 at 11:19
  • $\begingroup$ Oh, you've expressed $k$ from the inequality... $\endgroup$
    – roman
    Commented Nov 1, 2018 at 11:20
  • $\begingroup$ @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$. $\endgroup$ Commented Nov 1, 2018 at 11:27
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I don't think you can show $e^u \geq 1+u$ without calculus or limits as the OP is asking for $\endgroup$ Commented Nov 1, 2018 at 9:27
  • 2
    $\begingroup$ $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$. $\endgroup$
    – user593746
    Commented Nov 1, 2018 at 9:29
  • 2
    $\begingroup$ @Zvi Isn't this definition derived from Taylor expansion which is after definition of limits and derivatives? $\endgroup$
    – roman
    Commented Nov 1, 2018 at 9:31
  • 2
    $\begingroup$ 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$. $\endgroup$
    – user593746
    Commented Nov 1, 2018 at 9:33
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How did you come up with this $y_n$ ? $\endgroup$ Commented Nov 1, 2018 at 11:37
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Nov 1, 2018 at 11:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .