3

The theorem and the first part of its proof is shown below: enter image description here

In particular, the authors conclude (2 lines below equation (2)) that

$(i): P_R(n) = {n + a_1 \choose a_1}+\cdots+ {n+a_r -(r-1) \choose a_r} + c$.

Question 1: Is there an immediate way to see how they arrived at this equation?

Question 2: It is not clear at first sight that $c$ is even an integer. Or it is? Anyway, the authors consider it obvious that $c$ is an integer and they proceed to show that it is non-negative via a rather complicated argument.

In trying to understand equation $(i)$ i came up with the following argument, which not only shows that $c$ is an integer, but that it is also non-negative:

My argument: There exists a unique expression

$(ii): P_R(n) = {n + a_1 \choose a_1}+{n + a_2-1 \choose a_2}+\cdots+ {n+a_s -(s-1) \choose a_s}$

with $a_1 \ge a_2 \ge \cdots \ge a_s \ge 0$. As in the argument in the proof, suppose that $P_R(n) - P_R(n-1)$ has a unique expression

$P_R(n) - P_R(n-1) = {n + b_1 \choose b_1}+\cdots+ {n+b_r -(r-1) \choose b_r}$

with $b_1 \ge b_2 \ge \cdots \ge b_r \ge 0$. Then using Pascal's triangle we must have that

${n + b_1 \choose b_1}+\cdots+ {n+b_r -(r-1) \choose b_r} = {n + a_1-1 \choose a_1-1}+\cdots+ {n+a_s-1 -(s-1) \choose a_s-1}$.

By the uniqueness of the expression on the left and the fact that $b_i \ge 0$ we can identify $a_i = b_i + 1$ for $i=1,\dots,r$ and we must also have that

${n + a_{r+1}-1-r \choose a_{r+1}-1}+\cdots+ {n+a_s-1 -(s-1) \choose a_s-1}=0$.

The only way this last equation can be satisfied is if $a_{r+1}=\cdots=a_s=0$. Substituting this in $(ii)$ we get precisely equation $(i)$, where $c:=s-r \ge 0$.

Question 3: Any comments regarding my argument?

user26857
  • 52,094
Manos
  • 25,833
  • At this moment I can't see any flaw in your argument. (The only thing I'd change is that $a_{r+1}=⋯=a_s=0$ follows from the uniqueness, no need to write that sum equal to $0$.) – user26857 Dec 21 '14 at 18:37
  • @user26857: So basically we are using the uniqueness of the expression in exercise 4.2.17, right? Strange however that the exercise itself does not mention anything about uniqueness. – Manos Dec 21 '14 at 19:26
  • I'd say so. Anyway, the uniqueness is out of any doubt. – user26857 Dec 21 '14 at 19:34
  • @user26857: How do you see that the uniqueness is out of any doubt? – Manos Dec 21 '14 at 19:38
  • That equality for any $n\in\mathbb Z$ says that $P_R(X)$ is a sum of "combinatorial" polynomials and this is unique (by degree arguments). – user26857 Dec 21 '14 at 19:50

1 Answers1

2

It seems they used $P_R(k) - P_R(k-1) = {k + b_1 \choose b_1}+\cdots+ {k+b_r -(r-1) \choose b_r}$ by summing these up for $k=1,\dots,n$ and using the well known combinatorial identity $\sum_{k=0}^n{k + b_1 \choose b_1}={n + b_1 + 1\choose b_1 + 1}$. Then $c$ is nothing but $P_R(0)-1$ which is obviously an integer.

user26857
  • 52,094