Finding Close Form For Recurrence Relation

Question

Find a closed form for the following recurrence relation:

$\begin{cases} C_n=3C_{n-1}+n+2\\ C_0=0\\ \end{cases}$

So we start with a guess $D_n=C_n+an+b\iff C_n=D_n-an-b$

substituting to the equations gives

$D_n-an-b=3(D_{n-1}-a(n-1)-b)+n+2\iff \\ \iff D_n=3D_{n-1}+n(a-3a+1)+(3a-3b+b+2)$

taking

$\begin{cases} a-3a+1=0\iff a=\frac{1}{2}\\ 3a-3b+b+2=0 \iff -2b=-3/2-2\iff b=\frac{7}{4}\\ \end{cases}$

So $C_n=D_n-\frac{1}{2}n-\frac{7}{4}$

How to continue from here?

Answer 1

Hint:

Just like linear differential equations, the solutions of linear recurrence relations are the sum of one particular solution, which you've found, and the general solution of the associated homogeneous recurrence relation: $$ C_n=3C_{n-1}. $$

Answer 2

Put $C_n=D_n-\frac{1}{2}n-\frac{7}{4}$ in to $$C_n=3C_{n-1}+n+2$$ and solve it on $D_n$...