# Find $\sum_{k=0}^{n}2^ks(n,k)$, where $s(n,k)$ is the Stirling number of the first kind?

Find $\sum_{k=0}^{n}2^ks(n,k)$, where $s(n,k)$ is the Stirling number of the first kind?

I was able to find that $\sum_{k=0}^{n}x^kc(n,k)=\dfrac{(n-1+x)!}{(x-1)!}$ where $c(n,k)$ is the signless Stirling number of the first kind. Since $s(n,k)=(-1)^{n-k}c(n,k)$, I can multiply both sides by $(-1)^n$ and replace $x$ by $-x$ in both sides. Then I get $\sum_{k=0}^{n}x^ks(n,k)=(-1)^n\dfrac{(n-1-x)!}{(-x-1)!}$. When $x=2$, we have $\sum_{k=0}^{n}x^ks(n,k)=(-1)^n\dfrac{(n-3)!}{(-3)!}$. Is this result good enough? Should I get rid of the $(-3)!$? If so, do I have to use the Gamma function? Thanks!

• Well, what is $(-3)!?$ – Igor Rivin Dec 17 '13 at 2:34
• I don't know. I had tried to do it with $x(x+1)...(x+n-1)$ instead of $\dfrac{(x+n-1)!}{(x-1)!}$, then replaced $x$ by $-x$. The result turned out to be 0 since $(-2)(-1)(0)(1)...(n-3)=0$. – user116267 Dec 17 '13 at 3:01

You can use the well known identity

$$(x)_n = \sum_{k=0}^n s(n,k) x^k,$$

where $(x)_n = x(x-1)\dots(x-n+1)$. Now, you can easily prove that

$$(x)_n = \frac{x!}{(x-n)!}.$$

I think you can finish the problem.

• Thanks! I could factor $-1$ out from each term on the right hand-side of my equation and I will get $(x)_n$. – user116267 Dec 17 '13 at 3:05
• @user116267: You are welcome. – Mhenni Benghorbal Dec 17 '13 at 3:08

This can also be done with the exponential generating function of the Stirling numbers of the first kind, which says that $$\left[n\atop k\right] = n! [z^n] [u^k] \exp\left(u\log\frac{1}{1-z}\right) = n! [z^n] [u^k] \left(\frac{1}{1-z}\right)^u.$$ It follows that $$2^k \left[n\atop k\right] = n! [z^n] [u^k] \left(\frac{1}{1-z}\right)^{2u}.$$ This yields $$\sum_{k=0}^n 2^k \left[n\atop k\right] = n! [z^n] [u^n] \frac{1}{1-u} \left(\frac{1}{1-z}\right)^{2u} \\= n! [u^n] \frac{1}{1-u} {n+2u-1\choose n} = n! \left. {n+2u-1\choose n}\right|_{u=1} = n! {n+1\choose n} = (n+1)!$$