Find expression of $c_n$, where $c_n = a_n + b_n$ Given the recurrence relation $a_{n+2} = 3a_{n+1} + 6a_n$ and $b_{n+2} = b_{n+1} + b_n$ I am supposed to find an expression of the recurrence relation for $c_n := a_n + b_n$. I tried to find some form of linear dependence to obtain a recurrence relation for $c_n$ but this did not let me finish.
Appreciate your help!

If I define the generating functions
$$ f(x) = \sum_{n=0}^\infty a_n x^n $$
$$ g(x) = \sum_{n=0}^\infty b_n x^n $$
then
$$ \begin{align*}
 (6x^2 + 3x - 1) f(x) &= \sum_{n=0}^\infty (6 a_n x^{n+2} + 3 a_n x^{n+1} - a_n x^n)\\
 &= -a_0 + (3 a_0 - a_1) x + \sum_{n=2}^\infty (6 a_{n-2} + 3 a_{n-1} - a_n) x^n \\
 &= -a_0 + (3 a_0 - a_1) x
\end{align*} $$
$$ f(x) = \frac{A + Bx}{6x^2 + 3x - 1} $$
$$ \begin{align*}
(x^2+x-1) g(x) &= \sum_{n=0}^\infty (b_n x^{n+2} + b_n x^{n+1} - b_n x^n) \\
&= -b_0 + (b_0-b_1)x + \sum_{n=2}^\infty(b_{n-2}+b_{n-1}-b_n)x^n \\
&= -b_0 + (b_0-b_1)x
\end{align*} $$
$$ g(x) = \frac{C + Dx}{x^2+x-1} $$
The generating function for $c_n$ is $f+g$:
$$ \sum_{n=0}^\infty c_n x^n = \sum_{n=0}^\infty (a_n+b_n) x^n = f(x) + g(x) $$
And that sum is a fraction of polynomials, where the numerator $P(x)$ has degree at most $3$, but its exact form doesn't matter for this purpose:
$$ f(x) + g(x) = \frac{P(x)}{(6x^2+3x-1)(x^2+x-1)} = \frac{P(x)}{6x^4 + 9x^3 - 4x^2 - 4x + 1} $$
$$ \begin{align*}
 P(x) &= (6x^4+9x^3-4x^2-4x+1)(f(x)+g(x)) \\
 &= \sum_{n=0}^\infty (6c_n x^{n+4} + 9c_n x^{n+3} - 4c_n x^{n+2} - 4c_n x^{n+1} + c_n x^n) \\
&= Q(x) + \sum_{n=4}^\infty (6c_{n-4} + 9c_{n-3} -4c_{n-2} - 4c_{n-1} + c_n) x^n
\end{align*} $$
where $Q(x)$ is another polynomial of degree at most $3$ of "left over" terms. The equality forces $P(x) = Q(x)$ and all coefficients in the infinite sum must be zero.
So shifting the index, we get the recurrence relation for all $n \geq 0$:
$$ c_{n+4} = 4c_{n+3} + 4c_{n+2} - 9c_{n+1} - 6c_n $$
