Determining the form of generating functions based on recursive formula

73 Views Asked by At

Consider the following two sequences:

$$a_n = 3a_{n-1} + 2a_{n-2}, a_0 = 1, a_1 = 2$$ and $$a_n = 2a_{n-1} + 4^{n-1}, a_0 = 1$$

I see the method used here that looks nice and clean but I can't detect the pattern here in these two cases. Maybe I'm not paying good attention?

1

There are 1 best solutions below

1
On BEST ANSWER

As regards the second one, multiply both sides of the equation by $z^n$ and take the sum for $n$ from $1$ to infinity: $$\sum_{n=1}^{\infty}a_nz^n = 2\sum_{n=1}^{\infty}a_{n-1}z^n + \sum_{n=1}^{\infty}4^{n-1}z^n,$$ that is, for $4|z|<1$, $$f(z)-a_0 = 2zf(z) + z\sum_{n=1}^{\infty}(4z)^{n-1}=2zf(z) + \frac{z}{1-4z}$$ where $f(z):=\sum_{n=0}^{\infty}a_nz^n$ is the generating function of the sequence $(a_n)_{n\geq 0}$. Finally use the fact that $a_0=1$, and solve with respect to $f$.

Can you take it from here? For the first one, try to follow the same procedure.