Archivo de la etiqueta: inducción

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.

Seminario de Resolución de Problemas: Principio de Inducción, Parte 3

Introducción

En entradas anteriores ya hablamos acerca de la idea básica del principio de inducción y también vimos cómo la inducción puede interactuar con las heurísticas de trabajar hacia atrás y de generalización. En esta entrada hablaremos de dos formas adicionales y válidas en las que se puede hacer inducción.

Inducción fuerte

El principio de inducción funciona pues es un mecanismo que pasa por los números naturales “uno por uno”. Al momento en el que suponemos la hipótesis inductiva para cierto natural n, lo que queremos hacer para continuar es mostrar la afirmación para el natural n+1. Es decir, el natural n+1 es el primer natural para el que todavía no sabemos que la afirmación funciona. Dicho de otra forma, para todo natural m\leq n ya sabemos que la afirmación sí funciona.

Aunque típicamente usemos únicamente la afirmación para el paso n para demostrar la validez del paso n+1, en realidad podríamos usar toda la información que ya tenemos de que la inducción se vale para todo m entre la base inductiva y n. Esta es la idea detrás del principio de inducción fuerte.

Principio de inducción fuerte. Sea P(n) una afirmación (o proposición o propiedad) que depende del número natural n. Si

  • la afirmación P(a) es cierta y
  • la veracidad de la afirmación “P(m) es cierto para todo a\leq m \leq n” implica la veracidad de la afirmación P(n+1),

entonces la afirmación P(n) es cierta para toda n \geq a.

Veamos un ejemplo de teoría de gráficas. No entraremos en detalles de las definiciones. Aunque no conozcas mucho de teoría de gráficas, es posible que de cualquier forma las definiciones te hagan sentido.

Problema. Un árbol es una gráfica que no tiene ciclos y que es conexa. Demuestra que todo árbol de n vértices tiene n-1 aristas.

Solución. Lo vamos a demostrar por inducción sobre el número de vértices que tiene el árbol. Si el árbol tiene 1 vértice, entonces el resultado es cierto, pues tiene 0 aristas.

Tomemos ahora un entero n y supongamos que el resultado es cierto para cuando el número de vértices es cualquier entero entre 1 y n. Tomemos un árbol T de n+1 vértices.

Árbol con n+1 vértices.

Tomemos una arista cualquiera de T y quitémosla. Esto parte a T en dos árboles (¡demuéstralo!) con, digamos a y b vértices, de modo que a+b=n+1.

Después de quitar la arista

Tenemos 1\leq a < n y 1\leq b <n, así que cada uno de esos árboles tiene, por hipótesis inductiva, a-1 y b-1 aristas, respectivamente. Así, T tiene esas aristas, y la que quitamos, es decir, (a-1)+(b-1)+1=a+b-1=n aristas, como queríamos demostrar.

\square

Los que han estudiado teoría de gráficas quizás noten que pudimos haber evitado usar inducción fuerte si en vez de usar una arista arbitraria usábamos una que llegaba a un vértice hoja (de grado 1). Haciendo eso se puede usar inducción “normal”. La demostración anterior tiene la ventaja de no necesitar definir qué es una hoja.

Inducción de Cauchy

Hablemos ahora de otra variante. El principio de inducción es un mecanismo que nos permite probar una afirmación para los naturales “pasando por todos ellos” de una manera muy natural se prueba para el primero, luego para el siguiente, luego para el siguiente y así sucesivamente. Hay otras formas de cubrir a los números enteros.

Principio de inducción de Cauchy. Sea P(n) una afirmación (o proposición o propiedad) que depende del número natural n. Si

  • la afirmación P(1) es cierta,
  • la veracidad de la afirmación P(n) implica la veracidad de la afirmación P(2n) y
  • la veracidad de la afirmación P(n) para un n>a implica la veracidad de la afirmación P(n-1),

entonces la afirmación P(n) es cierta para toda n \geq 1.

Intuitivamente, lo que está pasando es que al probar P(1) y la segunda afirmación, estamos probando P(2), de ahí P(4), de ahí P(8) y en general P(n) para cuando n es potencia de 2. Luego, con P(4) y la tercera afirmación sale P(3). Con P(8) y la tercera afirmación sale P(7), P(6),P(5). Esto garantiza cubrir todos los naturales pues para cualquier natural n hay una potencia de dos 2^m mayor que él para la que sabemos que el resultado es cierto, y de ahí con la tercera afirmación “vamos bajando cubriendo todos los naturales”, incluido n.

Como ejemplo, presentamos una demostración de la desigualdad entre la media aritmética y la media geométrica,

Problema. Sea n un entero positivo y x_1,x_2,\ldots,x_n números reales positivos. Demuestra que

    \[\frac{x_1+x_2+\ldots+x_n}{n}\geq \sqrt[n]{x_1x_2\cdots x_n}.\]

Solución. Vamos a proceder por inducción de Cauchy sobre n. Sea P(n) la afirmación del problema.

En el caso n=1 tenemos sólo un real x_1 y tenemos que demostrar que \frac{x_1}{1}\geq \sqrt[1]{x_1}, lo cual es cierto pues en ambos lados tenemos x_1. Así, P(1) es cierta.

Para el resto de la demostración, será útil que probemos también por separado el caso para dos números, es decir, P(2). Pero esto es sencillo pues si tenemos reales positivos a y b, entonces \frac{a+b}{2}\geq \sqrt{ab} es equivalente a a-2\sqrt{ab}+b\geq 0, la cual es cierta pues el lado izquierdo es el número no negativo (\sqrt{a}-\sqrt{b})^2.

Ahora veremos que P(n) implica P(2n). Supongamos la veracidad de P(n) y tomemos 2n números reales x_1,x_2,\ldots,x_{2n}. Queremos demostrar que

    \[\frac{x_1+\ldots+x_{2n}}{2n}\geq \sqrt[2n]{x_1\cdots x_{2n}}.\]

Llamemos A al lado izquierdo y G al lado derecho.

Sea B la media aritmética de x_1,\ldots, x_n y C la de x_{n+1},\ldots, x_{2n}. Aplicando por separado P(n) a estos números, tenemos que

    \begin{align*}B:=\frac{x_1+\ldots+x_n}{n}&\geq \sqrt[n]{x_1\cdots x_n}\\C:=\frac{x_{n+1}+\ldots+x_{2n}}{n}&\geq \sqrt[n]{x_{n+1}\cdots x_{2n}}\\ \end{align*}



Notemos que A=\frac{B+C}{2}. Aplicando P(2) a los números B y C tenemos que

    \begin{align*}A&=\frac{B+C}{2}\\&\geq \sqrt[2]{BC} \\&\geq \sqrt[2]{\sqrt[n]{x_1\cdots x_n} \cdot \sqrt[n]{x_{n+1}\cdots x_{2n}}}\\& = G.\end{align*}



Es decir, P(2n) es cierta.

Para terminar con la inducción de Cauchy, el último paso es suponer la veracidad de P(n) para n>1 y con ella demostrar la veracidad de P(n-1). Supongamos entonces la veracidad de P(n) y tomemos n-1 números x_1,\ldots, x_{n-1}. Queremos usar la veracidad de P(n), así que tenemos que “inventarnos” otro número m para poder aplicar P(n). Tomemos m=\frac{x_1+\ldots+x_{n-1}}{n-1}, es decir, la media aritmética de los números de x_1 hasta x_{n-1}.

Observemos que

    \[\frac{x_1+\ldots+x_{n-1}+m}{n}=m.\]

Usando la veracidad de P(n) para los números x_1,\ldots, x_{n-1},m tenemos que

    \[m=\frac{x_1+\ldots+x_{n-1}+m}{n}\geq \sqrt[n]{x_1\cdots x_{n-1}m}.\]

Dividiendo entre \sqrt[n]{m}=m^{1/n} en ambos extremos de la cadena, obtenemos

    \[m^{\frac{n-1}{n}}\geq \sqrt[n]{x_1 \cdots x_{n-1}}.\]

Elevando ambos lados de esta desigualdad a la n/(n-1) obtenemos

    \[m\geq \sqrt[n-1]{x_1 \cdots x_{n-1}}.\]

Esto es exactamente lo que queríamos probar. Con esto se comprueba la veracidad de P(n-1) y así terminamos la inducción de Cauchy.

\square

La elección de m en la última parte de la demostración parece un poco sacada de la manga. En realidad, sí tiene una cierta motivación. En la hipótesis P(n) tenemos a la izquierda \frac{x_1+x_2+\ldots+x_n}{n}, pero lo que queremos es tener \frac{x_1+x_2+\ldots+x_{n-1}}{n-1}. Nuestra elección de x_n=m vino de igualar ambas expresiones y despejar x_n.

Más ejemplos

Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas:

Seminario de Resolución de Problemas: Principio de Inducción, Parte 2

En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:

Principio de inducción. Sea P(n) una afirmación (o proposición o propiedad) que depende del número natural n. Si

  • la afirmación P(a) es cierta y
  • la veracidad de la afirmación P(n) implica la veracidad de la afirmación P(n+1),

entonces la afirmación P(n) es cierta para toda n \geq a.

Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.

Inducción y trabajar hacia atrás

Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero n. Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero n. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero n+1.

Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.

Consideremos el siguiente ejemplo.

Problema. Demuestra que para todo entero no negativo n se tiene que

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}\]

es un número entero.

Solución. Tenemos que probar la afirmación para n\geq 0 entero. Procedemos por inducción sobre n. Si n=0, la expresión es igual a 0, así que la afirmación es cierta. Supongamos entonces que

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}\]

es entero y consideremos la expresión

    \[\frac{(n+1)^5}{5}+\frac{(n+1)^4}{2}+\frac{(n+1)^3}{3}-\frac{(n+1)}{30}.\]

Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para n. Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que

    \begin{align*}\frac{(n+1)^5}{5}&=\frac{n^5+5n^4+10n^3+10n^2+5n+1}{5}\\&=\frac{n^5}{5}+n^4+2n^3+2n^2+n+\frac{1}{5}\\\frac{(n+1)^4}{2}&=\frac{n^4+4n^3+6n^2+4n+1}{2}\\&=\frac{n^4}{4}+2n^3+3n^2+2n+\frac{1}{2}\\\frac{(n+1)^3}{3}&=\frac{n^3+3n^2+3n+1}{3}\\&=\frac{n^3}{3}+n^2+n+\frac{1}{3}\\-\frac{n+1}{30}&=-\frac{n}{30}-\frac{1}{30}.\end{align*}

Así, cuando hagamos la suma tenemos los términos

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30},\]

cuya suma es entera por hipótesis inductiva,

    \[n^4+2n^3+2n^2+n+2n^3+3n^2+2n+n^2+n,\]

que es entero pues n es entero y \frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}=1, de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.

\square

Si no comenzábamos a manipular la expresión para n+1, hubiera sido muy difícil, sólo a partir de la de n, llegar a la de n+1.

Inducción y generalización

Una forma sencilla de combinar inducción con generalización es la siguiente:

  • Nos piden demostrar una afirmación para un natural muy específico.
  • En vez de eso, construimos un problema más general que funcione “para todos los naturales”.
  • Resolvermos ese problema por inducción.

Veamos un ejemplo.

Problema. Muestra que

    \[\left(\frac{3+\sqrt{17}}{2}\right)^{2020}+ \left(\frac{3-\sqrt{17}}{2}\right)^{2020}\]

es un entero impar.

Solución. Sean \alpha=\frac{3+\sqrt{17}}{2} y \beta=\frac{3-\sqrt{17}}{2}. Se pide mostrar que \alpha^{2020}+\beta^{2020} es un entero impar. Mostraremos que, de hecho, \alpha^n+\beta^n es un entero impar para todo entero n\geq 1. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).

El primer caso es n=1 y notemos que \alpha^1+\beta^1=\alpha+\beta=3. Notemos también que \alpha\beta=\frac{9-17}{4}=-2, de modo que \alpha^2+\beta^2=(\alpha+\beta)^2-2ab=9+4=13, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes n-1 y n.

Consideremos el polinomio cuadrático

    \[(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-3x-2.\]

Como \alpha y \beta son raíces, tenemos que \alpha^2-3\alpha-2=0 y \beta^2-3\beta -2=0. Multiplicando estas igualdades por \alpha^{n-1} y \beta^{n-1} respectivamente, sumando ambas igualdades obtenidas, y despejando \alpha^{n+1}+\beta^{n+1} llegamos a

    \[\alpha^{n+1}+\beta^{n+1}=3(\alpha^n+\beta^n})+2(\alpha^{n-1}+\beta^{n-1}).\]

De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes n y n-1, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son n+1.

Para demostrar el problema original, basta con hacer la observación de que, en particular, \alpha^{2020}+\beta^{2020} es un entero impar.

\square

Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.

Problema. Demuestra que para todo entero n\geq 1 se tiene que

    \[\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots + \frac{1}{n(n+1)} <1.\]

Antes de resolver el problema, intentemos hacer una solución “ingenua” que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para n=1 al lado izquierdo tenemos únicamente \frac{1}{2} y al lado derecho 1. Supongamos que el resultado es cierto para n, es decir, que

    \[\frac{1}{1\cdot 2}+\ldots + \frac{1}{n(n+1)} <1.\]

Llamémosle M a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para n+1, es decir, que M+\frac{1}{(n+1)(n+2)}<1. Sabemos que M<1, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues M<1 es una afirmación “muy débil”. Veamos cómo darle la vuelta a esta dificultad.

Solución. Sea P(n) la afirmación del problema. Consideremos la afirmación Q(n) que dice que para todo entero n\geq 1 se tiene que

    \[\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots + \frac{1}{n(n+1)}} =1-\frac{1}{n+1}.\]

Si logramos demostrar Q(n), entonces P(n) será cierta de manera inmediata, pues 1-\frac{1}{n+1}<1. Vamos a demostrar Q(n) por inducción.

Tenemos que Q(1) es cierto pues en ambos lados de la igualdad queda \frac{1}{2}. Supongamos que Q(n) es cierto. Usando esto, tenemos que

    \begin{align*}\frac{1}{1\cdot 2}+\ldots+\frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &=\left(1-\frac{1}{n+1}\right)+\frac{1}{(n+1)(n+2)}\\&=1-\frac{(n+2)-1}{(n+1)(n+2)}\\&=1-\frac{1}{n+2},\end{align*}

es decir, que Q(n+1) es cierto. Así, por inducción Q(n) es cierto para todo entero n y con eso P(n) también.

\square

Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que P(n) implica P(n+1). Pero esto es imposible pues P(n) “es muy débil”, o bien “pierde información de todo lo que está pasando”. Sin embargo, cuando consideramos la afirmación auxiliar Q(n), resulta que esta “tiene más información”. Aquí, esta información es “qué tal lejos está la expresión de 1

La afirmación Q(n) tiene tanta información, que ahora sí con ella se puede probar Q(n+1). Se termina el problema usando que Q(n) implica P(n). Así, la estrategia fue la siguiente:

  • Se tiene una afirmación P(n) que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues P(n) parece no ser suficiente para probar P(n+1)
  • Se considera entonces una afirmación Q(n) más fuerte (que implique a P(n)), pero para la cual Q(n) sí pueda probar Q(n+1).
  • Se prueba Q(n) por inducción, y se concluye que P(n) es cierta.

Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance la generalización Q(n) que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.

Más ejemplos

Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas:

Seminario de Resolución de Problemas: Principio de Inducción

Esta es una serie de entradas de blog para dar seguimiento a los estudiantes del Seminario sobre Enseñanza de las Matemáticas (Resolución de Problemas) durante la época de cuarentena debida al coronavirus.

Introducción

El principio de inducción es una de las piedras angulares de las matemáticas y de la resolución de problemas. Es altamente probable que ya lo hayas utilizado previamente, en cursos como Álgebra Superior I y II, en Álgebra Lineal, en Cálculo y varios otros.

En esta entrada y las siguientes repasaremos la idea general del principio de inducción, pero además veremos lo flexible que puede ser en la resolución de problemas.

La idea general que debes tener cuando hagas inducción es pensar en Tlaloc (dios de la lluvia). Imagina que Tlaloc decide que llueva hoy, y además decide que si llueve un día, entonces lloverá también al día siguiente. Como llueve hoy, entonces lloverá mañana, pero como llueve mañana entonces lloverá pasado mañana. De hecho, ¡va a llover todos los días a partir de hoy!

De manera general, el principio de inducción sirve para cuando se quieren probar afirmaciones “para todo número natural n” y en donde para probar la afirmación para un valor n es útil tener la validez de la afirmación para los valores anteriores. Sin embargo, se puede también utilizar para probar afirmaciones “a partir de cierto natural”. Enunciamos esta versión a continuación.

Principio de inducción. Sea P(n) una afirmación (o proposición o propiedad) que depende del número natural n. Si

  • la afirmación P(a) es cierta y
  • la veracidad de la afirmación P(n) implica la veracidad de la afirmación P(n+1),

entonces la afirmación P(n) es cierta para toda n \geq a.

En estos términos, a probar la afirmación para a se le conoce como probar la base de inducción. Suponer la veracidad de P(n) para una n se conoce como suponer la hipótesis inductiva, y a probar la veracidad de P(n+1) se le conoce como hacer el paso inductivo. Así, para hacer una prueba por inducción se tienen que hacer los siguientes pasos:

  • Probar la base de inducción, osea, mostrar que P(a) es válido.
  • Suponer, libremente, la hipótesis inductiva, es decir, suponer que P(n) cierto.
  • A partir de la hipótesis inductiva, y el resto de las hipótesis del problema, hacer el paso inductivo, es decir, demostrar P(n+1).

Es muy importante hacer estos tres pasos. Si no se prueba la base de inducción, es como si Tlaloc no decidiera que lloviera hoy: no hay forma de saber qué pasara. Si no se hace el paso inductivo, es como si Tlaloc no dijera nada de la lluvia de un día a partir del anterior.

La creatividad en el uso de la inducción en la resolución de problemas reside en varios aspectos. A veces:

  • Se requiere ingenio para probar el caso base.
  • Se requiere ingenio para saber exactamente cómo usar la hipótesis inductiva para hacer el paso inductivo.
  • Se requiere crear una afirmación auxiliar Q(n) más fuerte que implique a P(n), tal qué Q(n) sí se pueda probar por inducción, pero P(n) no, de lo cual veremos ejemplos en siguientes entradas.

Problemas con solución

Veamos algunos ejemplos de problemas que se pueden resolver utilizando induccicón. En el primer problema vamos a ser muy explícitos en cómo estamos ejecutando la inducción. Esto te puede ayudar cuando estas haciendo tus primeras pruebas de inducción: te ayudará a ser explícito en demostrar la base, en suponer la hipótesis inductiva y en hacer el paso inductivo.

En algunas otras de las demostraciones, vamos a ser un poco más flexibles con cómo se escribe la demostración. No hay que ser totalmente explícitos en qué parte de demostración por inducción se está haciendo. Esto te puede ayudar para cuando ya estas escribiendo una prueba más larga y la parte inductiva sólo es un pequeño fragmento del argumento.

Problema. Sea n\geq 1 un número entero y a_n>a_{n-1}>\ldots>a_1>0 números reales. Considera todas las expresiones que puedes hacer de la forma

    \[e_1a_1+e_2a_2+\ldots+e_na_n\]

donde cada e_i es 1 o 0. Demuestra que al pasar por todas las 2^n posibilidades para las e_i se forman por lo menos \binom{n+1}{2} números diferentes.

Solución. Vamos a proceder por inducción sobre n. Hagamos primero la base de inducción. Como queremos demostrar la afirmación para toda n\geq 1, el caso base es n=1. Cuando n=1, tenemos un sólo número real a_1>0 y lo que tenemos que demostrar es que hay al menos \binom{2}{2}=1 valor en las expresiones que se pueden formar. Si e_1=0 o 1, obtenemos las expresiones 0 y a_1 respectivamente, que son al menos dos. Esto prueba el caso base.

Ahora supongamos la hipótesis inductiva. Es decir, suponemos libremente que para cierta n, cada que tomamos n números reales se cumple la afirmación del problema, es decir, que al pasar por las 2^n posibilidades de e_i, se obtienen al menos \binom{n+1}{2} expresiones diferentes.

La parte final es hacer el paso inductivo. Es decir, a partir de todas las hipótesis del problema, de la hipótesis inductiva, y de otras ideas, tenemos que probar la afirmación para n+1. Así, tomemos n+1 números reales

    \[a_{n+1}>a_n>\ldots>a_1>0.\]

Tenemos que mostrar que usando coeficientes 0 y 1 podemos formar al menos \binom{n+2}{2} números distintos.

Una buena idea es aprovechar que ya sabemos que los números

    \[a_n>\ldots>a_1>0\]

ya hacen varias expresiones. Podemos aplicar la hipótesis inductiva a estos números, y con ello logramos conseguir al menos \binom{n+1}{2} expresiones diferentes. Notemos que estas expresiones también sirven para cuando tenemos a a_{n+1} y le ponemos coeficiente e_{n+1}=0. Lo que tenemos que hacer ahora es conseguir \binom{n+2}{2}-\binom{n+1}{2}=n+1 expresiones nuevas.

Consideremos la expresión S=a_1+a_2+\ldots+a_n en la que todos los coeficientes son 1. Esta es claramente mayor que cualquiera de las otras que ya tenemos. Además, todas las expresiones S+a_{n+1}, S+a_{n+1}-a_1, S+a_{n+1}-a_2, \ldots, S+a_{n+1}-a_n son mayores que S (pues a_{n+1} es el más grande de los a_i‘s), son todas diferentes, y son de la forma deseada (pues cada a_i con 1\leq i \leq n está en S).

De esta forma, conseguimos n+1 expresiones distintas y todas ellas mayores que S, así que distintas de todas las dadas por la hipótesis inductiva. Con esto completamos la demostración.

\square

La inducción sirve para probar afirmaciones que dependen de un número natural. Sin embargo, no siempre es inmediato de dónde sale este natural. A veces ese natural aparece simplemente como el tamaño de algún conjunto involucrado. A veces hay que hacer una demostración para “todos los polinomios” y entonces podríamos intentar hacer inducción sobre el grado del polinomio. En otro problema puede que se tenga que mostrar algo “para todas las matrices” y entonces tal vez tengamos que demostrarlo por inducción sobre las dimensiones de la matriz.

Problema. Se dibuja una cantidad finita de lineas en el espacio de modo que no haya tres de ellas que pasan por un mismo punto. Estas líneas definen regiones en el plano. Muestra que se pueden colorear estas regiones de blanco o negro de modo que no haya dos regiones del mismo color que tengan un lado en común.

El problema no tiene ningún número natural explícitamente en el enunciado. Sin embargo, se pide demostrar algo para una cantidad finita de cosas, así que basta probar la afirmación para n cosas, para todo entero n\geq 0. De esta forma, la variable “cantidad de líneas que tenemos” ya es una variable sobre la cual podemos hacer inducción. Hagamos la demostración así.

Solución. Procedamos por inducción sobre el número de líneas. Si tenemos 0 líneas, sólo hay una región en el plano. La pintamos de blanco.

Ahora, supongamos que cada que tenemos n líneas, no tres de ellas por un punto, podemos hacer una coloración de su conjunto de regiones R de modo que no haya dos adyacentes del mismo color.

Tomemos cualquier conjunto de n+1 líneas. Tomemos una de ellas L e ignorémosla por el momento. Por hipótesis inductiva, podemos hacer una coloración para las n líneas que quedan. Al regresar L se hacen nuevas regiones. A las regiones que quedan de un lado de L, las dejamos del color que ya tenían. A las que están del otro lado de L, les intercambiamos el color (blanco a negro y viceversa).

El nuevo acomodo funciona pues todas las regiones de R totalmente contenidas en alguno de los lados de L siguen sin problemas. Y aquellas regiones de R cortadas por L sólo pueden tener problemas con un lado que caiga sobre L. Pero de estos problemas tampoco hay pues de un lado quedaron de un color, y del otro del otro.

\square

Observa que en el problema anterior ya no estamos haciendo los pasos de la inducción tan “explícitos”.

A veces hay problemas en los que hay una variable entera, pero no necesariamente hay que aplicar inducción para esa variable, sino para otro parámetro que introduzcamos.

Problema. Dado un entero positivo n y un real x\geq 0, muestra que

    \[\floor{x}+\floor{x+\frac{1}{n}}+\floor{x+\frac{2}{n}}+\cdots+\floor{x+\frac{n-1}{n}}=\floor{nx}.\]

Recuerda que \floor{y} es el mayor entero que sea menor o igual a y.

Solución. El problema con hacer inducción en n es que no hay una forma sencilla de relacionar el resultado para n y el resultado para n+1. Tampoco podemos hacer “inducción sobre x” porque x es un número real.

El truco para el problema es probar el resultado para todas las x en el intervalo [\frac{k}{n},\frac{k+1}{n}) para todo entero k\geq 0. Con esos intervalos cubrimos a todos los reales positivos, y por lo tanto cubrimos todas las posibilidades para x. Para probar que se vale en esos intervalos, vamos a proceder por inducción sobre k.

Si k=0, entonces queremos mostrar el resultado para el intervalo [0,\frac{1}{n}). Para las x en este intervalo, cada uno de los términos x+\frac{i}{n} (para i-0,1,\ldots,n-1) es menor que 1 y por lo tanto el lado izquierdo de la igualdad que queremos mostrar tiene puros sumandos 0 y entonces es igual a 0. También para las x en este intervalo tenemos nx<1, y así el lado derecho también es 0. Esto prueba la base inductiva.

Supongamos ahora que el resultado es cierto para x en el intervalo [\frac{k-1}{n},\frac{k}{n}) para cierto entero k. Esto quiere decir que

    \[\floor{x}+\floor{x+\frac{1}{n}}+\floor{x+\frac{2}{n}}+\cdots+\floor{x+\frac{n-1}{n}}=\floor{nx}.\]

Tomemos ahora un entero y en el intervalo [\frac{k}{n},\frac{k+1}{n}). Notemos que x=y-\frac{1}{n} está en el intervalo anterior, de modo que cumple la igualdad de la hipótesis inductiva. Notemos además que si en

    \[\floor{y}+\floor{y+\frac{1}{n}}+\floor{y+\frac{2}{n}}+\cdots+\floor{y+\frac{n-1}{n}}\]

substituimos y=x+\frac{1}{n}, obtenemos

    \[\floor{x+\frac{1}{n}}+\floor{x+\frac{2}{n}}+\floor{x+\frac{3}{n}}+\cdots+\floor{x+\frac{n}{n}}.\]

El último sumando es \floor{x+1}=\floor{x}+1, de modo que en el lado izquierdo tenemos todos los sumandos del lado izquierdo de la hipótesis inductiva y un 1. Así, el lado izquierdo es igual a

    \[\floor{nx}+1=\floor{nx+1}=\floor{ny},\]

como queríamos mostrar.

\square

Más ejemplos

Puedes encontrar más ejemplos en la Sección 2.1 del Problem Solving through Problems de Loren Larson. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. Así mismo, aquí en el blog hay otras entradas en las que se hacen pruebas por inducción.

Buscar un patrón

HeuristicasLa primer cosa que se puede hacer para empezar a resolver un problema es jugar con él. Hay que acostumbrarse a cómo funcionan sus elementos y para esto se hacen problemas chiquitos. En esta serie de videos veremos la idea general de buscar un patrón y realizaremos algunas conjeturas con esta técnica.

Ir a los videos…