7

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.

roman
  • 5,391

3 Answers3

5

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

Gabriel Romon
  • 35,428
  • 5
  • 65
  • 157
  • 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 – roman Nov 01 '18 at 10:50
  • 1
    @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. – Gabriel Romon Nov 01 '18 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)$? – roman Nov 01 '18 at 11:19
  • Oh, you've expressed $k$ from the inequality... – roman Nov 01 '18 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$. – Gabriel Romon Nov 01 '18 at 11:27
4

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

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

achille hui
  • 122,701
  • How did you come up with this $y_n$ ? – Gabriel Romon Nov 01 '18 at 11:37
  • 1
    @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. – achille hui Nov 01 '18 at 11:42