Patrón con la tetración de sumas.

Question

Al tratar con una pregunta para encontrar una forma explícita para una secuencia, noté algo:

PS

PS

PS

PS

Pregunta:

¿Cómo puedo probar el patrón que estoy viendo?

Estoy pensando en la inducción, en cuyo caso se prueba el caso base. Pero luego, asumiendo que$$\sum_{x_0=0}^{n-1} 1=\frac{n}{1!}$ es verdadero, necesito mostrar que$$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1=\frac{n(n-1)}{2!}$ es verdadero. Pero, ¿cómo puedo escribir$$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1} 1= \frac{n(n-1)(n-2)}{3!}$, ya que la notación me preocupa, y cómo puedo ir desde allí?

Answer 1

Es un cascasded forma de la suma a lo largo de una diagonal del triángulo de Pascal, también conocido como el palo de hockey de la identidad, es decir, $$\sum_{r=0}^m \binom ra=\binom {m+1}{a+1}$$ Suponga $p$ los niveles de la cascada de sumatorias. Trabajar desde adentro hacia afuera tenemos $$\begin{align} &\quad \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \sum_{x_{p-3}=0}^{x_{p-4}-1} \sum_{x_{p-2}=0}^{x_{p-3}-1} \sum_{x_{p-1}=0}^{x_{p-2}-1} \quad \quad 1\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \sum_{x_{p-3}=0}^{x_{p-4}-1} \sum_{x_{p-2}=0}^{x_{p-3}-1} \underbrace{\sum_{x_{p-1}=0}^{x_{p-2}-1} \binom{x_{p-1}}0}\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \sum_{x_{p-3}=0}^{x_{p-4}-1} \underbrace{\sum_{x_{p-2}=0}^{x_{p-3}-1} \quad\binom{x_{p-2}}1}\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1}\cdots \underbrace{\sum_{x_{p-3}=0}^{x_{p-4}-1} \quad \binom{x_{p-3}}2}\\\\ &=\qquad\vdots\\\\ &= \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \underbrace{\sum_{x_2=0}^{x_1-1} \binom{x_2}{p-3}}\\ &= \sum_{x_0=0}^{n-1} \underbrace{\sum_{x_1=0}^{x_0-1} \;\;\;\binom{x_1}{p-2}}\\ &= \underbrace{\sum_{x_0=0}^{n-1} \quad\binom{x_0}{p-1}}\\ &= \qquad\binom{n}{p} \end{align}$$ es decir, $$\color{red}{\boxed{\sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\sum_{x_2=0}^{x_1-1} \cdots \sum_{x_{p-1}=0}^{x_{p-2}-1}1=\binom np}}$$ Poner a $p=4$ da la última ecuación en su pregunta, es decir, $$\begin{align} &\quad \sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\sum_{x_2=0}^{x_1-1} \sum_{x_{3}=0}^{x_{2}-1}1\\ &=\sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\sum_{x_2=0}^{x_1-1}\binom{x_2}1\\ &=\sum_{x_0=0}^{n-1}\sum_{x_1=0}^{x_0-1}\binom{x_1}2\\ &=\sum_{x_0=0}^{n-1}\binom{x_0}3\\ &=\binom n4\\ &=\frac {n(n-1)(n-2)(n-3)}{4!}\end{align}$$

Answer 2

Cambiaré un poco tu notación y usaré$x_{-1}\equiv n$ en su lugar.

Sugerencia : para$m>0$, $$ \ sum_ {x_ {0} = 0} ^ {x _ {- 1} -1} \ cdots \ sum_ {x_ {m} = 0} ^ {x_ {m-1 } -1} 1 = \ sum_ {x_ {0} = 0} ^ {x _ {- 1} -1} \ left [\ sum_ {x_ {1} = 0} ^ {x_ {0} -1} \ cdots \ sum_ {x_ {m} = 0} ^ {x_ {m-1} -1} 1 \ right] = \ cdots $$ En este punto, debe usar una hipótesis de inducción sobre la suma interna.

Answer 3

Tenga en cuenta que podemos desarrollar un argumento combinatorio que proporcione el número total de formas como${n\choose r}$ donde r es el número total de sumas