# Initial conditions of a recurrence relation from a generating series

Suppose I have the following generating series: $$\phi_S(x) = \frac{1+x}{1-x^2-2x^3}$$

The corresponding recurrence relation is this (I can show this): $$a_n=a_{n-2} + 2a_{n-3}, n \geq 3$$

My question is, how would one get the initial conditions $$a_0, a_1, a_2$$ using only this information?

• By "this information" do you include $\phi_S(x)$? – Parcly Taxel Jul 4 '19 at 4:44
• Yes, you can use $\phi_S(x)$ – Mark Dodds Jul 4 '19 at 4:44

You've used the denominator of $$\frac{1+x}{1-x^2-2x^3}$$ to get the recurrence: the numerator gives the initial terms. If we generalise slightly so that you can see the derivation, $$\frac{b+cx+dx^\alpha}{1-x^2-2x^3}$$ gives recurrence $$a_n=a_{n-2} + 2a_{n-3} + b[n = 0] + c[n = 1] + d[n = \alpha]$$ where $$[\cdot]$$ is an Iverson bracket and evaluates to $$1$$ when the condition inside is true and $$0$$ when it is false. So in your case ($$b=c=1, d=0$$) we have $$\begin{eqnarray}a_0 &=& a_{-2} &+& 2a_{-3} + b &=& b &=& 1 \\ a_1 &=& a_{-1} &+& 2a_{-2} + c &=& c &=& 1 \\ a_2 &=& a_{0} &+& 2a_{-1} &=& a_0 &=& 1 \end{eqnarray}$$

### Why?

"$$\phi_S(x)$$ is the generating function for $$a_i$$" is another way of saying $$\phi_S(x) = \sum_{n} a_n x^n$$

If we substitute that into the given rational function, $$\sum_{n} a_n x^n = \frac{1+x}{1-x^2-2x^3}$$ we can rearrange to $$(1-x^2-2x^3)\sum_{n} a_n x^n = 1+x$$ and then to $$\sum_{n} a_n x^n = 1+x + \sum_{i} (a_i x^{i+2} + 2a_i x^{i+3})$$ Then if we apply the coefficient extraction operator $$[x^n]$$ to both sides, using its linearity, we get $$a_n = [x^n]1 + [x^n]x + \sum_{i} ([x^n]a_i x^{i+2} + [x^n] 2a_i x^{i+3}) \\ = [n=0] + [n=1] + \sum_{i} (a_i [n=i+2] + 2a_i [n=i+3]) \\ = [n=0] + [n=1] + a_{n-2} + 2a_{n-3}$$

Since $$\phi_S(x)=\sum_{i=0}a_ix^i=a_0+a_1x+a_2x^2+a_3x^3+\dotsb$$ Therefore $$a_0=\phi_S(0)=1$$ and $$a_1=\phi_S'(0)$$. So take the derivative and compute it at $$x=0$$ to get $$a_1$$. Similarly take second derivative to get $$a_2$$.

By definition, the sequence coefficients arise in the generating function's Maclaurin series, so the definition of Maclaurin series can be employed to find the initial terms. $$a_n=\frac{\phi_S^{(n)}(0)}{n!}$$ (I use zero-based indexing here, and $$f^{(n)}$$ indicates the $$n$$th order derivative.) You should find that the initial three terms are all $$1$$.

This is OEIS A159284.

Why not to use the Taylor expansion $$\phi_S(x) = \frac{1+x}{1-x^2-2x^3}=1+x+x^2+3 x^3+3 x^4+5 x^5+9 x^6+11 x^7+19 x^8+29 x^9+O\left(x^{10}\right)$$ which could also be obtained by long division.