1
$\begingroup$

Show that the coefficient of $[x^nu^m] $ in the bivariate generating function $\dfrac{1}{1-2x+x^2-ux^2}$ is ${n+1\choose n-2m}.$

I tried to do this by using the multinomial theorem (an extension of the binomial theorem), which basically states that for terms $x_1,\cdots, x_r, n\in \mathbb{N}_{\geq 0}, (x_1+\cdots + x_r)^n = \sum_{k_1+\cdots + k_r = n} \dfrac{n!}{k_1! \cdots k_r!}x_1^{k_1}\cdots x_r^{k_r}.$

This gives that the given bivariate generating function is equal to $\sum_{n\geq 0}(2x-x^2+ux^2)^n = \sum_{n\geq 0} \sum_{k_1+k_2 + k_3 = n} \dfrac{n!}{k_1!k_2!k_3!} (2x)^{k_1}(-x^2)^{k_2}(ux^2)^{k_3}$.

Thus the coefficient of $[x^n u^m]$ should be $\sum_{k_1 + 2k_2 = n-2m} \dfrac{(n-k_2-m)!}{k_1!k_2!m!}2^{k_1} (-1)^{k_2} .$ I can further simplify this by replacing $k_2$ with $\dfrac{n-2m-k_1}{2},$ but I'm not sure how to get the desired result from that. Is there some other useful property of polynomials? I also realized that $\sum_{m\geq 0} {n+1\choose n-2m} = 2^n,$ which can be shown using Pascal's identity, though I'm not sure if this is useful.

$\endgroup$
  • $\begingroup$ Technically this is not a polynomial (that would require finitely many terms of form $x^i u^j$), this is more of a bivariate generating function. $\endgroup$ – Sil Aug 28 '20 at 20:12
  • 1
    $\begingroup$ @Sil sorry for the poor use of terminology. It can also be called a formal power series. $\endgroup$ – Fred Jefferson Aug 28 '20 at 20:18
1
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Show that the coefficient of $\ds{\bracks{x^{n}u^{m}}}$ in the bivariate generating function $\ds{1 \over 1 - 2x + x^{2} - ux^{2}}$ is $\ds{\bbox[5px,#ffd]{n + 1\choose n - 2m}: {\Large ?}}$.


\begin{align} &\bbox[5px,#ffd]{\bracks{x^{n}u^{m}}{1 \over 1 - 2x + x^{2} - ux^{2}}} = \bracks{x^{n}u^{m}}{1 \over \pars{1 - x}^{2} - ux^{2}} \\[5mm] = &\ \bracks{x^{n}u^{m}}{1 \over \pars{1 - x}^{2}} \bracks{1 - {x^{2} \over \pars{1 - x}^{2}}\,u}^{-1} = \bracks{x^{n}}{1 \over \pars{1 - x}^{2}} \bracks{x^{2} \over \pars{1 - x}^{2}}^{m} \\[5mm] = &\ \bracks{x^{n - 2m}}\pars{1 - x}^{-2m - 2} = {-2m - 2 \choose n - 2m}\pars{-1}^{n - 2m} \\[5mm] = &\ {-\bracks{-2m - 2} + \bracks{n - 2m} - 1 \choose n - 2m} = \bbx{\large{n + 1 \choose n - 2m}} \\ & \end{align}
$\endgroup$
2
$\begingroup$

It might be more helpful to factorize the quadratic expression first (taking it as a variable in $x$). This way we can extract coefficient of $x^n$ ($u$ taken as a constant) and then coefficient of $u^m$ (in other words $[x^n u^m]f(x,u)=[u^m]([x^n]f(x,u))$. So, by factorization of denominator we arrive at $$ \dfrac{1}{1-2x+x^2-ux^2}=\frac{1}{1-(1+\sqrt{u})x}\cdot \frac{1}{1-(1-\sqrt{u})x} $$ which by geometric series is $$ (\sum_{i \geq 0}(1+\sqrt{u})^ix^i) \cdot (\sum_{j \geq 0}(1-\sqrt{u})^j x^j ). $$ So we get a coefficient of $x^n$ $$ \sum_{k=0}^{n}(1+\sqrt{u})^k(1-\sqrt{u})^{n-k}\tag{*} $$ and the problem reduces to finding coefficient of $u^m$ in $(*)$. We can evaluate the expression for example by writing it as $$ (1-\sqrt{u})^n\sum_{k=0}^{n}\left(\frac{1+\sqrt{u}}{1-\sqrt{u}}\right)^k $$ and spot the finite geometric series with $q=\frac{1+\sqrt{u}}{1-\sqrt{u}}$, so we can just use well-known formula for the sum $\frac{q^{n+1}-1}{q-1}$. After some messy algebra we get $$ \frac{1}{2\sqrt{u}}[(1+\sqrt{u})^{n+1}-(1-\sqrt{u})^{n+1}], $$ which finally by Binomial theorem gives $$ \frac{1}{2\sqrt{u}}\sum_{m=0}^{n+1}\binom{n+1}{m}\sqrt{u}^{m}(1-(-1)^{m}). $$ For even $m$ the terms vanish and we are left with $$ \sum_{m=0}^{\lfloor n/2 \rfloor}\binom{n+1}{2m+1}u^{m}. $$ Now just read off the coefficient, also perhaps use $\binom{n}{k}=\binom{n}{n-k}$.

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