Generating function for $\frac{1}{(1-3x)^2}$

Question

I was tasked to solve the following recurrence using generating functions: $$a_{n+1} = 3a_n + 3^n$$ Using $A(x) = \sum a_nx^n$ I arrived at the following decomposition (which I checked to be true): $$A(x) = \frac{2-5x}{(1-3x)^2} = \frac{5}{3}\cdot\frac{1}{1-3x} + \frac{1}{3}\cdot\frac{1}{(1-3x)^2}$$

I know that $\frac{1}{1-3x}$ corresponds to the generating function $\sum 3^nx^n$, but what about $\frac{1}{(1-3x)^2}$? It is never mentioned in any of the sources I am working with.

Answer 1

Since $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$, we can differentiate both sides we get

$$\frac{1}{(1-x)^2} = \sum_{n=1}^\infty n x^{n-1}$$

Edit:

Explicitly, we can now substitute $3x$ for $x$ in the above to see

$$\frac{1}{(1-3x)^2} = \sum_{n=1}^\infty n 3^{n-1} x^{n-1}$$

---

I hope this helps ^_^

Answer 2

Hint: Differentiate \begin{eqnarray*} \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{eqnarray*} and now sub $x \rightarrow 3x$.