$\sum(-1)^{k}k^{2}C_{n}^{k}$

Question

I'm asked to compute $\sum^{n}_{k=1}(-1)^{k}k^{2}C_{n}^{k}$ for $n\geqslant 1$. I tried to use generating functions to solve the problem: $A(x):=\sum^{n}_{k=1}k^{2}C_{n}^{k}x^{k}$. So, I need to compute $A(-1)$.

For $n=1$ $A(-1)=-1$, for $n=2$ $A(-1)=2$, for $n=2$ $A(-1)=2$, for $n=3,4,5,6,7,...(?)$ $A(-1)=0$. It seems that the answer is $0$ for $n\geqslant 3$...

Thank you in advance!

Answer 1

First note that \begin{align} \sum_{k=1}^\infty k^2 x^k &=x^2\sum_{k=1}^\infty k(k-1) x^{k-2} + x\sum_{k=1}^\infty k x^{k-1}\\ &=x^2\frac{d^2}{dx^2}\sum_{k=0}^\infty x^k + x\frac{d}{dx} \sum_{k=0}^\infty x^k\\ &=x^2\frac{d^2}{dx^2}\frac{1}{1-x} + x\frac{d}{dx} \frac{1}{1-x}\\ &=x^2\frac{2}{(1-x)^3}+x\frac{1}{(1-x)^2}\\ &=\frac{x(1+x)}{(1-x)^3}. \tag1 \end{align} Now \begin{align} \sum_{n=1}^\infty \sum_{k=1}^n (-1)^k k^2 \binom{n}{k} z^n &=\sum_{k=1}^\infty (-1)^k k^2 \sum_{n=k}^\infty \binom{n}{k} z^n\\ &=\sum_{k=1}^\infty (-1)^k k^2 \frac{z^k}{(1-z)^{k+1}}\\ &=\frac{1}{1-z}\sum_{k=1}^\infty k^2 \left(\frac{-z}{1-z}\right)^k\\ &=\frac{1}{1-z}\frac{\frac{-z}{1-z}\left(1+\frac{-z}{1-z}\right)}{\left(1-\frac{-z}{1-z}\right)^3} &&\text{by $(1)$ with $x=\frac{-z}{1-z}$}\\ &=-z+2z^2. \end{align} Hence $$\sum_{k=1}^n (-1)^k k^2 \binom{n}{k}= \begin{cases} -1 &\text{if $n=1$}\\ 2 &\text{if $n=2$}\\ 0 &\text{otherwise} \end{cases}$$

---

Alternatively, @Phicar's approach yields \begin{align} \sum_{k=1}^n (-1)^k k^2 \binom{n}{k} &=\sum_{k=1}^n (-1)^k \left(2\binom{k}{2}+\binom{k}{1}\right) \binom{n}{k} \\ &=2\sum_{k=2}^n (-1)^k \binom{k}{2} \binom{n}{k} +\sum_{k=1}^n (-1)^k \binom{k}{1} \binom{n}{k} \\ &=2\sum_{k=2}^n (-1)^k \binom{n}{2} \binom{n-2}{k-2} +\sum_{k=1}^n (-1)^k \binom{n}{1} \binom{n-1}{k-1} \\ &=2\binom{n}{2} \sum_{k=2}^n (-1)^{k-2} \binom{n-2}{k-2} -\binom{n}{1}\sum_{k=1}^n (-1)^{k-1} \binom{n-1}{k-1} \\ &=2\binom{n}{2} \sum_{k=0}^{n-2} (-1)^k \binom{n-2}{k} -\binom{n}{1}\sum_{k=0}^{n-1} (-1)^k \binom{n-1}{k} \\ &=2\binom{n}{2} (1-1)^{n-2} - \binom{n}{1}(1-1)^{n-1} \\ &=2\binom{n}{2} [n=2] - \binom{n}{1}[n=1] \\ &= \begin{cases} -1 &\text{if $n=1$}\\ 2 &\text{if $n=2$}\\ 0 &\text{otherwise} \end{cases} \end{align}

Answer 2

Hint: Notice that $$k^2=2C_k^2+k,$$ so $$\sum _{k=1}^n(-1)^k\left (2C_k^2+k\right )C_n^k=2\sum _{k=1}^n(-1)^kC_k^2C_n^k+\sum _{k=1}^n(-1)^kkC_n^k.$$ Notice, further, that $C_a^bC_b^c=C_a^cC_{a-c}^{b-c},$ hence $C_n^kC_k^2=C_n^2C_{n-2}^{k-2}$ and $C_n^kC_k^1=C_n^1C_{n-1}^{k-1}.$

You probably now can use Binomial theorem.

Answer 3

Computing

$$\sum_{k=0}^n {n\choose k} (-1)^k k^2$$

we write

$$\sum_{k=0}^n {n\choose n-k} (-1)^k k^2 = [z^n] (1+z)^n \sum_{k=0}^n z^k (-1)^k k^2.$$

Here the coefficient extractor controls the range and we find

$$[z^n] (1+z)^n \sum_{k\ge 0} z^k (-1)^k k^2 = [z^n] (1+z)^n \frac{z(z-1)}{(1+z)^3} \\ = [z^n] (1+z)^{n-3} (z^2-z).$$

This is zero when $n\ge 3$ because we are extracting the coefficient $[z^n]$ from a polynomial in $z$ of degree $n-1.$

Continuing, it becomes

$$[z^n] z^2 (1+z)^{n-3} - [z^n] z (1+z)^{n-3} = {n-3\choose n-2} - {n-3\choose n-1}.$$

This is again zero by inspection when $n\ge 3$ because
$(n-3)^\underline{n-2} = 0$ and $(n-3)^\underline{n-1} = 0.$

For $n=2$ we get ${-1\choose 0} - {-1\choose 1} = 1 - (-1) = 2$ and for $n=1$ we find $- {-2\choose 0} = -1.$