How can this $T(n) = T(n-1)+T(n-2)+3n+1$ non homogenous recurrence relation be solved

Question

How are can the above recurrence relation be solved?

I've reached here: $(x^{2}-x-1)(x-3)^2(x-1)$

And then here:

$$a_n = l_1 \cdot (x_1)^n+l_2 \cdot (x_2)^n+l_3 \cdot (x_3)^n+l_4\cdot n \cdot (x_3)^n+l_5\cdot (x_4)^n$$

And we are given that these: $T(0) = 2, T(1) = 3$

So, for $n = 0$ and $n = 1$ we get two equations but we need 3 more, yet we don't have any more constants.

Answer 1

Rewrite the expression as $$ T_{n+2}=T_{n+1}+T_{n}+3n+7 $$ Now postmultiply by $z^k$ and sum over $k$ to get the generating function $G_{T}(z)=\sum_{k=0}^{\infty}T_k z^k$. Here $$ \sum_{k=0}^{\infty}T_{k+2}z^k = \frac{1}{z^2}\bigg(G(z)-T_0-T_1 z\bigg)\\ \sum_{k=0}^{\infty}T_{k+1}z^k=\frac{1}{z}\bigg(G(z)-T_0 \bigg) $$ Now do the algebra and find the expression with $G(z)$ on the LHS of the expression and $\sum_{k \geq 0}\varphi_k z^k$. The $\varphi_n$ term corresponding to $z^n$ will be the solution.

Answer 2

If you define a vector $\mathbf{U}_{n}$ by $$ \mathbf{U}_{n}=\left( \begin{array} [c]{c}% T\left( n\right) \\ T\left( n-1\right) \\ n\\ 1 \end{array} \right) \text{ }n\geq1 $$ then your recurence relation can be written $$ \mathbf{U}_{n+1}=\mathbf{AU}_{n} $$ where $\mathbf{A}$ is the constant 4x4 matrix $$ \mathbf{A}=\left( \begin{array} [c]{cccc}% 1 & 1 & 3 & 4\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{array} \right) $$ So the problem is equivalent to finding an expression for the matrix powers $\mathbf{A}^{m}$. This should be straightforward via the eigenvalues of $\mathbf{A}$, which are $\lambda$=1 (twice), and $\frac{1\pm\sqrt{5}}{2}$.

Answer 3

You can also solve it the following way:

Step 1: Find one particular $f(n)$ so that

$$f(n)=f(n-1)+f(n-2)+3n+1 \,.$$

If you look fora polynomial $f$, the highest power doesn't cancel so you need to look for some $f(n)=an+b$. Find it.

Step 2: Let $g(n)=T(n)-f(n)$. Then $g(n)$ satisfies the homogeneous recurrence

$$g(n)=g(n-1)+g(n-2) \,.$$

Solve it.

Answer 4

Modify $T$ as follows:

$$ \begin{aligned} T(n) &= T(n-1) + T(n-2) + 3n + 1\\ T(n) + 3n &= T(n-1) + T(n-2) + 6n + 1\\ T(n) + 3n &= T(n-1) + 3n + T(n-2) + 3n + 1\\ T(n) + 3n &= T(n-1) + 3(n-1) + T(n-2) + 3(n-2) + 10\\ T(n) + 3n + 10 &= T(n-1) + [3(n-1) + 10] + T(n-2) + [3(n-2) + 10 ] \end{aligned} $$

So, $S(n) = T(n) + 3n + 10$ satisfies the Fibonacci recurrence.

Answer 5

Use "generatingfunctionology" techniques. Define $G(z) = \sum_{n \ge 0} T(n) z^n$, write your recurrence as: $$ T(n + 2) = T(n + 1) + T(n) + 3 n + 3 $$ Multiply by $z^n$, add for $n \ge 0$. Remember that: $$ \sum_{n \ge 0} (n + 1) z^n = \frac{1}{(1 - z)^2} $$ and you get: $$ \frac{(G(z) - T(0) - T(1) z}{z^2} = \frac{G(z) - T(0)}{z} + G(z) + 3 \cdot \frac{1}{(1 - z)^2} $$ Solve for $G(z)$, expand in partial fractions: $$ G(z) = \frac{2 - 3 z + z^2 + z^3}{1 - 3 z + 2 z^2 + z^3 - z^4} = \frac{4 + 2 z}{1 - z - z^2} - \frac{1}{1 - z} - \frac{1}{(1 - z)^2} $$ We have the last two terms, the first one is for Fibonacci numbers: $$ T(n) = 4 F_{n + 1} + 2 F_n - 1 - (n + 1) = 4 F_{n + 1} + 2 F_n - n - 2 $$