Find the generating function for the recurrence:

Question

Struggling to approach keep ending with solutions that do not work.

Find the generating function for the recurrence:

$$a_{+1}= \frac{a_}3 + 1, \quad ≥ 0$$

with the initial condition $a_0 =0$.

Answer 1

Let $A(x)=\displaystyle\sum_{n\ge0}a_nx^n$ be the generating function for the sequence $\{a_n\}$. For $|x|<1$, we can multiply both sides by $x^n$ and sum over $n\ge0$ to get

$$\sum_{n\ge0} a_{n+1} x^n = \sum_{n\ge0} \left(\frac13 a_n + 1\right) x^n$$

Now we can recover a few instances of $A(x)$,

$$\begin{align*} \sum_{n\ge1} a_n x^{n-1} &= \frac13 A(x) + \sum_{n\ge0}x^n \\ \implies \frac{A(x) - a_0x^0}x &= \frac13 A(x) + \frac1{1-x} \end{align*}$$

and from here you can easily solve for $A(x)$.