Monotonicity of $M$-sequence

Question

Consider the following definition in the second page of this article:

For any two integers $k,n\ge 1$, there is a unique way of writing $$n=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\dots+\binom{a_i}{i}$$ so that $a_k > a_{k-1} > \dots > a_i\geq i > 0$. Define $$\partial_{k-1}(n) = \binom{a_k}{k-1}+\binom{a_{k-1}}{k-2}+\dots+\binom{a_i}{i-1}.$$

Is it true that when $k$ is fixed, the function $\partial_{k-1}(n)$ is weakly increasing in $n$? It does not look straightforward to prove this directly, but I assume it has already been shown somewhere.

Answer 1

The reason is that this ordering is lexicographic. We may induct on $k$. The base $k=1$ is clear. Assume that $n>m$ and \begin{align*} n=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\ldots+\binom{a_i}{i},a_k>a_{k-1}>\ldots>a_i\geqslant i,\\ m=\binom{b_k}{k}+\binom{b_{k-1}}{k-1}+\ldots+\binom{b_j}{j},b_k>b_{k-1}>\ldots>b_j\geqslant j. \end{align*} If $a_k>b_k$, then $$ \partial_{k-1}(n)\geqslant \binom{a_k}{k-1}\geqslant \binom{b_k+1}{k-1}=\binom{b_k}{k-1}+\binom{b_k}{k-2}=\\ \binom{b_k}{k-1}+\binom{b_k-1}{k-2}+\binom{b_k-1}{k-3}=\ldots=\\ \binom{b_k}{k-1}+\binom{b_k-1}{k-2}+\binom{b_k-2}{k-3}+\ldots+\binom{b_k-k+j+1}{j}+\binom{b_k-k+j+1}{j-1}\geqslant \\ \binom{b_k}{k-1}+\binom{b_{k-1}}{k-2}+\binom{b_{k-2}}{k-3}+\ldots+\binom{b_{j+1}}{j}+\binom{b_{j+1}}{j-1}>\partial_{k-1}(m). $$ If $a_k=b_k$, they cancel and we use induction. If $a_k<b_k$, then $m>n$ by the same reasoning as above.

Answer 2

It is not hard to show that $0 \leq \delta_{k-1}(n)-\delta_{k-1}(n-1) \leq k-1$ and to say when each possible jump happens.

Let me first alter the notation by setting $a_j=j+t_j.$

For any two integers $k,n\ge 1$, there is a unique way of writing $$n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+t_i}{i}$$ so that $i \geq 1$ and $t_k\geq t_{k-1} \geq \dots \geq t_i\geq 0$.

Define $$\partial_{k-1}(n) = \binom{k+t_k}{k-1}+\binom{k-1+t_{k-1}}{k-2}+\dots+\binom{i+t_i}{i-1}.$$

CLAIM: Let $n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+t_i}{i}>1$ as above.

If $t_i = 0$ then

• $n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}+\binom{i}{i}$

• $n-1=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}$

• $\delta_{k-1}(n)-\delta_{k-1}(n-1)=i$.

If $t_i>0$ then

• $n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}+\binom{i+t_i}{i}$

• $n-1=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}+\binom{i+t_i-1}{i}+\binom{i-1+t_i-1}{i-1}+\cdots+\binom{1+t_i-1}{1}$

• $\delta_{k-1}(n)-\delta_{k-1}(n-1)=0$.

---

Note that if the expansion above for $n$ is according to the requirements then the expansion claimed for $n-1$ also meets the requirement. That it is actually equal to $n-1$ is clear in the case $t_i=0$ and for the case $t_i \gt 0$ follows from this familiar fact:

For $a \gt i$ and $i \geq 1$ we have $$\binom{a}{i}=\binom{a-1}{i}+\binom{a-2}{i-1}+\cdots+\binom{a-i}{1}+\binom{a-i-1}{0}$$ Switching to the $t$ notation:$$\binom{i+t}{i}=\binom{i+t-1}{i}+\binom{i-1+t-1}{i-1}+\cdots+\binom{1+t-1}{1}+1$$

That $\delta_{k-1}(n)-\delta_{k-1}(n-1)=i$ when $t_i=0$ is clear and that $\delta_{k-1}(n)=\delta_{k-1}(n-1)$ when $t_i \gt 0$ follows from writing the same fact as

$$\binom{i+t}{i-1}=\binom{i+t-1}{i-2}+\binom{i-1+t-1}{i-2}+\cdots+\binom{1+t-1}{0}$$