Archivo de la etiqueta: combinatoria

Seminario de Resolución de Problemas: Coeficientes binomiales

Introducción

Los coeficientes binomiales aparecen en muchos problemas de matemáticas, y por ello es útil conocerlos bien y saber sus propiedades básicas. En esta entrada hablaremos de varios aspectos de los coeficientes binomiales: algebraicos, combinatorios y de teoría de números. Aunque resolvamos un problema con una técnica en particular, te recomendamos intentar usar las distintas herramientas en otros problemas, para conocer sus alcances y limitaciones.

Antes de empezar, ponemos una figura con un hecho curioso acerca de los coeficientes binomiales:

Coeficientes binomiales, Pascal y Fibonacci
“Las sumas de las diagonales del triángulo de Pascal dan los números de Fibonacci”

Definición algebraica de coeficientes binomiales

Como recordatorio, para n\geq 0 un entero, definimos n! recursivamente como 0!=1 y n!=n(n-1)!. En otras palabras, para n\geq 1 tenemos

    \[n!=1\cdot 2\cdot \ldots \cdot n.\]

Definimos para n\geq 0 un entero y k un entero en \{0,\ldots,n\}al coeficiente binomial n en k como

    \[\binom{n}{k}:=\frac{n!}{k!(n-k)!}.\]

Si n es un entero negativo o k es un entero fuera del rango \{0,\ldots,n\} es conveniente definir \binom{n}{k}=0.

A partir de la definición, es claro que \binom{n}{n}=\binom{n}{0}=1 para todo entero positivo n. Lo que no es inmediato a partir de la definición es que \binom{n}{k} siempre sea un entero. Veremos eso en la siguiente sección.

Mientras tanto, veamos algunas propiedades de los coeficientes binomiales que se pueden verificar sin mostrar que \binom{n}{k} es entero.

Propiedad (simetría). \binom{n}{k}=\binom{n}{n-k}.

Propiedad (fórmula de Pascal). \binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}.

Propiedad (propiedad de entrada-salida). \binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}.

El siguiente problema se puede resolver usando estas identidades.

Propiedad (suma cambiando arriba). Muestra que para n y k enteros positivos se tiene que

    \[\sum_{j=0}^k \binom{n+j}{n} = \binom{n+k+1}{n+1}.\]

Sugerencia pre-solución. Primero, formula un problema equivalente usando la propiedad de simetría. Luego, procede por inducción y usa otra de las propiedades de coeficientes binomiales mencionada arriba.

Solución. Usando la propiedad de simetría de coeficientes binomiales, el problema es equivalente a demostrar que

    \[\sum_{j=0}^k \binom{n+j}{j} = \binom{n+k+1}{k}.\]

Fijemos un entero n\geq 0 y hagamos inducción sobre k. Para k=0, la identidad es cierta pues

    \[\binom{n}{0}=1=\binom{n+1}{0}.\]

Para k=1, tenemos que mostrar que \binom{n}{0}+\binom{n+1}{1}=\binom{n+2}{1}. El primer término se puede escribir como \binom{n+1}{0}, pues ambos son 1. Así, lo que hay que mostrar es

    \[\binom{n+1}{0}+\binom{n+1}{1}=\binom{n+2}{1},\]

que es cierto por la fórmula de Pascal.

Suponiendo el resultado cierto para una k dada, mostraremos que es cierto para k+1. Esto se sigue de la siguiente cadena de igualdades, en donde en la segunda igualdad usamos la hipótesis inductiva, y en la tercera la fórmula de Pascal:

    \begin{align*}\sum_{j=0}^{k+1} \binom{n+j}{j} &= \sum_{j=0}^{k} \binom{n+j}{j}+\binom{n+k+1}{k+1}\\&=\binom{n+k+1}{k}+\binom{n+k+1}{k+1}\\&=\binom{n+k+2}{k+1}.\end{align*}

Esto termina la inducción.

\square

Existen otras formas de demostrar identidades con coeficientes binomiales, y de hecho una misma identidad se puede mostrar de varias formas. Veamos más técnicas.

Aspectos combinatorios de los coeficientes binomiales

El coeficiente binomial \binom{n}{k} cuenta la cantidad de subconjuntos de tamaño k de un conjunto de tamaño n. Argumentar esto es relativamente fácil, usando un argumento de doble conteo. Supongamos que dicha cantidad de subconjuntos es igual a A.

Respondamos la pregunta, ¿cuántos vectores de k entradas existen, tales que las entradas son distintas y vienen de un conjunto de n elementos? La pregunta es un poco distinta, pues como tenemos vectores, aquí sí importa el orden de los elementos. Supongamos que la respuesta es B.

Una forma de responder la pregunta es la siguiente. Primero, elegimos cuál subconjunto de tamaño k conformará las entradas. Esto se puede hacer de A formas (que aunque no sepamos cuánto vale, lo podemos usar). Luego, hay que ordenar las k entradas elegidas, que se puede hacer de k! maneras. Así, esto muestra que B=k! A.

Otra forma de responder la pregunta es la siguiente. Elegimos el primer elemento, que se puede hacer de n formas. Luego el segundo, de entre los n-1 restantes, que se puede hacer de n-1 formas. Siguiendo de esta manera, el último de los k hay que elegirlo entre n-k+1 restantes. Así, esta otra forma de contar dice que

    \[B=n\cdot(n-1)\cdot\ldots\cdot (n-k+1)=\frac{n!}{(n-k)!}.\]

Como ambas formas de contar son válidas, tenemos que k!A=B=\frac{n!}{(n-k)!}, de donde A=\frac{n!}{k!(n-k)!}=\binom{n}{k}.

Hay problemas que de lejos parecen preguntar algo de álgebra, pero que pueden ser interpretados en términos combinatorios para dar una solución.

Problema. Para n un entero positivo, muestra que

    \[\sum_{k=1}^n k \binom{n}{k} = n 2^{n-1}.\]

Sugerencia pre-solución. Construye un problema de conteo cuya respuesta se pueda poner tanto en términos del lado izquierdo, como en términos del lado derecho.

Solución. Preguntémonos, ¿de cuántas formas se puede elegir un subconjunto de un conjunto de n elementos en el que uno de sus elementos está pintado de azul?

Por un lado, primero se puede elegir qué elemento va a ser el azul. Hay n formas de hacer esta elección, y ésta forza a que el elemento en azul esté en el subconjunto. Luego, de los n-1 elementos restantes hay que elegir un subconjunto para completar la elección, lo cual se puede hacer de 2^{n-1} formas posibles. Así, una forma de contar da n2^{n-1}.

Por otro lado, primero se puede decidir de qué tamaño k va a ser el subconjunto. Como hay un elemento especial, el tamaño k va de 1 a n. Ya elegido k, hay \binom{n}{k} formas de elegir cuál será el subconjunto. Ya elegido el subconjunto, hay k formas de elegir cuál será el elemento pintado de azul. Así, otra posible respuesta, también correcta, es \sum_{k=1}^n k \binom {n}{k}.

Como estamos contando lo mismo con ambas expresiones, concluimos la igualdad del problema.

\square

A este método de resolver problemas se le conoce como contar de dos formas distintas y funciona no sólo con coeficientes binomiales, sino también con cualquier otra expresión algebraica que tenga términos que se puedan interpretar de manera combinatoria. Hay otro ejemplo en el blog, en donde vemos cómo aparecen los números de Fibonacci en el triángulo de Pascal. En esa entrada también hablamos de cómo aparecen los coeficientes binomiales en el triángulo de Pascal.

Coeficientes binomiales y binomio de Newton

La interpretación combinatoria de los coeficientes binomiales nos da una demostración para la fórmula del binomio de Newton, que ya vimos en una entrada anterior. Aquí enunciamos la fómula como recordatorio.

Teorema (binomio de Newton). Para a y b números reales y n un entero no negativo, se tiene que

    \begin{align*}(a+b)^n=\sum_{j=0}^n \binom{n}{j}a^{n-j}b^j.\end{align*}

Si en el binomio de Newton ponemos a=b=1, obtenemos

    \[\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=(1+1)^n=2^n.\]

Otra forma de probar esta identidad es simplemente notar que tanto la suma de la izquierda como el término de la derecha cuentan la cantidad de subconjuntos de un conjunto de n elementos: la de la izquierda los cuenta por tamaño, y el de la derecha decidiendo para cada elemento si está o no.

Si ponemos a=1, b=-1, obtenemos que

    \[\binom{n}{0}-\binom{n}{1}+\ldots+(-1)^n\binom{n}{n} = 0,\]

o bien

    \[\binom{n}{0}+\binom{n}{2}+\ldots = \binom{n}{1}+\binom{n}{3}+\ldots.\]

Se obtienen otras identidades de coeficientes binomiales interesantes si se usan raíces n-ésimas de la unidad, como ya vimos en la entrada de aritmética compleja.

Hay otras formas de usar el binomio de Newton para probar identidades de coeficientes binomiales.

Problema. Muestra que

    \[\binom{n}{0}^2+\binom{n}{1}^2+\ldots+\binom{n}{n}^2=\binom{2n}{n}.\]

Sugerencia pre-solución. Considera el polinomio (1+x)^{2n}.

Solución. Consideremos el polinomio (1+x)^{2n} y determinemos el coeficiente de su término x^n.

Usando el binomio de Newton directamente, tenemos que

    \[(1+x)^{2n}=\sum_{j=0}^{2n} \binom{2n}{j}x^j,\]

de modo que el coeficiente de x^n es \binom{2n}{n}.

Por otro lado, podemos escribir (1+x)^{2n}=(1+x)^n(1+x)^n. Usando el binomio de Newton, tenemos

    \[(1+x)^n=\sum_{j=0}^n \binom{n}{j} x^j.\]

Al multiplicar esta expresión consigo misma, los términos que quedan de grado n son cuando, para cada j, elegimos en un paréntesis al término que tiene x^j (que tiene coeficiente \binom{n}{j}) y en el otro al que tiene a x^{n-j} (que tiene coeficiente \binom{n}{n-j}).

De esta forma, el coeficiente del término de grado n es

    \[\sum_{j=0}^n \binom{n}{j} \binom{n}{n-j}.\]

Usando la identidad de simetría, podemos cambiar \binom{n}{n-j} por \binom{n}{j}, para obtener

    \[\sum_{j=0}^n \binom{n}{j}^2.\]

Igualando ambas formas de encontrar el coeficiente, obtenemos la identidad deseada.

\square

Hay otras técnicas que usan herramientas de integrales o derivadas. Vimos un ejemplo de esto en una entrada anterior.

Coeficientes binomiales y teoría de números

El hecho de que los coeficientes binomiales son la respuesta a un problema de conteo, implica que son enteros no negativos. Alternativamente, esto se puede demostrar por inducción usando la identidad de Pascal.

Este hecho nos puede ayudar a resolver problemas de teoría de números. Veamos un ejemplo clásico.

Problema. Muestra que el producto de n enteros consecutivos siempre es divisible entre n!.

Sugerencia pre-solución. Haz una división en casos para ver si se incluye al cero, si son sólo negativos o sólo positivos. Reduce el caso de negativos a positivos y usa notación adecuada para escribir al producto de dichos enteros usando un coeficiente binomial.

Solución. Si alguno de los enteros es 0, entonces el producto es 0, que es divisible entre cualquier número. Si son n enteros negativos, entonces podemos cambiar el signo a todos y su producto diferirá, quizás, en un factor -1 que no afecta la divisibilidad, y habremos obtenido un problema con n enteros positivos consecutivos. De esta manera, podemos enfocarnos en el caso de n enteros positivos consecutivos.

Llamemos al primero k+1, para k\geq 0. Los demás son entonces k+2,\ldots,k+n. Su producto es

    \begin{align*}(k+1)(k+2)\ldots(k+n)&=\frac{k!}{k!}(k+1)(k+2)\ldots(k+n)\\&=\frac{(n+k)!}{k!}\\&=n!\binom{n+k}{k}.\end{align*}

Como \binom{n+k}{k} es un entero, tenemos que el lado derecho es un múltiplo de n!, como queríamos.

\square

Otro tipo de técnicas hablan de la divisibilidad de un coeficiente binomial. Por ejemplo si tenemos un primo p, sabemos que todos los siguiente coeficientes binomiales son enteros

    \[\binom{p}{1}, \binom{p}{2},\ldots,\binom{p}{p}.\]

Por su expresión en términos de factoriales, todos tienen a p en el numerador, pero no tienen ningún divisor de p distinto de 1 en el denominador, pues p es primo. Así, todos ellos son enteros divisibles entre p. Eso puede ayudar en problemas como el siguiente.

Problema. Muestra que si p es un número primo, entonces p^2 divide a \binom{2p}{p} -2.

Sugerencia pre-solución. Formula un problema equivalente usando un resultado anterior.

Solución. Por un problema anterior,

    \[\binom{2p}{p}=\binom{p}{0}^2+\binom{p}{1}^2+\ldots+\binom{p}{p}^2.\]

Por la discusión previa, para j=1,\ldots,p-1 tenemos que p\mid \binom{p}{j}, así que p^2\mid \binom{p}{j}^2. De esta forma, trabajando módulo 2p tenemos

    \begin{align*}\binom{2p}{p}&\equiv \binom{p}{0}^2+\binom{p}{p}^2 \\&\equiv 1+1\equiv 2 \pmod{p^2}.\end{align*}

Esto es justo lo que queríamos mostrar.

\square

Más problemas

Puedes encontrar más problemas de coeficientes binomiales en la sección 5.1 del libro Problem Solving through Problems de Loren Larson.

Seminario de Resolución de Problemas: Identidades algebraicas y binomio de Newton

Introducción a entradas de álgebra

Cuando en matemáticas hablamos de álgebra, se abarca una gran cantidad de ideas, que van desde el álgebra de secundaria, en la cual factorizamos, despejamos y usamos identidades algebraicas, hasta el álgebra abstracta, que estudia estructuras algebraicas más generales como grupos, anillos y campos. Todas estas ideas tienen amplias aplicaciones en la resolución de problemas. En esta entrada, y las que vendrán a continuación, veremos numerosos ejemplos de esto

Para empezar, hablaremos de álgebra en el sentido de secundaria y preparatoria. Veremos que estas ideas, aunque sencillas, son muy versátiles. Después hablaremos de polinomios y de dos resultados fundamentales en su teoría: el teorema de factorización única y el teorema de la identidad. Los polinomios abundan en las matemáticas, y un correcto entendimiento de ellos abre muchas puertas en la resolución de problemas. En una entrada final daremos algunas ideas de otras estructuras algebraicas como grupos, anillos y campos.

Más adelante en el curso hablaremos con detalle de otros dos temas relacionados con álgebra: desigualdades y álgebra lineal.

Como lo hemos hecho hasta ahora, la idea no es profundizar demasiado en el desarrollo de la teoría algebraica. Para eso, es más recomendable llevar buenos cursos de distintos tipos de álgebra a nivel superior. Aquí en el blog hay material de los cursos Álgebra Superior II y Álgebra Lineal I que imparto en la Facultad de Ciencias de la UNAM.

Identidades algebraicas

Comenzaremos hablando de identidades algebraicas. Una identidad algebraica es una igualdad que se satisface para ciertas variables, independientemente del valor que tomen. Algunos ejemplos son las igualdades que se aprenden a nivel secundaria y bachillerato:

    \begin{gather*}a^2-b^2=(a-b)(a+b),\\a^2+2ab+b^2=(a+b)^2,\\a^2+b^2+c^2+2ab+2bc+2ca=(a+b+c)^2,\\a^n-b^n = (a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1}).\end{gather*}

Varias de las identidades algebraicas nos permiten desarrollar o factorizar una expresión. Factorizarla es bastante útil en problemas de teoría de números, en donde es importante conocer qué números dividen a la expresión. Desarrollarla a veces nos permite trabajar con una suma de términos simétricos, que podemos estudiar con técnicas de polinomios o con desigualdades.

Veamos algunos ejemplos.

Problema. Muestra que si n es un entero, entonces n^4-20n^2+4 no es un número primo.

Sugerencia pre-solución. Intenta formular un problema equivalente al factorizar la expresión. Hay más de un camino por el que puedes proceder para factorizar, pero no todos te llevan a una solución. Intenta completar cuadrados de distintas formas y ve si encuentras un patrón.

Solución. Reescribimos la expresión como sigue:

    \begin{align*}n^4-20n^2+4&=n^4-4n^2+4-16n^2\\&=(n^2-2)^2-(4n)^2\\&=(n^2-4n-2)(n^2+4n-2).\end{align*}

Para ver que la expresión no es un primo, basta con ver que ninguno de estos factores puede ser igual a 1 o -1. Si n^2-4n-2=1 o n^2+4n-2=1, entonces n^2=\pm 4n+3. Trabajando módulo 4, tendríamos n^2\equiv 3 \pmod{4}, lo cual es imposible.

Si n^2-4n-2=-1 o n^2+4n-2=-1, entonces sumando 6 de ambos lados tenemos

    \[(n\pm 2)^2=n^2\pm 4n+4=5.\]

Esto es imposible pues 5 no es el cuadrado de un entero. Así, n^4-20n^2+4 se puede factorizar en factores distintos de 1 y -1 y por lo tanto no es primo.

\square

El siguiente problema fue parte de la 1a Olimpiada Mexicana de Teoría de Números. Veremos dos soluciones. Ambas usan ideas algebraicas, pero son distintas entre sí.

Problema. Sean a,b,c,d enteros tales que

    \begin{align*}ab + bc + ca &= 1\\ ad + dc + ca &= 1\\ ab + bd + da &= 1.\end{align*}

Determina todos los valores posibles que puede tomar bc+cd+db.

Sugerencia pre-solución 1. Hay varias formas de aprovechar la simetría del problema. Intenta manipular las ecuaciones para obtener información y recuerda que es importante usar que a, b, c son enteros.

Solución 1. A partir de la primera y segunda ecuación, tenemos que

    \[ab+bc+ca=ad+dc+ca,\]

de donde 0=ad+dc-ab-bc=(a+c)(d-b). De aquí tenemos dos opciones: a=-c o b=d. Si a=-c, de la segunda ecuación obtenemos

    \[1=ad+dc+ca=-c^2,\]

lo cual es imposible. Así, concluimos que b=d.

Por simetría, concluimos que c=b, así que b=c=d. Tras esto, las tres ecuaciones se reducen a una sola

    \[1=2ab+b^2=b(2a+b).\]

Las únicas factorizaciones de 1 en enteros son 1=1\cdot 1 o 1=(-1)(-1), de modo que b=2a+b, de donde a=0 y b=\pm 1. De cualquier forma, la expresión que buscamos es bc+cd+db=3b^2=3.

\square

Sugerencia pre-solución 2. Formula un problema equivalente sumando a^2 en ambos lados en cada una de las ecuaciones.

Solución 2. Sumando a^2 en ambos lados de la primer ecuación obtenemos

    \[a^2+1=a^2+ab+bc+ca=(a+b)(a+c).\]

Las otras dos ecuaciones dan expresiones simétricas. Multiplicando las tres, tenemos

    \[(a^2+1)(a^2+1)^2=(a+b)^2(b+c)^2(c+a)^2.\]

El lado derecho es el cuadrado de un entero, así que el izquierdo también debe serlo, de modo que a^2+1 debe ser el cuadrado de un entero. Pero los únicos cuadrados a distancia 1 son 0 y 1, de donde a^2+1=1, y así a=0. Las ecuaciones se convierten entonces en bc=dc=bd=1, de donde la suma de las tres es 3.

\square

Demostraciones del binomio de Newton

La siguiente es una de las identidades algebraicas más importantes.

Teorema (binomio de Newton). Para a y b números reales y n un entero no negativo, se tiene que

    \begin{align*}(a+b)^n=\sum_{j=0}^n \binom{n}{j}a^{n-j}b^j\end{align*}

El término de la derecha es

    \[a^n+\binom{n}{1}a^{n-1}b+\ldots+\binom{n}{n-1}ab^{n-1} + b^n.\]

Veamos algunas demostraciones del teorema de binomio de Newton, que usan ideas un poco distintas. La primera usa ideas combinatorias. La segunda, ideas más algebraicas. La tercera es menos general, pero usa ideas geométricas.

Demostración combinatoria

Demostración 1. Pensemos al lado izquierdo como el producto

    \[(a+b)(a+b)\ldots(a+b)(a+b).\]

¿Cómo se obtienen factores al desarrollar esta expresión? En cada uno de los n paréntesis hay que elegir o un a, o un b. Así, cada sumando es producto de n letras.

Si elegimos j veces b, entonces elegimos n-j veces a. ¿De cuántas formas podemos elegir j veces b? Tantas como subconjuntos de tamaño j de un conjunto de n elementos, es decir, \binom{n}{j}.Así, el término a^{n-j}b^j aparece \binom{n}{j} veces.

Para terminar, notemos que j puede ir desde 0 (no elegir ningún b), hasta n (no elegir ningún a).

\square

La demostración anterior es combinatoria, pues está usando argumentos de conteo. Está contando de dos formas distintas los términos que aparecen en el producto desarrollado. Además, está usando la interpretación combinatoria de los coeficientes binomiales.

Demostración algebraica

Demostración 2. Si b=0, entonces en ambos lados tenemos a^n, ya que el único sumando en el que no aparece b es el primero. Tenemos algo análogo si a=0. De otra forma, podemos asumir que a y b no son cero y dividir ambos lados de la igualdad que queremos entre b^n. Definiendo x=a/b, tenemos que mostrar que:

    \[(x+1)^n= \sum_{j=0}^n \binom{n}{j}x^{n-j}.\]

Esta igualdad es claramente cierta para n=0, pues en ambos lados obtenemos 1, y para n=1, pues en ambos lados obtenemos x+1. Procediendo por inducción (explicamos cada paso con un poco de detalles más abajo):

    \begin{align*}(x+1)^{n+1}&=(x+1)(x+1)^n\\& = (x+1)\sum_{j=0}^n \binom{n}{j} x^{n-j}\\&=\sum_{j=0}^n \binom{n}{j} x^{n-j+1}+\sum_{j=0}^n \binom{n}{j}x^{n-j}\\&  = \sum_{j=0}^{n+1} \binom{n}{j-1} x^{n-j}+\sum_{j=0}^{n+1} \binom{n}{j}x^{n-j}\\&=\sum_{j=0}^{n+1}\left(\binom{n}{j-1}+\binom{n}{j}\right) x^{n-j}\\&=\sum_{j=0}^{n+1}\binom{n+1}{j} x^{n-j}.\end{align}

El primer paso es claro. En el segundo usamos hipótesis inductiva. Luego, hacemos la multiplicación por x+1. El siguiente paso puede ser un poco confuso, pues parece que “agregamos términos”, pero en la segunda suma sólo agregamos \binom{n}{n+1}x^{-1}=0. En la primer suma hicimos un shift o desfase: los términos que estaban antes para j de 0 a n, ahora están para j de 1 a n+1. Además, agregamos el término \binom{n}{-1}x^{n}=0. En el siguiente paso usamos la identidad de Pascal:

    \[\binom{n}{j-1}+\binom{n}{j}=\binom{n+1}{j},\]

que se puede demostrar combinatoriamente, o directamente de manera algebraica a partir de la fórmula para coeficientes binomiales.

Con esto termina la demostración por inducción.

\square

Esta segunda demostración es mucho más algebraica, es decir, usa ideas de cómo se manipulan las expresiones con variables. El primer paso, en el que reducimos el problema a cuando un término es 1, se llama homogenización. En realidad no era estrictamente necesario hacerlo, pero simplifica la notación. En las sumas hicimos un shift, que es otra técnica que se usa al estudiar sumas y series.

Demostración geométrica

Daremos una última demostración del teorema del binomio de Newton, pero sólo para el caso n=2. Lo que tenemos que demostrar es simplemente la identidad

    \[(a+b)^2=a^2+2ab+b^2.\]

Para este caso, hay una bonita “demostración sin palabras”:

Binomio al cuadrado mostrado geométricamente
Demostración visual del binomio al cuadrado

Esta demostración es geométrica, pues estamos interpretando a la igualdad como una igualdad de áreas. Estamos usando una fórmula de área para cuadrados y rectángulos. Además, estamos usando que el área de una figura es aditiva, es decir, que es igual a la suma de áreas de figuras en las que queda subdividida.

Puedes elegir tu demostración favorita del binomio de Newton. Sin embargo, en resolución de problemas es importante saber proceder con varios acercamientos. Hay problemas en los que el acercamiento combinatorio, el algebraico o el geométrico es ventajoso, y por ello es mejor tener buena práctica en todos ellos.

Una aplicación del binomio de Newton en teoría de números

En entradas anteriores ya hemos usado el teorema del binomio de Newton en repetidas ocasiones, por ejemplo, en la entrada de aritmética de números complejos. Veamos un ejemplo más.

Problema. Sean a y b enteros primos relativos. Muestra que para todo entero positivo n, se tiene que a^n y b^n son primos relativos.

Sugerencia pre-problema. Hay varias formas de dar una solución de esto. Una es analizando a los enteros primo por primo. Sin embargo, existe una solución usando binomio de Newton y la caracterización en términos de combinaciones lineales enteras para primos relativos.

Solución. Como a y b son primos relativos, existe una combinación lineal entera de ellos que da 1, digamos

    \[ax+by=1.\]

Elevando esta igualdad a la 2n-1 tenemos

    \[1=1^{2n-1}=(ax+by)^{2n-1}.\]

Abriendo el último término con binomio de Newton queda

    \[\sum_{j=0}^{n-1} \binom{2n-1}{j} a^{2n-1-j}b^j +  \sum_{j=n}^{2n-1}  \binom{2n-1}{j} a^{2n-1-j}b^j,\]

y factorizando a^n del primer sumando y b^n del segundo,

    \[a^n \sum_{j=0}^{n-1} \binom{2n-1}{j} a^{n-1-j}b^j + b^n  \sum_{j=n}^{2n-1}  \binom{2n-1}{j} a^{2n-1-j}b^{j-n}.\]

Lo que queda a la derecha es una combinación lineal entera de a^n y b^n igual a 1, y por lo tanto son primos relativos.

\square

Más problemas

En la siguiente entrada hablaremos de la identidad de Gauss para suma de cuadrados y de la identidad para x^3+y^3+z^3-3xyz, las cuales se usan frecuentemente en resolución de problemas. Además, puedes encontrar más problemas de identidades algebraicas en la Sección 4.1 del libro Problem Solving through Problems de Loren Larson.

Fuente

Playa del Carmen antes de LAGOS

PlayaHace una semana salí de la terminal de ADO, llegando a Playa del Carmen. La ciudad está fantástica. Desde que sales de la terminal puedes ver que es una ciudad totalmente turística, incluso en temporada baja. Por las calles se ven caminar “tourists” hablando inglés, francés, alemán y quien sabe que otros idiomas.

Llegué y el calor me pegó de lleno. Comencé a caminar un rato, maleta y mochila en mano. ¡Sí que es cansado hacer eso bajo ese sol! Tenía que conseguir un hotel u hostal pronto para poder pasear más libremente. Pero dije: “Ah, bueno, me doy una vuelta inicial y ya luego lo busco”.

Seguir leyendo…

El principio de divide y conquista en conteo

CombinatoriaMuchas veces es mejor dividir un problema grande en problemas pequeños. A esto se le conoce como el principio de Divide y conquista. En esta serie de videos veremos en qué consiste aplicándolo al conteo. Después recapitularemos lo que vimos.

Ir a los videos…

Contando combinaciones

CombinatoriaLas combinaciones nos permiten contar de cuántas formas podemos elegir algunos objetos de un cierto conjunto de objetos. Comenzamos por una introducción al principio de doble conteo, luego vemos un par de problemas, introducimos la noción de coeficiente binomial y finalmente encontramos una fórmula en términos de factoriales.

Ir a los videos…