Una pequeña suma

Una disculpa por no haber escrito en los días pasados, pero fueron vacaciones y había que ponerse al corriente con las amistades y las clases, pero ya estamos de regreso.

Muchos ya deben conocer la famosa fórmula por Gauss que mencionan desde secundaria, que nos dice que:

\displaystyle 1+2+3+\mathop{...}+n=\frac{n\mathop{.}(n+1)}{2}

y la mayoría debe de haber escuchado la demostración en que copiamos esta suma, la escribimos al revés, sumamos por pares y formamos términos repetidos para luego simplificar.

Este método es muy bonito, pero en ocasiones queremos fórmulas para {1^2+2^2+\mathop{...}} o para {1^3+2^3+\mathop{...}} y en esas situaciones, nuestra idea mágica ya no funciona bien. Para estas expresiones pudieramos utilizar inducción matemática, pero sería necesario tener conocimiento a priori de la forma que tendrá la expresión, por lo que este método no nos da una expresión, sólamente permite comprobar que alguna funciona y, si bien uno puede ser bueno identificanto patrones numéricos, sería agradable tener un método más seguro y así poder tener una expresión cerrada para estas sumas o en general:

\displaystyle \sum_{i=1}^{n} i^k

Como en varias ocasiones me han pedido algunas personas que les diga una manera de obtener estas fórmulas, decidí hacer esta publicación, y el acercamiento que tendré, aprovechando la publicación anterior, es mediante técnicas de conteo. Para ello empezaremos viendo el concepto de combinaciones repetidas.

Pensemos que hay {4} tipos de pasteles en una pastelería: zanahoria, tortuga, tres leches y alemán. Vamos a comprar {8} pasteles para una fiesta y nos gustaría saber de cuántas maneras podemos hacer un pedido de pasteles para los invitados encargando solamente de estos {4} tipos. Notamos que en este problema no importa que si compro un pastel alemán y luego otro o si los compro al revés, lo importante es que tendría {2} pasteles alemanes. Tampoco importa si compramos primero los de tres leches o los de zanahoria, sino que sólo importa el hecho de comprarlos y la cantidad que llevamos.

Para resolver este problema podríamos elegir un orden arbitrario, puesto que el orden no afectará a nuestro conteo. Primero pondremos los de zanahoria, luego los de tortuga, luego los de tres leches y al final los alemanes. Para no confundirlos entre ellos (vienen en cajitas), pondremos separadores entre dos tipos diferentes de pastel. Un posible arreglo para eso se vería así.

\displaystyle 00 \qquad 1 \qquad 00 \qquad 1 \qquad 00 \qquad 1 \qquad 00

Donde los {0} representan pasteles y los {1} representan separadores. En esta fila en particular tendríamos {2} pasteles de cada uno. Si tomaramos por ejemplo el arreglo {000 \quad 1 \quad 00 \quad 1 \quad 1 \quad 000}, llevariamos {3} de zanahoria, dos de tortuga, ninguno de tres leches y {3} pasteles alemanes. De la misma manera pudieramos hacer otros arreglos de ocho {0}‘s y tres {1}‘s y cada arreglo nos daría una eleccón de pasteles distinta. Los primeros {0}‘s nos dirían cuantos pasteles de zanahoria llear hasta el primer {1}, los siguientes {0}‘s nos dirían sobre cuantos pasteles de tortuga llevar y así sucesivamente. En caso de no haber ceros en un lugar específico, querría decir que no llevaremos de ese tipo de pastel.

Con lo anterior, nuestro problema de elección se reduce a formar una pequeña fila de ocho {0}‘s y tres {1}‘s. Podemos pensar que tenemos {8+3=11} espacios donde poner los unos y ceros. Elegiremos, de entre estos {11}, los lugares {3} sitios donde poner los unos, lo cual es simplemente una elección, un subconjunto, por lo que, según vimos la publicación anterior, simplemente se trata de una combinación:

\displaystyle \binom{11}{3}= \frac{11!}{3!\mathop{.}(11-3)!} = \frac{11!}{3!\mathop{.}8!}=\frac{11\mathop{.}10\mathop{.}9\mathop{.}8!}{3!\mathop{.}8!} =\frac{11\mathop{.}10\mathop{.}9}{3!} =11\mathop{.}5\mathop{.}3=165

Esto se ve sencillo, pero huele a ser muy generalizable, así que vamos directamente. Supongamos que tenemos {n} tipos diferentes de objetos, por ejemplo {n} tipos de piezas de legos o {n} tipos de panes, y vamos a elegir k objetos, entre los que puede haber varios del mismo tipo (incluso todos del mismo tipo). Para esto, procederemos de la misma manera: que arriba. Tomaremos {n-1} separadores en forma de unos y haremos una fila con los objetos, representados de nuevo por ceros, y los separadores. Los primeros ceros nos indican cuantos del primer tipo elegimos; los segundos ceros, después del primer separador, indican cuantos elegimos del segundo tipo y así sucesivamente.

Nuevamente nuestro problema se reduce a formar una fila, donde tenemos {n-1+k} espacios y vamos a poner {k} objetos (o bien {n-1} separadores), lo cual podemos hacer de {\binom{n+k-1}{k}} maneras. Con esto tendremos otra definición conveniente:

Sea {\bar{C}\binom{n}{k}} el número de maneras de elegir {k} objetos de entre {n} tipos diferentes.

A {\bar{C}\binom{n}{k}} se le llama combinaciones con repetición de {n} tipos en k, y por el desarrollo anterior, tenemos que:

\displaystyle \bar{C}\binom{n}{k} = \binom{n+k-1}{k} \ \ \ \ \ (1)

Notemos además que, este problema equivale a encontrar todos los grupos de números {k_1,k_2,\mathop{...}k_n}, tales que todos son enteros no-negativos y que cumplen con que:

\displaystyle k_1+k_2+\mathop{...}+k_n=k

Claramente estos {k_i} corresponderían a el número objetos del tipo {i} que habríamos elegido.

Ya con esto en mente podemos volver a las sumas en las que estamos interesados. Pensemos por un momento en todas las combinacion con repetición de {n+1} tipos en {k}, por la ecuación (1), tenemos que esto sería {\bar{C}\binom{n+1}{k} = \binom{n+k}{k}}. Ahora pensemos en ota manera de contabilizar estas combinaciones con repetición. Concentrémonos en el tipo {1} y pensemos en cuantas elecciones tiene exactamente {m} objetos del este tipo {1}.

Si elegimos {m} objetos del primer tipo, nos quedan {n} tipos y aún debemos elegir {k-m} objetos entre ellos, dandonos un total de {\bar{C}\binom{n}{k-m} = \binom{n+k-m-1}{k-m}} elecciones cuando tomamos {m} del primer tipo. Como podemos tomar ninguno del primero o uno del primer tipo o dos del primer tipo, etc. Sumamos el número de elecciones para cada posibilidad hasta el máximo, cuando elegimos los {k} objetos de la misma primer clase. Esto debería darnos el mismo número de elecciones que al inicio calculamos:

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

Y ahora, por conveniencia, sustituimos {n} por {n+1} y {k} por {k-1} en la ecuación (3) y utilizamos la simetría de los coeficientes binomiales:

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

Esto último se vería así una vez desarrollado:

\displaystyle \binom{n+k}{n+1} = \sum_{m=0}^{k-1}\binom{n+k-m-1}{n}= \binom{n+k-1}{n}+\mathop{...}+\binom{n+1}{n}+\binom{n}{n} \ \ \ \ \ (4)

Con esto podemos empezar la mágia. Debería ser claro que {\binom{r}{1}=r}. Con esto, sustituyamos cuando {n=1}:

\displaystyle \binom{k}{1}+\binom{k-1}{1}+\mathop{...}+\binom{2}{1}+\binom{1}{1}=\binom{1+k}{2} \ \ \ \ \ (5)

Pero notamos que el lado izquierdo corresponte a la suma de los primer {k} enteros y el lado derecho es una expresión que sólo depende de {k}:

\displaystyle 1+2+\mathop{...}+(k-1)+k=\frac{k(k+1)}{2} \ \ \ \ \ (6)

Ya con esto tenemos nuestra primera expresión de sumatoria de Gauss. Ahora volvemos a la ecuación (4), en la que ahora remplazamos {n=2}:

\displaystyle \binom{2+k}{3} = \binom{k+1}{2}+\binom{k}{2}+\mathop{...}+\binom{3}{2}+\binom{2}{2} \ \ \ \ \ (7)

Pero notamos que {\binom{r+1}{2}=\frac{(r+1)r}{2}=\frac{(r^2+r)}{2}=\frac{1}{2}(r^2+r)}, de donde la sumatoria anterior puede escribirse como:

\displaystyle \binom{2+k}{3} = \frac{1}{2}\left((k^2+k)+((k-1)^2+(k-1))+\mathop{...}+2^2+2+1^2+1\right)

\displaystyle \binom{2+k}{3} =\frac{1}{2}\left(\left(k^2+(k-1)^2+\mathop{...}+2^2+1^2\right)+\left( k+(k-1)+\mathop{...}+2+1\right) \right)

\displaystyle \binom{2+k}{3} =\frac{1}{2}\left(\left(k^2+(k-1)^2+\mathop{...}+2^2+1^2\right)+\left( \frac{k(k+1)}{2}\right) \right)

Para la última línea utilizamos la fórmula de Gauss que acabamos de obtener. Multiplicando ambos lados por 2 y haciendo algo de algebra obtenemos que:

\displaystyle 1^2+2^2+\mathop{...}+(k-1)^2+k^2 = \frac{(k+2)(k+1)k}{3}-\frac{k(k+1)}{2}=\frac{k(k+1)(2k+1)}{6} \ \ \ \ \ (8)

Finalmente, para nuestra última expresión que nos interesa, sustituimos {n=3} y sustituimos de nuevo {k-1} en vez de {k} en la ecuación (4) y vemos que {\binom{r+1}{3}=\frac{(r+1)(r-1)r}{6}=\frac{1}{6}(r^3-r)}:

\displaystyle \binom{k+2}{4} =\binom{k+1}{3}+\binom{k}{3}+\mathop{...}+\binom{4}{3}+\binom{3}{3}

\displaystyle \binom{k+2}{4} =\frac{1}{6}\left((k^3-k)+((k-1)^3-(k-1)))+\mathop{...}+(3^3-3)+(2^3-2)\right)

\displaystyle \binom{k+2}{4} =\frac{1}{6}\left((k^3-k)+((k-1)^3-(k-1)))+\mathop{...}+(3^3-3)+(2^3-2)+(1^3-1)\right)

\displaystyle \binom{k+2}{4} =\frac{1}{6}\left(\left(k^3+(k-1)^3+\mathop{...}+3^3+2^3+1^3\right)-\left(1+2+\mathop{...}+k\right)\right)

\displaystyle \binom{k+2}{4} =\frac{1}{6}\left(\left(k^3+(k-1)^3+\mathop{...}+3^3+2^3+1^3\right)-\binom{k+1}{2}\right)

De nuevo la última línea viene directamente de la primer formula de Gauss. Pasando terminos a un lado y simplificando:

\displaystyle 1^3+2^3+\mathop{...}+k^3=6\binom{k+2}{4}+\binom{k+1}{2}=\left( \frac{k(k+1)}{2} \right)^2 \ \ \ \ \ (9)

Con esto pudimos obtener las ecuaciones (6), (8) y (9). En general este método nos puede dar las otras expresiones que nos pudiera interesar, esto porque los coeficiente en la suma de (4), en realidad son polinomios. Al sustituir un determinado {n} lo que hacemos es elegir el grado del polinomio en {\binom{r}{n}=\frac{r(r-1)\mathop{...}(r-n+1)}{n!}}, que tendría un total de {n} términos en el numerador (grado {n}). Con esto podemos obtener la suma {\sum_{i=1}^{k} i^n}, pero claramente para ello tendríamos que conocer los valores de esta suma para todos los valores menores a {n}. Sin embargo, si bien el método es largo. Nos garantiza encontrar todas las expresiones que nos interesen.

¡Listo! Con esto queda lo que queríamos y termina publicación. En otra ocasión quizás comprarta las notas que hice para mi clase física moderna respecto a relatividad especial o suba la solución de algún problema de la IPhO pasada. Saludos y gracias.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s