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.
Best Answer
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}$.