I'm attempting to show that, given a positive integer $m$ and a non-zero constant $\lambda,$ the sequence $n\mapsto\lambda^nn^k$ satisfies the recurrence relation $$\sum_{j=0}^m\binom{m}{j}(-\lambda)^{m-j}a_{n+j}=0$$ for any integer $0\le k<m.$ I have reduced the problem to showing that $$\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k=0$$ for such $k.$ To prove the $k=0$ case, one need only apply the binomial theorem to $(1-1)^m,$ but I'm stymied trying to prove it for other such $k.$

I checked several examples specifically to make sure I hadn't erred along the way, and it seems that it's true. I also determined (quite by accident) the apparent identity $$\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^m=m!,$$ which I have no idea how to prove, either. This leads me to wonder how one could possibly go about determining a closed form for $f(k,m):=\sum_{j=0}^m\binom{m}{j}(-1)^{m-j}j^k.$

Any suggestions/hints (for finding a closed form, proving the identities, or proving the recurrence relation is satisfied) would be appreciated.


Recall that $[m]=\{1,2,\cdots ,m\}$ and $A^B=\{f:A\longrightarrow B:\text{ f function}\}$.>By inclusion exclusion:

$$\sum_{j=0}^m \binom{m}{j}(-1)^j(m-j)^m=m^m-\sum_{j=1}^m \binom{m}{j}(-1)^{j-1}(m-j)^m=|[m]^{[m]}\setminus \bigcup _{j=1}^m A_j\|,$$ such that $A_x=\{f\in [m]^{[m]}:x\not \in Im(f)\}$ so $|A_x|=(m-1)^m$ and if $x\neq y,$ $A_x\cap A_y=(m-2)^m$ and so on. But that set is nothing more than permutations because are functions from $[m]$ to $m$ that are surjective. And there are $m!$ of them.

  • $\begingroup$ Very nice! I almost can't believe that I missed the combinatorial approach. $\endgroup$ – Cameron Buie Jul 23 '17 at 20:29

This is (almost) the formula for the Stirling numbers of the second kind which count the partitions of $\{1,\dots,n\}$ into non-empty sets.

They have the generating function

$$ \sum_{n,m} \begin{Bmatrix} n \\ m \end{Bmatrix} \frac{x^n}{n!}y^m = \exp(y(e^x - 1)). $$


\begin{align} \begin{Bmatrix} n \\ m \end{Bmatrix} &= \left[ \frac{x^n}{n!}y^m \right] \exp(y(e^x - 1)) \\ &= \frac{1}{m!} \left[ \frac{x^n}{n!} \right] (e^x - 1)^m \\ &= \frac{1}{m!} \left[ \frac{x^n}{n!} \right] \sum_{j = 0}^m \binom{m}{j}e^{jx}(-1)^{m - j} \\ &= \frac{1}{m!} \sum_{j = 0}^m \binom{m}{j}j^n(-1)^{m - j}. \end{align}

So one has

$$ \sum_{j = 0}^m \binom{m}{j}j^n(-1)^{m - j} = m! \begin{Bmatrix} n \\ m \end{Bmatrix}. $$

The right hand side evaluates to $0$ when $n < m$ and to $m!$ when $n = m$.


$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{j = 0}^{m}{m \choose j}(-1)^{m - j}\,j^{k} & = \pars{-1}^{m}\sum_{j = 0}^{m}{m \choose j}(-1)^{\,j} \,\braces{k!\bracks{z^{k}}\expo{\,jz}} \\[5mm] & = \pars{-1}^{m}\,k!\bracks{z^{k}}\sum_{j = 0}^{m}{m \choose j}(-\expo{z})^{\,j} = \pars{-1}^{m}\,k!\bracks{z^{k}}\bracks{1 + \pars{-\expo{z}}}^{m} \\[5mm] & = k!\bracks{z^{k}}\pars{\expo{z} - 1}^{m} = k!\bracks{z^{k}}\bracks{m!\sum_{n = 0}^{\infty}{n \brace m}{z^{n} \over n!}} \end{align}

$\ds{{n \brace m}}$ is a Stirling Number of the Second Kind.

Then, \begin{align} \sum_{j = 0}^{m}{m \choose j}(-1)^{m - j}\,j^{k} & = k!\,m!{k \brace m}\,{1 \over k!} = \bbx{m!{k \brace m}} \end{align}

  • $\begingroup$ I'm afraid I don't follow the substitution $j^k=\left\{k!\left[z^k\right]e^{jz}\right\}.$ are the braces and brackets grouping symbols, or indicative of some functions? What is $z$? $\endgroup$ – Cameron Buie Jul 23 '17 at 15:47
  • $\begingroup$ @CameronBuie $\left[z^{k}\right]\mathrm{f}\left(z\right)$ denotes the coefficient of $z^{k}$ in the $\mathrm{f}\left(z\right)$ expansion in powers of $z$. Note that $\mathrm{e}^{jz} = \sum_{\ell = 0}^{\infty}{j^{\ell}z^{\ell} \over \ell!}$ such that $\left[z^{k}\right]\mathrm{e}^{jz} = {j^{k} \over k!}$. The braces $\left\{\right\}$ is just for grouping... Thanks for your remark. $\endgroup$ – Felix Marin Jul 23 '17 at 15:57

You don't need to know any combinatorics to solve your original problem, just linear algebra (which happens to have combinatorial consequences). Let $S$ denote the (forward) shift operator, which sends a sequence $a_n$ to the sequence

$$(Sa)_n = a_{n+1}.$$

Saying that a sequence satisfies a linear recurrence $a_{n+k} = c_{k-1} a_{n+k-1} + \dots + c_0 a_n$ is equivalent to saying that it satisfies

$$(S^k - c_{k-1} S^{k-1} - \dots - c_0) a = 0.$$

Here are some simple observations:

  1. $a_n = r^n$ satisfies $(S - r) a = 0$.
  2. $(S - 1)$ computes the forward difference $(\Delta a)_n = a_{n+1} - a_n$. The forward difference of a polynomial of degree $d$ is a polynomial of degree $d-1$, so it follows that $a_n = n^d$ satisfies $(S - 1)^{d+1} a = 0$.
  3. If $a_n = n^k r^n$ then

$$\boxed{ (S - r) a = (n + 1)^k r^{n+1} - n^k r^{n+1} = (\Delta n^k) r^{n+1} }.$$

This is the key computation. Induction gives

$$(S - r)^i a = (\Delta^i n^k) r^{n+i}$$

and hence

$$(S - r)^m a = 0, m \ge k + 1.$$

In fact it's possible to reformulate the entire theory of linear recurrences in terms of the shift operator; basically the point is that you can factor $S^k - c_{k-1} S^{k-1} - \dots$ into irreducible factors, as a polynomial in $S$.

The Stirling numbers appear implicitly in this computation as the value of $\Delta^i n^k$ at $0$. Here are some other notes regarding the patterns that have been described in this discussion so far:

  1. $$\Delta^i a = (S - 1)^i a = \sum_{j=0}^i (-1)^{i-j} {i \choose j} S^j a$$
  2. If $a_n = c_d n^d + \dots$ is a polynomial of degree $d$ with leading coefficient $c_d$, then $(\Delta a)_n = d c_d n^{d-1} + \dots$ is a polynomial of degree $d-1$ with leading coefficient $dc_d$.
  3. Inducting on 5 gives $(\Delta^d n^d) = d!$.

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.