I'll use another way to give the question besides the title.

Define $$ A_k(n) = \frac{1}{2 \pi \mathrm{i}} \int_{|q|=1} \left( \frac{1}{2 \pi \mathrm{i}}\int_{|z|=1}\prod_{j=-n}^{n}(1+qz^j) \frac{dz}{z} \right) \frac{1}{q^k} \frac{dq}{q}.$$

By some numeral calculation buy a simple program, I note that if we freeze $k$, then $A_k(n)$ always satisfies a linear recurrence relations.

How to make a proof? Or anyone could give a counterexample? (A "appropriate" counterexample may be a sequence $A_l(1), A_l(2), \cdots, A_l(m)$ for large enough $m$.)

Thanks for reading my problem. : )

  • 1
    $\begingroup$ Residue formula seems the way to go, did you try it? It is difficult to give a counterexample to a recurrence relation that you did not state! $\endgroup$ – Benoît Kloeckner Jan 3 '14 at 13:43
  • $\begingroup$ Any sequence satisfies some recurrence relation. To make a meaningful question, specify what sort of recurrence relations you seek. $\endgroup$ – Andreas Blass Jan 3 '14 at 13:44
  • $\begingroup$ To Andreas, thanks for your comment, I've re-edited it. $\endgroup$ – Lwins Jan 3 '14 at 13:52
  • $\begingroup$ To Benoît, if changing $(1+qz^j)$ to $(1-qz^j)^{-1}$, I thought I could do it by residue formula. But if not, it seems to be too hard for me. $\endgroup$ – Lwins Jan 3 '14 at 13:56
  • $\begingroup$ Maybe the combinatorial interpretation is a better way to justify a recurrence. $A_k(n)$ is something like the number of $k$-subsets of $\lbrace -n,\ldots,n\rbrace$ that sum to 0, isn't it? $\endgroup$ – Brendan McKay Jan 3 '14 at 15:17

Here is a sketch of a proof. First I'll switch $q$ and $z$, since this is more consistent with standard “$q$-series” notation.

Let $C_k(n)$ be the coefficient of $z^k$ in $\prod_{j=-n}^n (1+q^jz)$, so that $A_k(n)$ is the constant term in $q$ in $C_k(n)$. By the $q$-binomial theorem $$\prod_{j=0}^{m-1} (1+q^iz) = \sum_{k=0}^m {m \atopwithdelims[] k} q^{\binom k2}z^k, $$ where $${m \atopwithdelims[] k} = \frac{(q^m-1)(q^{m-1}-1)\cdots (q^{m-k+1}-1)}{(q^k-1)\cdots (q-1)}.$$ It follows that $$C_k(n)={2n+1 \atopwithdelims[] k} q^{\binom k2 -kn}$$ Expanding the $q$-binomial coefficients, we see that $$C_k(n)=\sum_{l=-k}^k R_l(q) q^{ln},$$ where each $R_l(q)$ is a rational function of $q$.

Now let $$G_k=\sum_{n=0}^\infty C_k(n) t^n.$$ Then $$G_k=\sum_{l}\frac{R_l(q)}{1-tq^l}.$$ Expanding $G_k$ in partial fractions in $q$, we see that the constant term in $q$, which is $\sum_n A_k(n)t^n$, is a rational function of $t$, so $A_k(n)$ satisfies a linear recurrence with constant coefficients.

For example, $$G_2 = \frac{(1+q)t}{(1-t)^2(1-q^2t)} + \frac{t(q+t)}{(1-t)^2(q^2-t)}.$$ The second term, when expanded as a power series in $t$, has only negative powers of $q$, so it contributes nothing to the constant term in $q$. The first term, when expanded as a power series in $t$, has only nonnegative powers of $q$, so we obtain the constant term in $q$ by setting $q=0$ in the first term and we find that $$\sum_{n=0}^\infty A_2(n) t^n = t/(1-t)^2 =\sum_{n=0}^\infty nt^n.$$

| cite | improve this answer | |
  • $\begingroup$ Why $G_k = \sum_m {\dfrac{R_m(q)}{1-tq^m}}$? $\endgroup$ – Lwins Jan 3 '14 at 17:38
  • $\begingroup$ I have rewritten my answer to make this clearer. $\endgroup$ – Ira Gessel Jan 3 '14 at 18:16
  • $\begingroup$ Thanks for your detailed answer. Last problem: Why $C_k(n) = \exp (\cdots) \Longrightarrow C_k(n)$ is a linear combination of products... ? (Though that by $q$-binomial theorem it's trivial.) $\endgroup$ – Lwins Jan 3 '14 at 18:29
  • $\begingroup$ You're right. I rewrote it to use the q-binomial theorem. $\endgroup$ – Ira Gessel Jan 3 '14 at 20:15

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.