Sequence $< x_n >$ be defined by $x_1=1; x_2=2;$ and for $n \geq 3$ by $x_n =(x_{n-1} + x_{n-2}) / 2$. Prove $1 \leq x_n \leq 3$

Question

Let the sequence $< x_n >$ be defined by $x_1=1; x_2=2;$ and for $n \geq 3$ defined recursively by $x_n =(x_{n-1} + x_{n-2}) / 2$. Prove that $1 \leq x_n \leq 3$ for all $n \in \mathbf{N}$.

I know I need to use strong induction.

The sequence goes $x_1 = 1$; $x_2 = 2$; $x_3 = \frac{3}{2}$; $x_4 = \frac{7}{4}$; $x_5 = \frac{13}{8}$; $x_6 = \frac{27}{16}$; ...

If we build up the inequality with strong induction we get:

$1 \leq x_{ (n + 1) -1} \leq 3$

$1 \leq x_{n} \leq 3$

$1 + x_{ (n + 1) - 2} \leq x_{n} + x_{ (n + 1) - 2} \leq 3 + x_{ (n + 1) - 2}$

$1 + x_{n - 1} \leq x_{n} + x_{n - 1} \leq 3 + x_{n - 1}$

$\frac{1 + x_{n - 1}}{2} \leq \frac{x_{n} + x_{n - 1}}{2} \leq \frac{3 + x_{n - 1}}{2}$

Where do I go from here? I'm wondering how to prove the inequality in a simple straight forward fashion.

Am I even approaching this correctly? Maybe I should be deriving the series formula and then plugging in the formula for $x_n$ with n and n-1.

Thank you.

Answer 1

The average of two numbers will be somewhere between the two numbers. $x_4$ will be between $1.5$ and $2$, the average of that number and $1.5$ will be greater than 1.5, but less than $x_4$. It could be written more mathematically though. Think of it as sum of an alternating series.

Answer 2

Hypothesis: Assume $1 \leq x_z \leq 3$. for all $z$ from $1$ to $n$.

Inductive step: $1 = \frac{1+1}{2} \leq \frac{x_{n}+x_{n-1}}{2}=x_{n+1} \leq \frac{3+3}{2}=3$.

Answer 3

All averages of elements in [1,2] are in [1,2]. Thus each element is in [1,2].