How can this $T(n) = T(n-1)+T(n-2)+3n+1$ non homogenous recurrence relation be solved 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. 
 A: 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.  
A: 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.
A: 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.
A: 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}$.
A: 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
$$
