9 votos

entero como suma de tres binomios

Demostrar que para cualquier entero no negativo $n$ $\exists x,y,z \in \mathbb{N}$ et $0\leq x<y<z$ así que $$n=\binom{x}{1}+\binom{y}{2}+\binom{z}{3}$$

Por favor, dame una pista, no tengo ni idea.

0 votos

No funciona para $n=1$ .

3 votos

@Martigan , funciona: x = 0, y = 1, z = 3

0 votos

$0!=1$ por lo que no funciona....

3voto

Considere $z_m={m\choose 3}$ para todos $m$ . Diferencia $z_{m+1}-z_{m}=\frac{m(m-1)}{2}$ . Elegimos $m$ que $z_m$ es máxima, no superior a $n$ .
La mayor diferencia $n_y=n-z_m$ que tendríamos que cubrir, es $\frac{m(m-1)}{2}-1$ .
Ahora elegimos $y_k={k\choose 2}$ sea máxima, no superior a $n_y$ . Obsérvese que maximal $k$ podría ser $m-1$ ya que $\frac{m(m-1)}{2}-1$ es el valor máximo de $n_y$ (es decir, no puede ser $\ge\frac{m(m-1)}{2}$ ). Analógicamente, $y_{k+1}-y_k-1=k-1$ es el valor máximo a cubrir con $x$ .
Por lo tanto, seleccionamos $y=k$ et $z=m$ .

2voto

NP-hard Puntos 1872

Es fácil ver que $$ 1 = {x_1 \choose 1}+{y_1 \choose 2}+{z_1 \choose 3} $$ donde $x_1 = 0$ , $y_1 = 1$ , $z_1 = 3$ .

Supongamos $$ i = {x_i \choose 1}+{y_i \choose 2}+{z_i \choose 3} $$ donde $0 \leq x_i < y_i < z_i$ . Queremos decidir $0 \leq x_{i+1} < y_{i+1}<z_{i+1}$ tal que $$ i + 1 = {x_{i+1} \choose 1}+{y_{i+1} \choose 2}+{z_{i+1} \choose 3} $$


Proporciono un procedimiento para decidir $x_{i+1}, y_{i+1}, z_{i+1}$ abajo.

  • si $x_i < y_i - 1$

Sea $x_{i+1} = x_i + 1, y_{i+1} = y_i, z_{i+1} = z_i$ . Es fácil ver que la suma incremento $1$ .

  • si $x_i = y_i - 1\textbf{ and }y_i < z_i - 1$

Sea $x_{i+1} = 0, y_{i+1} = y_i + 1, z_{i+1} = z_i$ . Tenemos \begin{align} &{z_{i+1} \choose 3} + {y_{i + 1} \choose 2}+{x_{i+1} \choose 1} - {z_i \choose 3} - {y_i \choose 2}-{x_i \choose 1}\\ =& {z_i \choose 3} + {y_i + 1 \choose 2}+{0 \choose 1} - {z_i \choose 3} -{y_i \choose 2} - {y_i - 1 \choose 1} \\ =& \frac{(y_i + 1)y_i}{2} + 0 - \frac{y_i(y_i - 1)}{2} - (y_i - 1)\\ =& 1 \end{align}

  • si $x_i = y_i - 1\textbf{ and }y_i = z_i - 1$

Sea $x_{i+1} = 0, y_{i+1} = 1, z_{i+1} = z_i + 1$ . Tenemos \begin{align} &{z_{i+1} \choose 3} + {y_{i + 1} \choose 2}+{x_{i+1} \choose 1} - {z_i \choose 3} - {y_i \choose 2}-{x_i \choose 1}\\ =& {z_i + 1 \choose 3} + {1 \choose 2}+{0 \choose 1} - {z_i \choose 3} -{z_i - 1 \choose 2} - {z_i - 2 \choose 1} \\ =& \frac{(z_i + 1)z_i(z_i - 1)}{6} + 0 + 0 - \frac{z_i(z_i-1)(z_i-2)}{6} - \frac{(z_i - 1)(z_i - 2)}{2} - (z_i - 2)\\ =& \frac{z_i(z_i - 1)}{2} - \frac{(z_i-1)(z_i - 2)}{2} - (z_i - 2)\\ =& 1 \end{align}

Obsérvese que el procedimiento garantiza $0 \leq x_{i+1} < y_{i+1} < z_{i+1}$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X