Cada número entero es la única suma de una secuencia "decreciente" de coeficientes binomiales

Question

Necesito un consejo ya que tengo problemas con el siguiente ejercicio de combinatoria.

Dejemos que $k$ sea un número entero positivo dado. Demostrar que cualquier entero no negativo $N$ puede escribirse de forma única en la forma

$$N=\binom{x_k}{k}+\binom{x_{k-1}}{k-1}+\dots+\binom{x_1}{1},$$

donde $0 \leq x_1 < \dots < x_{k-1} < x_k$ .

El ejercicio va acompañado de este consejo:

Dejemos que $x$ sea tal que $\binom{x}{k} \leq N < \binom{x+1}{k}$ . Entonces cualquier representación posible tiene $x_k = x$ . Ahora utiliza la inducción y el hecho de que $N-\binom{x}{k} < \binom{x}{k-1}$ para demostrar la existencia y la unicidad de la representación.

Estoy realmente atascado y por ello agradezco la más mínima pista sobre cómo solucionarlo.

Answer 1

Tome como hipótesis de inducción la afirmación de que si $M$ es un número entero no negativo menor que $N$ y $\ell$ es cualquier número entero positivo, entonces hay una descomposición única

$$M=\binom{x_\ell}\ell+\binom{x_{\ell-1}}{\ell-1}+\ldots+\binom{x_1}1$$

con $0\le x_1<x_2<\ldots<x_\ell$ .

Existe ciertamente un único número entero no negativo $x$ tal que $\binom{x}k\le N<\binom{x+1}k$ . Lo primero que hay que comprobar es que es la única opción posible para $x_k$ . Ciertamente, nada más grande puede funcionar. ¿Y si empezamos con algunos $x_k<x$ ? Entonces el mayor total posible que podemos obtener es

$$\begin{align*} \binom{x-1}k+\binom{x-2}{k-1}+\ldots+\binom{x-k}1&=\sum_{i=1}^k\binom{x-k-1+i}i\\\\ &=\sum_{i=1}^k\binom{x-k-1+i}{x-k-1}\\\\ &=\binom{x}{x-k}-\binom{x-k-1}0\\\\ &=\binom{x}k-1\\\\ &<N\;. \end{align*}$$

Así que fijamos $x_k=x$ y que $N_1=N-\dbinom{x_k}k$ . Verifique que $N_1<N$ . Si $N_1=0$ has terminado. Si no, la hipótesis de inducción te da una descomposición única

$$N_1=\binom{x_{k-1}}{k-1}+\ldots+\binom{x_1}1$$

tal que $0\le x_1<\ldots<x_{k-1}$ . Para terminar, sólo hay que mostrar que $x_{k-1}$ en esta descomposición es necesariamente menor que $x_k$ la pista que se le da es utilizar el hecho de que $N_1<\dbinom{x_k}{k-1}$ . Para ver por qué esto es cierto, supongamos por el contrario que $x_{k-1}\ge x_k$ y considera lo que esto dice sobre $\dbinom{x_k}k+\dbinom{x_{k-1}}{k-1}$ en vista de la identidad de Pascal.