Solving non homogenous recurrence relation

Question

Find all solutions of the recurrence relation $$a_n = 2a_{n-1}+ 3^n$$

The $3^n$ is really throwing me off.

Answer 1

Well, compute a few terms:

$$a_0 = a_0.$$

$$a_1 = 2 a_0 + 3.$$

$$a_2 = 4 a_0 + 3 \times 2 + 3^2.$$

$$ a_3 = 8 a_0 + 3 \times 4 + 3^2 \times 2 + 3^3.$$

So, a reasonable guess is:

$$a_n = 2^n a_0 + \sum_{i=1}^n 3^i 2^{n-i} = 2^n a_0 + 2^n \sum_{i=1}^n (3/2)^i.$$

You should be able to prove this by induction.

Answer 2

$$a_n = 2a_{n-1}+ 3^n$$ Using generating functions $$f(x)=\sum_{n=0}^{\infty}a_nx^n=\sum_{n=0}^{\infty}(2a_{n-1}+3^n)x^n=2\sum_{n=0}^{\infty}a_{n-1}x^n+\sum_{n=0}^{\infty}3^nx^n=$$ $$=2x\sum_{n=0}^{\infty}a_{n}x^n+\frac{1}{1-3x}=2xf(x)+\frac{1}{1-3x}$$ from there $$f(x)=\frac{1}{(1-2x)(1-3x)}=\frac{1}{1-(5x-6x^2)}=\sum_{n=0}^{\infty}(5x-6x^2)^n=$$ $$=\sum_{n=0}^{\infty}x^n(5-6x)^n=\sum_{n=0}^{\infty}x^n\sum_{k=0}^{n}\binom{n}{k}5^{n-k}(-6x)^k=$$ $$=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}5^{n-k}(-6)^kx^{n+k}=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n-k}{k}5^{n-2k}(-6)^{k}x^{n}$$ equating coefficients next to $x$ we get $$a_n=\sum_{k\geq0}\binom{n-k}{k}5^{n-2k}(-6)^{k}$$