Initial conditions of a recurrence relation from a generating series

Question

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?

Answer 1

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}$$

Answer 2

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

Answer 3

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.

Answer 4

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.