3

Recently, I found that the generating function for a sequence I am interested in is $$s(x) = -\frac{3 \, x^{3} + x^{2} + 2 \, x}{2 \, x^{3} + x - 1}.$$ Naturally, I am now keen on extracting the $n$th coefficient of the Taylor expansion of $s(x)$ without the help of a computer. Unfortunately, the three roots of the denominator of $s(x)$, of which two are complex, are rather unfriendly creatures, so that partial fraction decomposition does not seem to be a viable method. But what can I do then to find the desired coefficients?

Thank you!

Malte
  • 39

2 Answers2

2

We can derive the $n$-th coefficient by makeing a geometric series expansion of \begin{align*} \color{blue}{s(x)}&\color{blue}{=-\frac{3x^3+x^2+2x}{2x^3+x-1}}\\ &\color{blue}{=2x+3x^2+6x^3+10x^4+16x^5+28x^6+\cdots} \end{align*} We use the coefficient of operator $[x^n]$ to derive the coefficient of $x^n$ of a series.

We obtain \begin{align*} \color{blue}{[x^n]}&\color{blue}{s(x)} =[x^n]\left(-\frac{3x^3+x^2+2x}{2x^3+x-1}\right)\\ &=\left(3[x^{n-3}]+[x^{n-2}]+2[x^{n-1}]\right)\frac{1}{1-x\left(1+2x^2\right)}\tag{1}\\ &=\left(3[x^{n-3}]+[x^{n-2}]+2[x^{n-1}]\right)\sum_{k=0}^{\infty}x^k\left(1+x^2\right)^k\tag{2}\\ &=3\sum_{k=0}^{n-3}[x^{n-3-k}]\left(1+2x^2\right)^k +\sum_{k=0}^{n-2}[x^{n-2-k}]\left(1+2x^2\right)^k\\ &\qquad\qquad+2\sum_{k=0}^{n-1}[x^{n-1-k}]\left(1+2x^2\right)^k\tag{3}\\ &=3\sum_{k=0}^{n-3}[x^{k}]\left(1+2x^2\right)^{n-3-k} +\sum_{k=0}^{n-2}[x^{k}]\left(1+2x^2\right)^{n-2-k}\\ &\qquad\qquad+2\sum_{k=0}^{n-1}[x^{k}]\left(1+2x^2\right)^{n-1-k}\tag{4}\\ &=3\sum_{k=0}^{\left\lfloor\frac{n-3}{2}\right\rfloor}[x^{2k}]\left(1+2x^2\right)^{n-3-2k} +\sum_{k=0}^{\left\lfloor\frac{n-2}{2}\right\rfloor}[x^{2k}]\left(1+2x^2\right)^{n-2-2k}\\ &\qquad\qquad+2\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}[x^{2k}]\left(1+2x^2\right)^{n-1-2k}\tag{5}\\ &\color{blue}{=3\sum_{k=0}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\binom{n-3-2k}{2k}2^{k} +\sum_{k=0}^{\left\lfloor\frac{n-2}{2}\right\rfloor}\binom{n-2-2k}{2k}2^{k}}\\ &\qquad\qquad\color{blue}{+\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{n-1-2k}{2k}2^{k+1}}\tag{6}\\ \end{align*}

Comment:

  • In (1) we use the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

  • In (2) we make a geometric series expansion.

  • In (3) we again apply the rule as in (1). We also restrict the upper limit since other terms do not contribute.

  • In (4) we change the order of summation $k\to n-a-k, a=1,2,3$.

  • In (5) we respect that only even powers contribute.

  • In (6) we select the coefficients accordingly.

Markus Scheuer
  • 108,315
  • Thank you, Markus Scheuer, for this enlightening answer which shows that the generating function can indeed be helpful to get to the coefficients of "my" series. I keep studying your answer and will be doing so over the next few days. Maybe I'll come back to you with some question about your answer. I am especially grateful for your comments on your own solution. Malte – Malte Nov 27 '22 at 17:29
  • @Malte: You're welcome! Many thanks for your nice comment. :-) – Markus Scheuer Nov 27 '22 at 18:23
  • There seems to be some issue, $[x^4]s(x)$ should be $10$ but by the final formula it evaluates to $6$ (and all the subsequent terms do not match as well). – Sil Dec 01 '22 at 08:12
  • I think it should be $3\sum_{k=0}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\binom{n-3-2k}{k}2^{k} +\sum_{k=0}^{\left\lfloor\frac{n-2}{2}\right\rfloor}\binom{n-2-2k}{k}2^{k}+\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{n-1-2k}{k}2^{k+1}$ – Sil Dec 01 '22 at 08:39
  • @Sil: Yes, you're right of course. Many thanks for pointing out the mistake. Corrected. – Markus Scheuer Dec 01 '22 at 09:52
1

If the genrating function is $$s(x) = -\frac{3 \, x^{3} + x^{2} + 2 \, x}{2 \, x^{3} + x - 1}$$ the coefficients correspond to the recurrence $$a_{n+3}=a_{n+2}+2a_n$$with $$a_1=0 \qquad a_2=2\qquad a_3=3\qquad a_4=6$$ The three roots of the characteristic equation $$r^3=r^2+2$$ are $$r_1=\frac 13\left(1+2 \cosh \left(\frac{1}{3} \cosh ^{-1}(28)\right)\right)$$ $$r_2=\frac 12\left(1-r_1-\sqrt{\frac{-r_1^2+r_1-6}{r_1} } \right)\qquad \qquad r_3=\frac 12\left(1-r_1+\sqrt{\frac{-r_1^2+r_1-6}{r_1} } \right)$$

Now, appy the conditions writing $$a_n=A_1\,r_1^n+A_2\,r_2^n+A_3\,r_3^n$$ to get $(A_1,A_2,A_3)$.

Claude Leibovici
  • 260,315
  • Thank you very much, Claude Leibovici, for your answer and the effort you put into it. It is interesting to see that you reconstructed the original sequence and did not actually use the generating function. So maybe using generating functions is a dead end here, and we must proceed as you suggest. – Malte Nov 26 '22 at 12:08
  • I don't know the theoretical background of the last three lines of your answer, though. Is there a theorem which states that, if $a_n$ obeys a recursion of order $n$ we have $a_n = A_1 r_1^n + A_2 r_2^n + A_3 r_3^n$ where $r_1, r_2, r_3$ are the roots of the characteristic equation and the $A_i$ are certain coefficients? – Malte Nov 26 '22 at 12:09
  • By the way, the background of the original sequence is this: Let us assume we have an infinite supply of paper strips of three different colours, the red ones having length 2, the green and the blue ones having length 1 each. We want to build longer paper strips by joining those little paper strips and must not directly join strips of the same colour. The $n$-th element of the sequence then gives the number of different paper chains of length $n$, the first few elements being 2, 3, 6, 10, 16. – Malte Nov 26 '22 at 12:09
  • I wonder if we can make a change to that setting so that the whole thing is still a challenge but does not involve so "difficult" numbers like the $r_i$ and $A_i$ in this setting. – Malte Nov 26 '22 at 12:10
  • You could use rationlized values of the roots computed to high accuracy. – Claude Leibovici Nov 26 '22 at 14:51
  • That is another good idea. I could use some convergent of the corresponding continued fraction. – Malte Nov 26 '22 at 15:09