Can someone explain me this: $T(n)=-T(n-1)+2\times T(n-2)+3 \times 2^n+n$
According to Wolfram Alpha the answer is:
$$ T(n) = c_1(-2)^n + c_2 + \dfrac{1}{18}n(3n + 7) + 3 \times 2^n - \dfrac{5}{27}$$
but can someone explain me how it is calculated? I know the basic algorithm, but don't know what to do with that $3 \times 2^n+n$
You can split this into three pieces $T(n)=P(n)+Q(n)+R(n)$ where
$$P(n)+P(n-1)-2P(n-1)=0$$$$Q(n)+Q(n-1)-2Q(n-1)=3\times 2^n$$$$R(n)+R(n-1)-2R(n-1)=n$$
You find $$P(n)=a(-2)^n+b \text { (where this is in fact }b\cdot 1^n)$$
The test solution for the linear recurrence $L(n)=s(n)t^n$ where $s$ is a polynomial in $n$ is $n^ru(n)t^{n}$ where $u(n)$ is a polynomial of the same degree as $s(n)$ and $r$ is the multiplicity of $t$ as a root of the associated equation, which in this case is $t^2+t-2=0$ with roots $1, -2$.
So for $Q$ we try $n^0\times d\times 2^n=d\cdot 2^n$
For $R$ noting that $1$ is a root of order $1$ we try $n(en+f)1^n$
