<s>[INST] Inhomogeneus recurrence relation $a_{n+1} = 2a_n+3^n+4^n$ So this was given in class and the teacher weren't able to solve it, and I was wondering how a solution can be given?

$a_{n+1} = 2a_n+3^n+4^n, \enspace a_0 = 1$

Usually we'd consider the solution $a_n$ to be of the form $a_n = a_n^{(h)}+a_n^{(p)}$, where $a_n^{(h)}$ is a solution to the homogeneous recurrence relation and $a_n^{(p)}$ is a particular solution to the recurrence relation. Thus $a_n^{(h)} = c_1\times 2^n$ and $a_n^{(p)} = c_2(3^n+4^n)$, but this strategy didn't work, as solving for $c_2$ in
$c_2(3^{n+1}+4^{n+1})+c_2(3^n+4^n) = 3^n+4^n$
there doesn't seem to be a way to cancel out the $n$'s this equation. Is there maybe another strategy that would make this possible to solve?
Thanks in advance.
 [/INST] $$\dfrac{a_{n+1}}{2^{n+1}} = \dfrac{a_n}{2^n} + \dfrac{1}{2}(\dfrac{3}{2})^n + \dfrac{1}{2}2^n$$
Let $b_{n+1} = \dfrac{a_{n+1}}{2^{n+1}}$, we have $$b_{n+1} = b_n  + \dfrac{1}{2}(\dfrac{3}{2})^n + \dfrac{1}{2}2^n $$
so $b_n = b_0 + \sum_{k=1}^n\left(\dfrac{1}{2}(\dfrac{3}{2})^k + \dfrac{1}{2}2^k\right)$
Can you go from this?(In general for $a\neq 1$, we have $\sum_{k=1}^n a^k = \dfrac{a-a^{n+1}}{1-a}$)
</s>