3
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.