1

I'm trying to understand the generating function for this sequence: Triangle read by rows, 0 <= k <= n: T(n,k) = binomial(n-[(k+1)/2],[k/2])*(-1)^[(k+1)/2]. It's a triangle, and I'm trying to find the function $F(r, x)$ such that I can substitute $r$ for the row number, and end up with the generating function in terms of $x$.

In the OEIS page I've linked, they give the generating function as $$A(x, y) = \frac{1 - xy}{1 - x + x^2y^2}$$ however, if I substitute the row $r=3$ for either $x$ or $y$ in A (what I assume would be a natural place to number the rows), and then do polynomial long division [starting with low-order terms], I most certainly do not get the generating function for $x$.

For example, with $y=3$, I get the polynomial $p(x) = 1 - 2x -11x^2 +7x^3+106x^4...$, which is certainly not the third row of the triangle [listed below and on the website.]

1 ;

1, -1 ;

1, -1, -1 ;

1, -1, -2, 1 ;

1, -1, -3, 2, 1 ;

1, -1, -4, 3, 3, -1 ;

1, -1, -5, 4, 6, -3, -1 ;

I have three questions:

  1. How should I understand the generating function given, A?
  2. Is it possible for a finite sequence to have a generating function?
  3. What is the $F(r, x)$ I'm looking for in this case?
Mark Miller
  • 215

1 Answers1

2

After some more reading, I feel confident in answering this question.

Question #1: How should I understand the generating function given, A? Turns out I had a misunderstanding of how multivariable generating functions worked. It's simple enough to write out the definition of a function like that - this was on Wikipedia.

$$A(x,y)=\sum_{n=0}^\infty\sum_{m=0}^\infty a_{n,m}x^ny^n$$

I was expecting $x$ or $y$ to work like an indexing variable - if I want $a_{p,q}$, then I'd plug in $A(p,q)$. That is most certainly not the case.

Question #2: Is it possible for a finite sequence to have a generating function? Absolutely - the generating function for binomial coefficients is naturally $(1+x)^k$. [Side note - I don't know if this is formally called a generating function, but it does have a lot of the same neat properties.]

Question #3: What is the $F(r,x)$ I'm looking for in this case? The function I was looking for was literally in the row below on the webpage, credited to Emeric Deutsch.

The generating polynomial (in $z$) of row $n\geq 0$ is $$\frac{u^{2n+1} + v^{2n+1}}{u + v}$$ where $u$ and $v$ are defined by $u^2 + v^2 = 1$ and $uv = z$.

Mark Miller
  • 215