4
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Well, what is $(-3)!?$ $\endgroup$ – Igor Rivin Dec 17 '13 at 2:34
  • $\begingroup$ 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$. $\endgroup$ – user116267 Dec 17 '13 at 3:01
3
$\begingroup$

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.

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

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)!$$

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