12 votos

Un trivial combinatoria resultado que he encontrado, es mi prueba correcta?

Acabo de terminar la secundaria, y han comenzado a aprender por mi cuenta algunos combinatoria y cómo hacer las pruebas, y mientras cachondeo con sumas y triángulo de Pascal me he encontrado un interesante aún propiedad trivial que he tratado de demostrar. Estoy asumiendo que ya se ha encontrado, pero no pude encontrar nada de mencionarla.
Así que mis preguntas son: Es mi prueba correcta? Tiene esta propiedad ha encontrado ya? ¿Qué puede esta propiedad se utiliza para?

Deje $$f(x,n)= \sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2} \cdots \sum_{i_x=1}^{i_{x-1}}i_x \ $$ donde $x$ es el número de sigma sumas.

Mi conjetura es que el $$f(x,n)={n+x \choose x+1}$$

Prueba por inducción

Base a paso:
$$\begin{align} f(1,n) &=\sum_{i=1}^ni\\ &=\frac{n(n+1)}{2}\\ &={n+1 \choose 2} \end{align}$$ La base paso funciona. Este primer resultado ya ha sido probada para todo n.

Inductivo paso: Suponga que el $f(x,n)= {n+x \choose x+1} $

Ahora, $$\begin{align}f(x+1,n) &=\sum_{m=1}^n \sum_{i_1=1}^{m} \sum_{i_2=1}^{i_1} \cdots \sum_{i_x=1}^{i_{x-1}}i_x\\ &=\sum_{m=1}^n f(x,m)\\ &=\sum_{m=1}^n {m+x \choose x+1}\\ &=\sum_{l=0}^{n-1}{l+1+x \choose x+1}\\ &={n+x+1 \choose x+2}\\ \end{align}$$ Por lo tanto, si $f(x,n)$ sostiene, a continuación, $f(x+1,n)$ mantiene.
Lo que no estoy seguro es si tengo que usar la inducción para demostrar que esta propiedad tiene para cada entero $n$ como bueno,

5voto

Mihir Singhal Puntos 1223

La prueba es correcta, ya que se puede tratar a $n$ fijo. Usted no tiene que introducir en $n$ desde su base de caso tiene para todos los $n$. Si su base de caso había sido $x=n=0$, entonces sí, habría que introducir en $n$.

Sin embargo, también hay una manera más simple de demostrar esta identidad. En primer lugar, vamos a volver a escribir un poco:

$$f(x, n) = \sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2} \cdots \sum_{i_x=1}^{i_{x-1}} \sum_{i_{x+1}=1}^{i_x}1$$

Ahora, observe que esta cuenta el número de formas de elegir los $i_1, i_2, \ldots, i_{x+1}$ tal que $1 \le i_{x+1} \le i_x \le \ldots \le i_1 \le n$. Pero por Estrellas y Barras (también conocido como multichoose), esto es sólo $\binom{n+x}{x+1}$ como se desee.

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: