Problem 1608

1. Define the sequence transformation:
Given the sequence $a_n$ defined by:
$$a_0 = 2 \quad \text{and} \quad a_n = \frac{2a_{n-1} + 1}{a_{n-1} + 2} \quad \text{for} \quad n \geq 1$$
we introduce a new sequence $c_n$ such that:
$$c_n = \frac{1}{a_n - 1}$$
This transformation is valid since $a_n > 1$ for all $n$.

2. Transform the recurrence relation:
Using the definition of $c_n$, we can express $a_n$ in terms of $c_n$:
$$a_n = 1 + \frac{1}{c_n}$$
Substitute $a_n$ into the recurrence relation:
$$a_n = \frac{2a_{n-1} + 1}{a_{n-1} + 2}$$
becomes:
$$1 + \frac{1}{c_n} = \frac{2 \left(1 + \frac{1}{c_{n-1}}\right) + 1}{1 + \frac{1}{c_{n-1}} + 2}$$
Simplify the right-hand side:
$$1 + \frac{1}{c_n} = \frac{2 + \frac{2}{c_{n-1}} + 1}{1 + \frac{1}{c_{n-1}} + 2} = \frac{3 + \frac{2}{c_{n-1}}}{3 + \frac{1}{c_{n-1}}}$$
Multiply numerator and denominator by $c_{n-1}$:
$$1 + \frac{1}{c_n} = \frac{3c_{n-1} + 2}{3c_{n-1} + 1}$$
Subtract 1 from both sides:
$$\frac{1}{c_n} = \frac{3c_{n-1} + 2}{3c_{n-1} + 1} - 1 = \frac{3c_{n-1} + 2 - (3c_{n-1} + 1)}{3c_{n-1} + 1} = \frac{1}{3c_{n-1} + 1}$$
Therefore:
$$c_n = 3c_{n-1} + 1$$

3. **Solve the recurrence relation for $c_n$:**
The recurrence relation $c_n = 3c_{n-1} + 1$ with $c_0 = 1$ is a linear non-homogeneous recurrence relation. To solve it, we first solve the homogeneous part:
$$c_n^{(h)} = A \cdot 3^n$$
For the particular solution, we assume $c_n^{(p)} = B$. Substituting into the recurrence relation:
$$B = 3B + 1 \implies B = -\frac{1}{2}$$
Therefore, the general solution is:
$$c_n = A \cdot 3^n - \frac{1}{2}$$
Using the initial condition $c_0 = 1$:
$$1 = A \cdot 3^0 - \frac{1}{2} \implies A = \frac{3}{2}$$
Thus:
$$c_n = \frac{3}{2} \cdot 3^n - \frac{1}{2} = \frac{3^{n+1} - 1}{2}$$

4. **Express $a_n$ in terms of $c_n$:**
Recall that:
$$a_n = 1 + \frac{1}{c_n}$$
Substituting $c_n$:
$$a_n = 1 + \frac{2}{3^{n+1} - 1}$$

5. **Prove the inequality $1 < a_n < 1 + \frac{1}{3^n}$:
- Lower bound:**
$$a_n = 1 + \frac{2}{3^{n+1} - 1} > 1$$
since $\frac{2}{3^{n+1} - 1} > 0$.

- Upper bound:
$$a_n = 1 + \frac{2}{3^{n+1} - 1} < 1 + \frac{1}{3^n}$$
We need to show:
$$\frac{2}{3^{n+1} - 1} < \frac{1}{3^n}$$
Cross-multiplying:
$$2 \cdot 3^n < 3^{n+1} - 1$$
Simplifying:
$$2 \cdot 3^n < 3 \cdot 3^n - 1 \implies 2 \cdot 3^n < 3 \cdot 3^n - 1 \implies 2 < 3 - \frac{1}{3^n}$$
which is true for all $n \geq 1$.

$\blacksquare$