Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can anyone suggest how to touch this?

My task:

Prove that if sequences $a, b$ satisfy: $$ b_{n} = \sum_{k}^{}\left[n\atop k\right]a_{k} $$ then this equation is correct for their exponential generating functions $A, B$: $$ B(x) = A\left(\log\frac{1}{1-x}\right) $$

Where $\left[n\atop k\right]$ are Stirling numbers of the first kind.

I would be grateful for any help.

share|cite|improve this question
What result do you know about Stirling numbers of the first kind and generating functions? – Did Mar 15 '12 at 17:50
Do you know the exponential generating function $$\left(\ln\frac1{1-x}\right)^m=m!\sum_{n\ge 0}\left[n\atop m\right]\frac{x^n}{n!}\;?$$ – Brian M. Scott Mar 15 '12 at 18:06
Re proof strategy, the result is a consequence of an interversion of the order of summations in a double summation--as I am ready to explain if you answer my first comment. – Did Mar 15 '12 at 20:26
Here's what I've got so far: $$ B(n) = \sum_{n}^{}b_{n} \frac{x^{n}}{n!} = \sum_{n}^{}\sum_{k}^{}\left[n\atop k\right]a_{k} \frac{x^{n}}{n!} = \sum_{n}^{}\sum_{k}^{}a_{k}\left[n\atop k\right]\frac{x^{k}}{k!} =\ ? $$ I understand that I need to change the order of summation, and therefore I'll be able to use a formula mentioned by Brian, and finally get $$ \sum_{n}^{}a_{n}\frac{(\log\frac{1}{1-x})^{n}}{n!} = A(\log\frac{1}{1-x}) $$ But how do I do that? I don't understand how to change summation from the lower argument of a Stirling number to the upper one, so it will fit the formula.. – Maria McKee Mar 15 '12 at 21:07
And answering the first question, I'm familiar with several formulas regarding Stirling numbers and generating functions. My source - Concrete Mathematics - is actually full of them:) – Maria McKee Mar 15 '12 at 21:14
up vote 1 down vote accepted

Let $A(x)$ be the exponential generating function for $a_n$, i.e. $\frac{d^n}{dx^n}A(0)=a_n$, and let $B(x)=A(\log(\frac{1}{1-x}))$.

We need to show that $\frac{d^n}{dx^n}B(0)=b_n$.

Let us find an expression for $\frac{d^n}{dx^n}B(x)$ using Stirling coefficients: $$\frac{d^n}{dx^n}B(x)=\sum_{k=1}^n\left[\matrix{n\\k}\right]a_k^n(x)A^{(k)}(-\log(1-x)).$$

We have $$\frac{d^{n+1}}{dx^{n+1}}B(x)=\sum_{k=1}^n\left[\matrix{n \\ k}\right]\left(a_k^{n'}(x)A^{(k)}(-\log(1-x))+\frac{a_k^n(x)}{1-x}A^{(k+1)}(-\log(1-x))\right)=a_1^{n'}(x)A^{(1)}(-\log(1-x))+\frac{a_n^n(x)}{1-x}A^{(n+1)}(-\log(1-x))+\sum_{k=2}^n\left(\left[\matrix{n \\ k}\right]a_k^{n'}(x)+\left[\matrix{n \\ k-1}\right]\frac{a_{k-1}^n(x)}{1-x}\right)A^{(k)}(-\log(1-x))=\sum_{k=1}^{n+1}\left(\left[\matrix{n \\ k}\right]a_k^{n'}(x)+\left[\matrix{n \\ k-1}\right]\frac{a_{k-1}^n(x)}{1-x}\right)A^{(k)}(-\log(1-x))$$

So we need $a_k^n(x)$ to be such that $\left[\matrix{n \\ k}\right]a_k^{n'}(x)+\left[\matrix{n \\ k-1}\right]\frac{a_{k-1}^n(x)}{1-x}=\left[\matrix{n+1 \\ k}\right]a_k^{n+1}(x)$. Also, we need $a_1^1(x)=\frac{1}{1-x}$.

Note that $n\left[\matrix{n \\ k}\right]+\left[\matrix{n \\ k-1}\right]=\left[\matrix{n+1 \\ k}\right]$. Therefore, we obtain the following expressions: $$a_k^n(x)=(1-x)^{-n}$$ and $$\frac{d^n}{dx^n}B(x)=\frac{1}{(1-x)^n}\sum_{k=1}^n\left[\matrix{n\\k}\right]A^{(k)}(-\log(1-x)).$$

Now just plug in $x=0$ into the final expression.

share|cite|improve this answer

The generating function of Stirling numbers of the first kind is $$ \sum_{k=0}^{+\infty} u^k \sum_{n=k}^{+\infty} \frac {x^n}{n!} \left[{n\atop k}\right] = \mathrm e^{ut},\qquad\text{with}\ t=\log(1/(1-x)). $$ Expanding the exponential along the powers of $u$, this yields, for every $k\geqslant0$, $$ \sum_{n=k}^{+\infty} \frac {x^n}{n!} \left[{n\atop k}\right] = \frac{t^k}{k!}. $$ Hence, $B(x)=\sum\limits_{n=0}^{+\infty} b_n\frac {x^n}{n!}$ is $$ B(x)=\sum_{n=0}^{+\infty}\sum_{k=0}^n\left[{n\atop k}\right]a_k\frac {x^n}{n!}=\sum_{k=0}^{+\infty}a_k\sum_{n=k}^{+\infty}\left[{n\atop k}\right]\frac {x^n}{n!}=\sum_{k=0}^{+\infty}a_k\frac{t^k}{k!}=A(t). $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.