Inhomogeneus recurrence relation $a_{n+1} = 2a_n+3^n+4^n$

Question

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.

Answer 1

$$\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}$)

Answer 2

Just write down the first couple of terms and make a hypothesis that the solutions have the form

$$a_n = 2^n+\sum_{k=0}^{n-1}\left((3^k+4^k)2^{n-1-k}\right).$$

The proof of this formula should be quite easy by induction. Even further, one can simplify it into

$$a_n=2^n+2^{n-1}\frac{(3/2)^n-1}{3/2-1} + 2^{n-1}\frac{2^n-1}{2-1} = 3^n + 4^n/2-2^{n-1}, \quad n\ge 1.$$

Answer 3

Let $G(x)$ be the generating function of the sequence; $ G(x) = \sum\limits_{i=0} a_ix^i $

Then from your recurrence we have

$ \frac{G(x)-1}{x} = 2G(x) + \sum\limits_{i=0} 3^ix^i + 4^ix^i = 2G(x) + \frac{1}{1-3x} + \frac{1}{1-4x}$

Solving for $G(x)$, $$ G(x) = \frac{1}{1-2x} + \frac{x}{1-2x} \left( \frac{1}{1-3x} + \frac{1}{1-4x}\right).$$

Finally, we expand $G(x)$ in powers of $x$ to find $ a_n = \frac{1}{2}(-2^n + 2*3^n + 4^n) $.