Find a closed formula given by the recurrence.

Question

Find a closed formula for $d_n$, where {$d_n$} is the sequence given by the recurrence: $d_n = 4d_{n−1} − 4d_{n−2} − 2n$, and $d_0 = 0, d_1 = 1$.

My attempt: Since this is a e.g.f I multiply everything by $\frac{x^n}{n!}$. What do I do from here?

Answer 1

We have, $$\theta_n = 4\theta_{n-1} - 4\theta_{n-2} - 2n\ \ \forall \ n>1 $$ $$\theta_0=0,\theta_1=1$$

let, $$\alpha_n = \theta_n - 2\theta_{n-1}\ \ \forall n\ge1$$ $$\Rightarrow\ \ \alpha_n=2\alpha_{n-1}-2n\ \ \forall n\gt1\ \ \&\ \alpha_1=1 $$ which can be solved to get, $$\alpha_n = 2(n+2)\ -\ 5\cdot2^{n-1}$$ $$\Rightarrow\ \ \theta_n = 2\theta_{n-1}\ +\ 2(n+2)\ -\ 5\cdot2^{n-1}$$ $$\Rightarrow\ \ \theta_n = (16-5n)\cdot2^{n-1}\ -\ 2(n+4)$$

PS: Both recurrences are of the form $\ t_n=2\cdot t_{n-1}\ +\ f(n)\ $which can be solved easily.