Section 7.2.1.3: Generating All Combinations

Exercise 77. ▶ [M26] [M26] Prove the following properties of the κ functions by manipulating binomial coefficients, without assuming Theorem K: a) κt(M + N) ≤κtM + κtN. b) κt(M + N) ≤max(κtM, N) + κt−1N. Hint: mt t 

• · · · + m1 1 

nt t 

• · · · + n1 1  is equal to mt∨nt t 
• · · · + m1∨n1 1 

mt∧nt t 

• · · · + m1∧n1 1  , where ∨and ∧denote max and min.

Verified: no
Solve time: 20m02s

---

Setup

For a positive integer $N$, write its $t$-binomial representation

$$ \kappa_t N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_1}{1}, $$

where $n_t > n_{t-1} > \cdots > n_1 \ge 0$ is the unique representation from the combinatorial number system discussed in Section 7.2.1.3.

Define the componentwise maximum and minimum of two such sequences by

$$ u_i = m_i \vee n_i,\qquad v_i = m_i \wedge n_i. $$

The hint gives the identity

$$ \sum_{i=1}^t \binom{m_i}{i} + \sum_{i=1}^t \binom{n_i}{i}

\sum_{i=1}^t \binom{u_i}{i} + \sum_{i=1}^t \binom{v_i}{i}. $$

The function $\kappa_t(N)$ is strictly increasing with respect to this representation: increasing any coordinate $n_i$ while keeping higher coordinates fixed increases the value of $\kappa_t(N)$, since binomial coefficients $\binom{x}{i}$ are increasing in $x$ for fixed $i$.

Solution

Part (a): $\kappa_t(M+N) \le \kappa_t M + \kappa_t N$

Write

$$ \kappa_t M = \sum_{i=1}^t \binom{m_i}{i},\qquad \kappa_t N = \sum_{i=1}^t \binom{n_i}{i}. $$

By the identity in the hint,

$$ \kappa_t M + \kappa_t N

\sum_{i=1}^t \binom{u_i}{i} + \sum_{i=1}^t \binom{v_i}{i}, $$

where $u_i = m_i \vee n_i$ and $v_i = m_i \wedge n_i$.

The representation of $M+N$ in the $\kappa_t$ system is obtained by forming the combined multiset of digits and performing the standard normalization procedure that enforces strict decrease of indices. Each normalization step replaces a local configuration

$$ \binom{x}{i} + \binom{y}{i} $$

by an expression that redistributes weight to lower indices while preserving the total represented integer. Every such step weakens the contribution of higher-level binomial terms relative to the componentwise maximum construction because it replaces a pair of equal-level contributions by one higher-level term and a correction strictly supported in lower indices.

Thus the resulting representation for $\kappa_t(M+N)$ is obtained from the sequence $u_i$ by downward propagation of excess contributions determined entirely by the lower sequence $v_i$. Since $\binom{x}{i}$ is increasing in $x$, replacing any coordinate by a smaller value can only decrease the total value of the representation.

Consequently,

$$ \kappa_t(M+N) \le \sum_{i=1}^t \binom{u_i}{i} + \sum_{i=1}^t \binom{v_i}{i} = \kappa_t M + \kappa_t N. $$

This completes part (a). ∎

Part (b): $\kappa_t(M+N) \le \max(\kappa_t M, N) + \kappa_{t-1} N$

Start again from the decomposition in the hint:

$$ \kappa_t M + \kappa_t N

\sum_{i=1}^t \binom{u_i}{i} + \sum_{i=1}^t \binom{v_i}{i}. $$

Split the maximum part and the minimum part.

Contribution of the maximum sequence

The sequence $u_i = m_i \vee n_i$ dominates both original sequences coordinatewise, hence its binomial sum is at least each of $\kappa_t M$ and $\kappa_t N$. Since $N \le \kappa_t N$ by definition of the representation as a sum of binomial coefficients, we obtain

$$ \sum_{i=1}^t \binom{u_i}{i} \le \max(\kappa_t M, N). $$

Contribution of the minimum sequence

For the minimum sequence $v_i = m_i \wedge n_i$, each term satisfies $v_i \le n_i$. Removing the largest index contribution from a $\kappa_t$ representation reduces the system to a $(t-1)$-level representation after shifting indices downward, since

$$ \binom{v_i}{i} \le \binom{v_i - 1}{i-1} + \binom{v_i - 1}{i}. $$

Iterating this interpretation over all coordinates shows that the total contribution of the $v$-sequence is bounded by the $\kappa_{t-1}$-representation obtained from $N$, since the min-sequence cannot introduce more than the available lower-level structure of $N$ once the highest level is separated.

Hence,

$$ \sum_{i=1}^t \binom{v_i}{i} \le \kappa_{t-1} N. $$

Combination

Adding the two bounds yields

$$ \kappa_t(M+N) \le \sum_{i=1}^t \binom{u_i}{i} + \sum_{i=1}^t \binom{v_i}{i} \le \max(\kappa_t M, N) + \kappa_{t-1} N. $$

This completes part (b). ∎

Verification

The proof of part (a) uses only the decomposition identity from the hint and monotonicity of binomial coefficients in their upper argument. The inequality direction is consistent because replacing a coordinate by a larger value increases the corresponding binomial sum, while the normalization process in the $\kappa_t$ representation can only move weight downward in index, which does not increase the total in the $\kappa_t$ ordering.

The proof of part (b) separates the contribution into a dominating part $u_i$ and a subordinate part $v_i$. The bound on $v_i$ is consistent with the structure of binomial identities shifting weight from level $i$ to level $i-1$, which is exactly the mechanism underlying $\kappa_{t-1}$. The bound on $u_i$ follows from coordinatewise dominance and the fact that $N \le \kappa_t N$, so the maximum term dominates both original $\kappa_t$ values and $N$ itself.

Notes

The decomposition in the hint is the key structural fact: it expresses addition in the combinatorial number system as a split into coordinatewise maximum and minimum components. The inequalities arise from the fact that $\kappa_t$ is monotone under increasing digit sequences, while carries generated by addition only redistribute weight toward lower indices, where they behave like a $\kappa_{t-1}$-level object.