Finding bounds for recurrence relation

Question

Prove that for the recuurence relation $f(n) = 2f(n-1) + f(n-2)$

with the starting values: f(1) = 1, f(2) = 6, $\forall n \ge 2$

$$(7/3)^n \le f(n) \le (5/2)^n$$

I tried using the fact that $f(n) \gt 2f(n-1)$

Answer 1

For $n = 1$ you get $7/3 \le 1 \le 5/2$. This is false. So the claim is wrong.

If you want bounds, try looking for an upper bound of the form $f(n) \le a_2 \cdot b^n$, substitute into the recurrence and see what happens:

$\begin{align*} f(n) &= 2 f(n - 1) + f(n - 2) \\ &\le 2 a_2 b^{n - 1} + a_2 b^{n - 2} \\ &= a_2 b^{n - 2} (2 b + 1) \end{align*}$

We want $a_2 b^n \le a_2 b^{n - 2} (2 b + 1)$, i.e. $b^2 = 2 b + 1$, positive zero is $1 + \sqrt{2} < 5/2$. Adjust $a_2$ to satisfy the bound for the initial values, i.e. $1 \le a_2 (1 + \sqrt{2})$ and $6 \le a_2 (1 + \sqrt{2})^2 = a_2 (3 + 2 \sqrt{2})$. The first gives $a_2 \ge \sqrt{2} - 1$, the second one $a_2 \ge 18 - 12 \sqrt{2}$. The later is larger, a bit more than 1. Thus we can say $f(n) \le (5/2)^n$

Do the same, but looking for a lower bound. As above, for $f(1) = 1$ you get $a_1 b < 1$, $a_1 < 2/5$, bound $b < 12/5$, giving $2/5 \cdot (12/5)^n < f(n)$; it would be simpler to just say $(2/5)^n \le f(n)$.

The bounds can be checked by induction.