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 $$
If $a_{n+2}=3a_{n+1}+6a_n$ iff $a_n=d_1r_1^n+d_2r_2^n$, where $r_1,r_2$ are the roots of $x^2-3x-6=0$, and $b_{n+2}=a_{n+1}+a_n$ iff $b_n=d_3r_3^n+d_4r_4^n$, where $r_3,r_4$ are the roots of $x^2-x-1=0$, and $d_1,d_2,d_3,d_4$ are arbitrary constants.
Hence, $$ c_n=a_n+b_n=d_1r_1^n+d_2r_2^n+d_3r_3^n+d_4r_4^n $$ which holds iff $$ c_{n+4}=4c_{n+3}+4c_{n+2}-9c_{n+1}-6c_n $$ since $r_1,r_2,r_3,r_4$ are the roots of $$ (x^2-3x-6)(x^2-x-1)=x^4-4x^3-4x^2+9x+6=0. $$
Note. The following result is not hard to prove:
Lemma. If the roots of $$p(x)=x^k-s_{1}x^{k-1}-s_{2}x^{k-2}-\cdots-s_k$$ are the distinct complex numbers $r_1,\ldots,r_k$ then $$ a_{n+k}=s_{1}a_{n+k-1}+s_{2}a_{n+k-2}+\cdots+s_ka_n $$ iff $a_n=d_1r_1^n+\cdots+d_kr_k^n$, for some constants $d_1,\ldots,d_k$.
Using that $\,a_{n+2} - 3a_{n+1} - 6a_n = 0\,$ and $\,b_{n+2} = b_{n+1} + b_n\,$:
$$ \require{cancel} \begin{align} c_{n+2}-3c_{n+1}-6c_n &= \cancel{(a_{n+2}-3a_{n+1}-6a_n)} + (b_{n+2}-3b_{n+1}-6b_n) \\ &= -2b_{n+1} - 5 b_n \end{align} $$
Then, using that $\,b_{n+2} - b_{n+1} - b_n = 0\,$:
$$ \begin{align} (c_{n+4} - 3c_{n+3}-6c_{n+2}&) - (c_{n+3}-3c_{n+2}-6c_{n+1}) - (c_{n+2}-3c_{n+1}-6c_n) \\ &=\; -2\cancel{(b_{n+3}-b_{n+2}-b_{n+1})} - 5\bcancel{(b_{n+2}-b_{n+1}-b_{n})} \\ &= 0 \end{align} $$ $$ \iff c_{n+4} - 4c_{n+3}-4c_{n+2}+9 c_{n+1}+ 6 c_n = 0 $$
