Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.