Demostraciones Matematicas problemas ejercicios preguntas consultas dudas ayuda apoyo, tareas. Foros. Tex, Latex Editor. Latexrender. Math help

jaromarm

Nuevo

Karma: +0/-0

Desconectado

Sexo: Masculino

El Salvador

Mensajes: 14

Suma de números combinatorios

« : 16/03/2012, 11:24:02 pm »

Hola buenas noches, he tratado de demostrar lo siguiente:

$\displaystyle\sum_{k=0}^m{(-1)^k \displaystyle\binom{m}{k} \cdot{} \displaystyle\binom{m+k}{k}}=(-1)^m$

sin éxito, agradecería me hacharen una manita! Gracias.


	En línea

Martingalo

Pleno

Karma: +0/-0

Desconectado

Sexo: Masculino

Norway

Mensajes: 116

Re: Suma de números combinatorios

« Respuesta #1 : 17/03/2012, 05:29:53 pm »

Hola,

Como sugiere el tipo de problema, demostrar la veracidad de la fórmula sale fácilmente por inducción. Observa que es cierta para

, suponla cierta para

y veamos que también lo es para

:

$\sum_{k=1}^{m+1} (-1)^k \begin{pmatrix}m \\ k \end{pmatrix} \begin{pmatrix}m+k \\ k \end{pmatrix}= \sum_{k=1}^{m} (-1)^k \begin{pmatrix}m \\ k \end{pmatrix} \begin{pmatrix}m+k \\ k \end{pmatrix}+(-1)^{m+1} \begin{pmatrix}m \\ m+1 \end{pmatrix}\begin{pmatrix}m+(m+1) \\ m+1 \end{pmatrix}=(-1)^m + (-1)^{m+1}\begin{pmatrix}m \\ m+1 \end{pmatrix}\begin{pmatrix}m+(m+1) \\ m+1 \end{pmatrix}$

(Partiendo la suma en dos y usando la hipótesis de inducción). Finalmente hay que sacar factor común de

:

$\dots=(-1)^m\left[ 1 -\begin{pmatrix}m \\ m+1 \end{pmatrix}\begin{pmatrix}m+(m+1) \\ m+1 \end{pmatrix}\right]$

y queda demostrar que el interior de las llaves es -1.

Saludos.


	En línea

$E\left[M_t|\mathcal{F}_s\right]=M_s$

pabloN

Moderador Global
Pleno*

Karma: +0/-0

Desconectado

Sexo: Masculino

Uruguay

Mensajes: 2.280

Re: Suma de números combinatorios

« Respuesta #2 : 17/03/2012, 05:58:49 pm »

Hola Martingalo

Cita de: Martingalo en 17/03/2012, 05:29:53 pm

Como sugiere el tipo de problema, demostrar la veracidad de la fórmula sale fácilmente por inducción.

A mi no me resulta tan fácil.

Cita de: Martingalo en 17/03/2012, 05:29:53 pm

${\sum_{k=1}^{m+1} (-1)^k \begin{pmatrix}m \\ k \end{pmatrix} \begin{pmatrix}m+k \\ k \end{pmatrix}= \sum_{k=1}^{m} (-1)^k \begin{pmatrix}m \\ k \end{pmatrix} \begin{pmatrix}m+k \\ k \end{pmatrix}+(-1)^{m+1} \begin{pmatrix}m \\ m+1 \end{pmatrix}\begin{pmatrix}m+(m+1) \\ m+1 \end{pmatrix}=(-1)^m + (-1)^{m+1}\begin{pmatrix}m \\ m+1 \end{pmatrix}\begin{pmatrix}m+(m+1) \\ m+1 \end{pmatrix}}$

Ahí hay dos errores. El primero es más bien una errata (y es que la sumatoria empieza desde

). El otro sí importa y es que la propiedad a probar es:

$P(m):=\quad \displaystyle\sum_{k=0}^m{(-1)^k \displaystyle\binom{m}{k} \cdot{} \displaystyle\binom{m+k}{k}}=(-1)^m$

Por lo tanto, en el paso inductivo (asumiendo que

es cierta) hay que probar:

$P({\red m+1}):=\quad \displaystyle\sum_{k=0}^{{\red m+1}}{(-1)^k \displaystyle\binom{{\red m+1}}{k} \cdot{} \displaystyle\binom{{\red m+1}+k}{k}}=(-1)^{\red m+1}$

Te has olvidado de sustituir

en los coeficientes binomiales. Justamente en ese punto radica la dificultad de hacer la prueba por inducción. Aún no me doy cuenta cómo aplicar la hipótesis inductiva. Algo parecido sucede en este ejercicio donde tampoco es inmediato aplicar la hipótesis de inducción. En este caso, capaz que sale aplicando alguna identidad combinatoria, pero habría que pensarlo mejor.


	En línea

I have a dream that one day no message of "Connection Problems" will appear. I still have a dream... :risa:

jaromarm

Nuevo

Karma: +0/-0

Desconectado

Sexo: Masculino

El Salvador

Mensajes: 14

Re: Suma de números combinatorios

« Respuesta #3 : 17/03/2012, 08:35:46 pm »

Gracias por el tiempo dedicado, en efecto ya había tratado por inducción y sin éxito, yo sigo trabajando en el problema también


	En línea

Martingalo

Pleno

Karma: +0/-0

Desconectado

Sexo: Masculino

Norway

Mensajes: 116

Re: Suma de números combinatorios

« Respuesta #4 : 18/03/2012, 06:48:34 am »

Uy, lo siento por el error! La verdad es que no lo he hecho, simplemente se me ocurrió que por inducción debería salir muy rápido, y es seguro que hay que usar alguna propiedad de los números combinatorios, así como se usa para demostrar el binomio de Newton.

Otra cuestión, será que el resultado es falso? :lengua_afuera:


	En línea

$E\left[M_t|\mathcal{F}_s\right]=M_s$

el_manco

Administrador
Pleno*

Karma: +0/-0

Desconectado

España

España

Mensajes: 25.228

Re: Suma de números combinatorios

« Respuesta #5 : 18/03/2012, 11:18:22 am »

Hola

El resultado es un caso particular de este otro más general:

$\color{red} \displaystyle\sum_{k=0}^n{}(-1)^{n-k}\displaystyle\binom{n}{k}p(k)=n!a_n\color{black}$ (1)

donde $p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x_1+a_0$ es un polinomio de grado menor o igual que

.

Basta aplicarlo al polinomio:

$p(x)=\dfrac{(x+1)(x+2)\ldots (x+m)}{m!}$

(si

es entero, $p(x)=\displaystyle\binom{m+x}{m}=\displaystyle\binom{m+x}{x}$ )

La prueba de (1) no es difícil. Se basa en:

i) Dado un polinomio

se llama derivada discreta de

al polinomio:

. Es inmediato ver que si

es un polinomio de grado

y coeficiente de mayor grado

, entonces

es un polinomio de grado

y coeficiente de mayor grado $na_{n}.$

ii) Inducitvamente se define a su vez la derivada discreta

-ésima de

mediante:

$p_k(x)=p_{k-1}(x+1)-p_{k-1}(x)$

siendo

, y es casi inmediato de probar por inducción que si

es un polinomio de grado

y coeficiente de mayor grado

, entonces

es un polinomio de grado

y coeficiente de mayor grado $n(n-1)\ldots (n-k+1)a_{n}.$

iii) Finalmente es muy fácil de probar por inducción que:

$p_k(x)=\displaystyle\sum_{i=0}^k{}(-1)^{k-i}\displaystyle\binom{k}{i}p(x+i)$

iv) De (ii) y (iii) si

es un polinomio de grado

y coeficiente de mayor grado

, entonces:

$n!a_n=p_n(0)=\displaystyle\sum_{i=0}^n{}(-1)^{n-i}\displaystyle\binom{n}{i}p(i)$

Saludos.

P.D. Si necesitas precisar alguna de las demostraciones dilo, pero son todas bastantes directas. Puedes incluso adaptar tu idea al caso particular que te compete con:

$p(x)=\dfrac{(x+1)(x+2)\ldots (x+m)}{m!}$

Aunque es una pérdida de generalidad innecesaria.

CORREGIDO (gracias PabloN)


	En línea

iBágoas polas Fragas do Eume.!

jaromarm

Nuevo

Karma: +0/-0

Desconectado

Sexo: Masculino

El Salvador

Mensajes: 14

Re: Suma de números combinatorios

« Respuesta #6 : 18/03/2012, 12:21:40 pm »

Ohhh! por Dios me has salvado la vida (casi literalmente), GRACIAS a todos por la dedicación y el tiempo, especialmente a el_manco, que hace de este un gran foro.

Ahora me pongo a completar la demostración, espero no tener dificultad, Saludos.


	En línea

pabloN

Moderador Global
Pleno*

Karma: +0/-0

Desconectado

Sexo: Masculino

Uruguay

Mensajes: 2.280

Re: Suma de números combinatorios

« Respuesta #7 : 18/03/2012, 04:01:46 pm »

Bueno, con lo que te dijo el_manco ya está resuelto y una infinidad de casos similares :sonrisa_amplia:

.

De todas formas, creo que se puede demostrar por inducción. En el paso inductivo,

$\displaystyle\sum_{k=0}^{m+1}{(-1)^k \displaystyle\binom{m+1}{k} \cdot{} \displaystyle\binom{m+1+k}{k}}=\sum_{k=0}^{m} \left[{(-1)^k \displaystyle\binom{m+1}{k} \cdot{} \displaystyle\binom{m+1+k}{k}}\right]+(-1)^{m+1}\binom{2(m+1)}{m+1}$

Luego observar que $\displaystyle \sum_{k=0}^{m} \left[{(-1)^k \binom{m+1}{k} \cdot \binom{m+1+k}{k}}\right]=\sum_{k=0}^{m} \left[{(-1)^k \cdot \frac{m+1+k}{m+1-k}\cdot \binom{m}{k} \cdot \binom{m+k}{k}}\right]$ y hacer el siguiente artificio (para poder aplicar la hipótesis inductiva):

$\displaystyle \frac{m+1+k}{m+1-k}=\frac{m+1-k+2k}{m+1-k}=1+\frac{2k}{m+1-k}$

Aún haciendo las sustituciones correspondientes, no queda algo trivial. Hay que mostrar que:

$\displaystyle \sum_{k=0}^{m} \left[{(-1)^{m-k}\cdot \frac{2k}{m+1-k}\cdot \binom{m}{k} \cdot \binom{m+k}{k}}\right]=\binom{2(m+1)}{m+1}-2$

Pareciera incluso ser una identidad más complicada que la original. Sin embargo, yo que creo que si la sumatoria se escribe sumando a sumando, se halla denominador común (van aparecer productorias en los sumandos) y se simplifica de forma ingeniosa, puede llegarse a lo que está a la derecha, aunque resulta muy engorroso. Yo desistí, aunque es cierto que soy muy torpe para hacer esas manipulaciones algebraicas. Capaz que alguien más hábil lo logra.

Saludos


	En línea

I have a dream that one day no message of "Connection Problems" will appear. I still have a dream... :risa:

pabloN

Moderador Global
Pleno*

Karma: +0/-0

Desconectado

Sexo: Masculino

Uruguay

Mensajes: 2.280

Re: Suma de números combinatorios

« Respuesta #8 : 07/10/2012, 09:13:31 pm »

Cita de: el_manco en 18/03/2012, 11:18:22 am

Hola

El resultado es un caso particular de este otro más general:

$\displaystyle\sum_{k=0}^m{}(-1)^{m-k}\displaystyle\binom{m}{k}p(k)=m!a_m$ (1)

donde $p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$ es un polinomio de grado menor o igual que

¿Cuándo se probó este teorema?

Editado: Aprovecho para señalar una errata. El polinomio debe ser $p(x)=a_mx^m+a_{m-1}x^{m-1}+\ldots+a_1x+a_0$ , ¿no?


	En línea

I have a dream that one day no message of "Connection Problems" will appear. I still have a dream... :risa:

el_manco

Administrador
Pleno*

Karma: +0/-0

Desconectado

España

España

Mensajes: 25.228

Re: Suma de números combinatorios

« Respuesta #9 : 08/10/2012, 05:43:47 am »

Hola

Cita de: pabloN en 07/10/2012, 09:13:31 pm

¿Cuándo se probó este teorema?

Sinceramente, no lo sé.

Cita

Editado: Aprovecho para señalar una errata. El polinomio debe ser $p(x)=a_mx^m+a_{m-1}x^{m-1}+\ldots+a_1x+a_0$ , ¿no?

¡Gracias! Tienes razón. Ya lo corrgegí.

Saludos.


	En línea

iBágoas polas Fragas do Eume.!

pabloN

Moderador Global
Pleno*

Karma: +0/-0

Desconectado

Sexo: Masculino

Uruguay

Mensajes: 2.280

Re: Suma de números combinatorios

« Respuesta #10 : 08/10/2012, 09:11:28 am »

Cita de: el_manco en 08/10/2012, 05:43:47 am

Cita de: pabloN en 07/10/2012, 09:13:31 pm

¿Cuándo se probó este teorema?

Sinceramente, no lo sé.

Ok. Lo preguntaba a propósito de este hilo. Allí se pide probar que para todo $n\geq 0$ y para todo $r\in \mathbb{R}$ :

$\displaystyle\sum_{i=0}^n(-1)^{i}\binom{n}{i}(r-i)^n = n!$

Pero eso no es más que un corolario de este teorema:

Cita de: el_manco en 18/03/2012, 11:18:22 am

El resultado es un caso particular de este otro más general:

$\displaystyle\sum_{k=0}^n{}(-1)^{n-k}\displaystyle\binom{n}{k}p(k)=n!a_n$ (1)

donde $p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x_1+a_0$ es un polinomio de grado menor o igual que

Simplemente se toma:

$p(x)=(r-x)^n=(-1)^nx^n+(-1)^{n-1}nrx^{n-1}+(-1)^{n-2}\binom{n}{2}r^2x^{n-2}+\dots+\binom{n}{n-2}r^{n-2}x^2-nr^{n-1}x+r^n$

Aplicando la fórmula quedaría:

$\displaystyle\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}p(i) = \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}(r-i)^n = n!(-1)^n$

Dividiendo entre

:

$\displaystyle\sum_{i=0}^n(-1)^{-i}\binom{n}{i}(r-i)^n = n!$

Y como $(-1)^{-i}=(-1)^i$ , ya queda probado. O sea, que el resultado que tú has escrito aquí es mucho más general que esa simple identidad algebraica. Leí que su interés "práctico" radica en que a partir de ella se puede demostrar el teorema de Wilson sin necesidad de recurrir al teorema de Lagrange ni a la estructura de grupo de

. Aparentemente eso lo hizo por primera vez el matemático español Sebastián Martín Ruiz (que intervino en el hilo que menciono).

Saludos


	En línea

I have a dream that one day no message of "Connection Problems" will appear. I still have a dream... :risa:

Páginas: [1] Ir Arriba

Imprimir

Foros de matemática > Matemática > Matemática Aplicada > Combinatoria > Tema: Suma de números combinatorios

« anterior próximo »

	Autor	Tema: Suma de números combinatorios (Leído 895 veces)
0 Usuarios y 1 Visitante están viendo este tema.