Find the generating function for the recurrence:

Question

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

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

with the initial condition $a_0 =0$.

This will be closed if you show no effort. You didn't even type the question, only used a camera. — coffeemath, Oct 10 '23 at 20:05
Sorry about that coffeemath, was trying to enter the characters on my keyboard but was having trouble — Martin, Oct 10 '23 at 20:11

score 1 · Answer 1 · answered Oct 10 '23 at 20:49

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)$.

answered Oct 10 '23 at 20:49

user170231

19,334

Thank you so much for the help I solved it, just one quick clarification question, why is a(x) -a0 divided by x? – Martin Oct 10 '23 at 22:16
1

If you look at the term on the left in the line above it, we have a sum that starts at $n = 1$ of a power series in $x^{n-1}$, so if you multiply it by $x$ to raise that to $x^n$ and then add the $a_0x^0$ term back in, you get the original power series for $A(x)$. – ConMan Oct 10 '23 at 22:29

Find the generating function for the recurrence:

1 Answers1