Help me finding closed form of sum of 4 elements

Question

I've been reading Wilf's Gfology and tried to calculate some complicated sum Let's say $0<k \le n$ $$f(k,n) = \sum_{i} i(-1)^i \binom{n}{i} \binom{i}{k-i} $$ I will write down my calculations, i hope there is no mistake. I want to calculate generating function of $f(k,n)$ it is $F(k,n) = \sum_{n} f(k,n) x^n$ $$\sum_{n}x^n \sum_{i} i(-1)^i \binom{n}{i} \binom{i}{k-i}=$$ $$\sum_{i} i(-1)^i \binom{i}{k-i} \sum_{n} \binom{n}{i} x^n=$$ $$\sum_{i} i(-1)^i \binom{i}{k-i} \frac{x^i}{(1-x)^{i+1}}=$$ $$\frac{1}{1-x} \sum_{i} i(-1)^i \binom{i}{k-i} \left(\frac{x}{(1-x)}\right)^i$$ I don't really know how to proceed with this sum. I'd like to solve it with generating functions if it's possible. I will be greatful for any hints or solutions to this.

Answer 1

Here's a variant to obtain a generating function $F(x,y)=\sum_{n\geq 0}\sum_{k\geq 0}f(k,n)x^ky^n$. It's not obvious (for me) to derive a closed formula from it. Maybe this indicates that there is no one obtainable.

Let \begin{align*} f(k,n)=\sum_{i}i(-1)^i\binom{n}{i}\binom{i}{k-i}\qquad\qquad0\leq k\leq n \end{align*}

We use with $k\geq 0$ a slightly extended range of definition.

We now introduce the formal generating function $$F_n(x)=\sum_{k\geq 0}f(k,n)x^k\qquad\qquad n\geq 0$$ and show

The following is valid

\begin{align*} F_n(x) =-nx(1+x)(1-x-x^2)^{n-1}\qquad\qquad n\geq 0\tag{1} \end{align*}

We observe \begin{align*} F_n(x)&=\sum_{k\geq 0}f(k,n)x^k\\ &=\sum_{k\geq 0}\sum_{i\geq 1}(-1)^ii\binom{n}{i}\binom{i}{k-i}x^k\\ &=\sum_{k\geq 0}\sum_{i\geq 1}(-1)^in\binom{n-1}{i-1}\binom{i}{k-i}x^k\tag{2}\\ &=n\sum_{i\geq 1}(-1)^i\binom{n-1}{i-1}x^i\sum_{k\geq 0}\binom{i}{k-i}x^{k-i}\tag{3}\\ &=n\sum_{i\geq 1}(-1)^i\binom{n-1}{i-1}x^i\sum_{r\geq 0}\binom{i}{r}x^{r}\tag{4}\\ &=n\sum_{i\geq 1}(-1)^i\binom{n-1}{i-1}x^i(1+x)^i\\ &=n\sum_{i\geq 0}(-1)^{i+1}\binom{n-1}{i}x^{i+1}(1+x)^{i+1}\tag{5}\\ &=-nx(1+x)\sum_{i\geq 0}(-1)^{i}\binom{n-1}{i}x^{i}(1+x)^{i}\\ &=-nx(1+x)\left(1-x(1+x)\right)^{n-1}\\ \end{align*} and the claim (1) follows.

Comment:

• In (2) we use the identity $i\binom{n}{i}=n\binom{n-1}{i-1}$

• In (3) we do some rearrangements to prepare for the index substitution in (4)

• In (4) we introduce the index $r := k-i$

• In (5) we shift the index $i$

We now calculate the complete generating function \begin{align*} F(x,y)=\sum_{n\geq 0}F_n(x)y^n=\sum_{n\geq 0}\sum_{k\geq 0}f(k,n)x^ky^n \end{align*}

The following is valid

\begin{align*} F(x,y) =-\frac{x(1+x)y}{\left(1-(1-x-x^2)y\right)^2} \end{align*}

We observe, using the expression (1) of the generating function $F_n(x)$

\begin{align*} F(x,y)&=-x(1+x)\sum_{n\geq 0}n(1-x-x^2)^{n-1}y^n\\ &=-x(1+x)y\sum_{n\geq 1}n(1-x-x^2)^{n-1}y^{n-1}\\ &=-x(1+x)y\sum_{n\geq 0}(n+1)(1-x-x^2)^{n}y^{n}\tag{6}\\ &=-x(1+x)y\sum_{n\geq 0}\binom{-2}{n}(1-x-x^2)^{n}(-y)^{n}\tag{7}\\ &=-\frac{x(1+x)y}{\left(1-(1-x-x^2)y\right)^2}\tag{8} \end{align*}

and the claim follows.

Comment:

• In (6) we shift the index $n$

• In (7) we use the binomial identity $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$