That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level...

As i said there, i'm working on a monograph about partitions, and one topic covered is the Simon Newcomb's problem. My main guide is the amazing "The Theory of Partitions", by George Andrews. I had two problems in understand some proofs on the book: one was solved by my question at MO, and the other is explained below.

The following lemma is in Andrews' book...


Let $r$ be an integer, and let $a_1, a_2, a_3, \ldots, b_1, b_2, b_3, \ldots$ be any numbers. Each of the following relations implies the other:

$ \begin{align} \label{first_eq} \tag{1} &a_n = \sum_{j=0}^{n-1}\binom{r - n + j}{j}b_{n-j}, \quad \forall n\geq 1;\\ \label{second_eq} \tag{2} &b_n = \sum_{j=0}^{n-1}\binom{r - n + j}{j}(-1)^{j}a_{n-j}, \quad \forall n\geq 1. \end{align} $

I'm asking for an elementary, self-contained proof with no use of Chu-Vandermonde summation. If it uses generating functions, better, but binomial identities would be great too.

An obvious hint by Andrews is that one can just proof that (2) implies (1), because once it was done, a simple "variable change" proves the reverse implication, i.e., just consider $b'_{n} = (-1)^{n}b_n$ and $a'_{n} = (-1)^{n}a_n$.

I'm sorry for this basic question, and thanks in advance for the attention!

  • 1
    $\begingroup$ What is $r$? Assuming the formula is correct as written, this seems to be a variant of the binomial inversion formula. The natural ways to try to prove this would be through the use of generating functions. Any introductory book on combinatorics that includes a discussion of generating functions should have the binomial inversion formula as one of the examples/exercises in it. $\endgroup$ – Michael Joyce Oct 20 '11 at 14:44
  • 1
    $\begingroup$ One interpretation of your pair of identities is that it is an easy task to invert Pascal matrices... $\endgroup$ – J. M. isn't a mathematician Oct 20 '11 at 14:55
  • $\begingroup$ @sweetjazz: $r$ is a positive integer. I tried to prove with generating function, but my knowledge of GF is not so great, and unfortunatelly i wasn't able to demonstrate. $\endgroup$ – Guilherme Oct 20 '11 at 15:23
  • 1
    $\begingroup$ It actually works for arbitrary real $r$ as long as you define $z \choose k$ for arbitrary real $z$ and integer $k$. $\endgroup$ – Thomas Andrews Oct 20 '11 at 15:55
  • $\begingroup$ @Thomas Andrews: You are right...but in the scope of my problem, $r$ positive integer suffices!Thanks nevertheless... $\endgroup$ – Guilherme Oct 20 '11 at 16:55

Consider the formal series $$ \begin{array}{}f(x)=\sum_{n=1}^\infty a_nx^n&\text{and}&g(x)=\sum_{n=1}^\infty b_nx^n\end{array} $$ Then \eqref{first_eq} is equivalent to $$ \begin{align} f(x) &=\sum_{n=1}^\infty\sum_{j=0}^{n-1}\binom{r-n+j}{j}b_{n-j}x^n\\ &=\sum_{n=1}^\infty\sum_{j=1}^{n}\binom{r-j}{n-j}b_jx^n\\ &=\sum_{j=1}^\infty\sum_{n=j}^{\infty}\binom{r-j}{n-j}b_jx^n\\ &=\sum_{j=1}^\infty\sum_{n=0}^{\infty}\binom{r-j}{n}b_jx^{n+j}\\ &=\sum_{j=1}^\infty b_j(1+x)^{r-j}x^{j}\\ &=(1+x)^rg\left(\frac{x}{1+x}\right) \label{a}\tag{a} \end{align} $$ and \eqref{second_eq} is equivalent to $$ \begin{align} g(x) &=\sum_{n=1}^\infty\sum_{j=0}^{n-1}\binom{r-n+j}{j}(-1)^ja_{n-j}x^n\\ &=\sum_{n=1}^\infty\sum_{j=1}^{n}\binom{r-j}{n-j}(-1)^{n-j}a_jx^n\\ &=\sum_{j=1}^\infty\sum_{n=j}^{\infty}\binom{r-j}{n-j}(-1)^{n-j}a_jx^n\\ &=\sum_{j=1}^\infty\sum_{n=0}^{\infty}\binom{r-j}{n}(-1)^na_jx^{n+j}\\ &=\sum_{j=1}^\infty a_j(1-x)^{r-j}x^{j}\\ &=(1-x)^rf\left(\frac{x}{1-x}\right) \label{b}\tag{b} \end{align} $$ Simple algebraic substitutions yield that \eqref{a} and \eqref{b} are equivalent. Thus, \eqref{first_eq} and \eqref{second_eq} are equivalent.

| cite | improve this answer | |
  • $\begingroup$ Outstanding proof...just what i need ! Thanks very much for spent your time with my question... $\endgroup$ – Guilherme Oct 20 '11 at 16:56
  • 1
    $\begingroup$ Guilherme, thank @MikeSpivey. If he hadn't posted his answer before I finished the previous answer I was working on, I wouldn't have written this one. $\endgroup$ – robjohn Oct 20 '11 at 20:15
  • $\begingroup$ Professor Mike Spivey saved my week...he helps me a lot, both here and at MO...so thanks again professor ! I like this kind of generating function proof, 'cause it so straightfoward... $\endgroup$ – Guilherme Oct 21 '11 at 2:41

As noted in the comments, this is a variation of the binomial inversion formula $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$. For proofs of this formula (which I will use), see this math.SE question. It can also be proved easily using the trinomial revision formula I cite below. From another perspective, binomial inversion says that the Pascal matrix is (up to sign) its own inverse. For more on that see "Combinatorial interpretation of binomial inversion" and my answer to "Stirling numbers and inverse matrices."

For your problem, I'll just prove that \eqref{second_eq} $\Rightarrow$ \eqref{first_eq}, since, as you note, that is sufficient.

First, reindex \eqref{first_eq} and \eqref{second_eq} to get the simpler forms $$a_n = \sum_{j=1}^n \binom{r-j}{n-j} b_j, \tag{1}$$ $$b_n = \sum_{j=1}^n \binom{r-j}{n-j} (-1)^{n-j} a_j. \tag{2}$$

Assuming that (2) is true, and starting with the right-hand side of (1), we have $$\sum_{j=1}^n \binom{r-j}{n-j} b_j = \sum_{j=1}^n \binom{r-j}{n-j} \sum_{k=1}^j \binom{r-k}{j-k} (-1)^{j-k} a_k = \sum_{k=1}^n \sum_{j=k}^n \binom{r-j}{n-j} \binom{r-k}{j-k} (-1)^{j-k} a_k.$$ Now, apply the trinomial revision formula $\binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}$. (This is easy to prove; just write out the binomial coefficients in factorial form and regroup. For a reference, see Concrete Mathematics, 2nd edition, p. 168.) We get $$\sum_{k=1}^n \sum_{j=k}^n \frac{\binom{r}{n} \binom{n}{j}}{\binom{r}{j}} \frac{\binom{r}{j} \binom{j}{k}}{\binom{r}{k}} (-1)^{j-k} a_k = \sum_{k=1}^n \frac{\binom{r}{n}}{\binom{r}{k}} a_k \sum_{j=k}^n \binom{n}{j} \binom{j}{k} (-1)^{j-k} .$$ Then, binomial inversion yields $$=\sum_{k=1}^n \frac{\binom{r}{n}}{\binom{r}{k}} a_k \delta_{nk} = \frac{\binom{r}{n}}{\binom{r}{n}} a_n = a_n.$$

| cite | improve this answer | |
  • $\begingroup$ Curse you! I had nearly completed a similar proof when your answer came in. So I started over with a generating function proof. :-) $\endgroup$ – robjohn Oct 20 '11 at 16:34
  • $\begingroup$ @robjohn: I don't know how many times on this site someone else has barely beat me to the same answer. :-) $\endgroup$ – Mike Spivey Oct 20 '11 at 16:37
  • 1
    $\begingroup$ @Guilherme: You're welcome; glad I could help. $\endgroup$ – Mike Spivey Oct 20 '11 at 17:15
  • 1
    $\begingroup$ Careful with those fractions: their denominators $\dbinom{r}{j}$ and $\dbinom{r}{k}$ may be zero. $\endgroup$ – darij grinberg Jul 30 '18 at 0:07
  • 1
    $\begingroup$ Better use trinomial revision to simplify $\dbinom{r-j}{n-j} \dbinom{r-k}{j-k}$ as $\dbinom{r-k}{r-n} \dbinom{n-k}{n-j}$; then use the formula for the alternating sum of a row of Pascal's triangle to obtain $\sum\limits_{j=k}^n \left(-1\right)^{j-k} \dbinom{n-k}{n-j} = \delta_{n, k}$, which simplifies everything down to the $a_n$ we're looking for. $\endgroup$ – darij grinberg Jul 30 '18 at 0:11

It's pretty easy to brute-force this proof, just by substitution and two basic identities. It's actually true for arbitrary $r\in\mathbb{R}$, as long as you define $z\choose k$ for arbitrary real $z$ and non-negative integers $k$.

Given (1), replace the $a_{n-j}$ in the right hand side of (2) to get that you want:

$$b_n = \sum_{j=0}^{n-1} \sum_{k=0}^{n-j-1} (-1)^j {{r-n+j}\choose j}{{r-n+j+k}\choose k} b_{n-j-k}$$

Gathering terms, the coefficient of $b_{n-m}$ in the right hand side is (noting that j+k=m, or that k=m-j):

$$\sum_{j=0}^{m} (-1)^j{{r-n+j}\choose j}{r-n+m \choose m-j}$$

Note this is a function of $r-n$, so we can write:

$$f_m(z) = \sum_{j=0}^m (-1)^j{z+j \choose j}{z+m \choose m-j}$$

So, the right hand side of (2), after substitution, is:

$$\sum_{m=0}^{n-1} f_m(n-r) b_{n-m}$$

But ${z+m \choose m-j}{z+j \choose j} = {z+m \choose m} {m \choose j}$. You can see this algebraically pretty easily, or you can prove it combinatorially for non-negative integers $z$, and then use that both sides are polynomials of degree $m$ in $z$, so they must agree everywhere.


$$f_m(z) = {z+m \choose m} \sum_{j=0}^m (-1)^j {m \choose j} = {z+m \choose m} (1+(-1))^m$$

And therefore $f_m(z)=0$ if $m>0$, and $f_0(z)=1$.

But that means that the right hand side of (2) is equal to $b_n$.

| cite | improve this answer | |
  • $\begingroup$ This proof is very good too, thanks! In fact, Andrews' proof is similar to yours... $\endgroup$ – Guilherme Oct 20 '11 at 17:00

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.