MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Suppose we have a triangle of numbers defined by the recurrence relation $$\left| n \atop k \right| = f(n,k) \left| n-1 \atop k \right| +g(n,k) \left| n-1 \atop k-1 \right| + [n=k=0],$$ for some functions $f(n,k)$ and $g(n,k)$.

What general conditions exist that imply, for all sufficiently large $n$, $$S(n) = \sum_{k=0}^n \left| n \atop k \right| = 0?$$

There are two that I know of.

First: If $g(n,k) = -f(n,k-1)$ then the recursion immediately yields a zero row sum.

Three examples, for $f(n,k) = 1, f(n,k)= k$, and (more esoterically) $f(n,k) = (k+1)(2n-k-2)(2n-k-3)$, respectively: $$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0, \text{ for } n \geq 1,$$ $$\sum_{k=1}^n (-1)^k (k-1)! \left\{ n \atop k \right\} = 0, \text{ for } n \geq 2,$$ $$\sum_{k=0}^{n} (-1)^k k!(2n-k-2)!\left\langle\left\langle n\atop k\right\rangle\right\rangle=0, \text{ for } n \geq 2,$$ where $\left\langle\left\langle n\atop k\right\rangle\right\rangle$ is a second-order Eulerian number. (The third identity appears in this question and was partly the inspiration for my question.)

Second: If $f(n,k) + g(n,k) = q(n)$ (i.e., independent of $k$) and $q(n) =0$ for some $n$, then $\sum_{k=0}^m \left| m \atop k \right| = 0$ for all $m \geq n$.

(See, for example, Theorem 17 of Neuwirth, "Recursively defined combinatorial functions: Extending Galton's board," Discrete Mathematics, 2001. This result states that if $f(n,k) + g(n,k) = q(n)$, then the row sum $S(n)$ satisfies the recurrence $S(n) = q(n) S(n-1)$. )

For example, with $f(n,k) = n-1$ and $g(n,k) = -1$, we have $$\sum_{k=0}^n (-1)^k \left[ n \atop k \right] = 0 , n \geq 2.$$

Are there any other known general conditions?

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.