Find 2nd order recurrence relation with given solution Let $(a)_{n\geq0}$ with $a_n=a_{n-1}+6a_{n-2}$ and $a_0=1, a_1=4$.
The sequence $(b)_{n\geq0}$ shall satisfy $$b_n=\sum_{k=0}^{n}\binom{n}{k}a_k$$
I have to find a 2nd order recurrence relation which has $(b_n)_{n\geq0}$ as solution. How does one approach this task?
I first solved the recurrence realtion for $(a_n)$:
$$a_n=\frac{6\cdot3^n+(-1)^{n+1}2^n}{5}$$
But how do I proceed?

For every $n \geq 0$, one has
\begin{align*} b_n&=\sum_{k=0}^{n}\binom{n}{k}a_k\\
&=\sum_{k=0}^{n}\binom{n}{k}\frac{6\cdot3^k+(-1)^{k+1}2^k}{5}\\
&=\frac{6}{5}\sum_{k=0}^{n}\binom{n}{k}3^k  - \frac{1}{5}\sum_{k=0}^{n}\binom{n}{k}(-2)^k\\
&=\frac{6}{5}(3+1)^n  - \frac{1}{5}(1-2)^n\\
&=\frac{6 \cdot 4^n - (-1)^n}{5}\\
\end{align*}
which satisfies the recursion
$$\boxed{b_{n+2} = 3b_{n+1} + 4b_n}$$
