Induction proof with big O

Question

I'm trying to prove using the induction method, however I'm not able to go forward

Question:

$x_{n+1} \le 2x_n + 3x_{n−1} + n^2 $ , where $x_0 = 1, x_1 = 1$.

Prove that $x_n = O(3.1^n)$.

Appreciate any help,

Answer 1

Hint:

Suppose $x_k \le ab^k$ for $k = n, n-1$.

Then $x_{n+1} \le 2x_n + 3x_{n−1} + n^2 \le 2ab^n + 3ab^{n-1} + n^2 $.

If we can show that $2ab^n + 3ab^{n-1} + n^2 \le ab^{n+1}$, we are done.

This is $ n^2 \le ab^{n+1}-2ab^n - 3ab^{n-1} = ab^{n-1}(b^2-2b - 3) $.

Now use $b^2-2b - 3 =(b-3)(b+1) $ for $b=3.1$ to find an $a$ for which this is true for all $n$.

You can actually do this for any $b > 3$. Do you why this fails for $0 \le b \le 3$?

Note: $b^2-2b-3$ is called the characteristic polynomial of the recurrence. Its roots give important information about the growth of solutions to the recurrence.