{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Principio de inducción"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introducción"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"En esta entrada supondremos que manejas el principio de inducción, por lo menos a un nivel básico. En caso de no ser así, te recomendamos revisar la siguiente entrada de blog: Introducción a principio de inducción.\n",
"\n",
"Como quizás recuerdes, el principio de inducción permite hacer demostraciones matemáticas para una cantidad infinita de números, probando simplemente una cantidad finita de afirmaciones, usualmente dos. En su versión más básica dice lo siguiente:\n",
"\n",
"**Principio de inducción.** Para mostrar que una afirmación $P(n)$ es cierta para todo entero positivo $n$ basta con:\n",
"\n",
"- Mostrar que $P(1)$ es cierta.\n",
"- Mostrar que para $n\\geq 1$, se tiene que $P(n)$ implica $P(n+1)$.\n",
" \n",
"En esta entrada recordaremos cómo usar el principio de inducción en su versión básica y luego discutiremos variantes del principio de inducción que cumplen con el mismo objetivo, pero son más versátiles."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Principio de inducción básico\n",
"\n",
"Para recordar cómo se usa el principio de inducción resolvamos el siguiente problema.\n",
"\n",
"**Problema.** Muestra que para todo entero $n$ se cumple que\n",
"\n",
"$$\\frac{1}{1\\cdot 2} + \\frac{1}{2\\cdot 3} + \\ldots + \\frac{1}{n\\cdot (n+1)}=\\frac{n}{n+1}$$\n",
"\n",
"*Solución.* Hagamos una solución que use principio de inducción. Para ello, necesitamos comenzar verificando que la igualdad es cierta cuando $n=1$. Luego, a partir de la veracidad de la igualdad para cierta $n$, debemos demostrar la veracidad para $n+1$.\n",
"\n",
"La veracidad para $n=1$ es sencilla de verificar, pues en lado izquierdo tendríamos únicamente al sumando $\\frac{1}{1\\cdot 2} = \\frac{1}{2}$, mientras que en el lado derecho tendríamos la expresión $\\frac{1}{2}$. Ambas expresiones son iguales.\n",
"\n",
"Como hipótesis inductiva, supongamos la veracidad de la igualdad para cierto valor de $n$. Aquí $n$ es fijo, no estamos suponiendo la veracidad para todo $n$, pues eso es lo que queremos mostrar. De esta manera, tenemos que \n",
"\n",
"$$\\frac{1}{1\\cdot 2} + \\frac{1}{2\\cdot 3} + \\ldots + \\frac{1}{n\\cdot (n+1)}=\\frac{n}{n+1}.$$\n",
"\n",
"Debemos mostrar la veracidad para $n+2$, es decir, debemos mostrar que \n",
"\n",
"$$\\frac{1}{1\\cdot 2} + \\frac{1}{2\\cdot 3} + \\ldots + \\frac{1}{n\\cdot (n+1)} + \\frac{1}{(n+1)(n+2)}=\\frac{n+1}{n+2}.$$\n",
"\n",
"Para ello, notemos que en el lado izquierdo aparece parte de la expresión de la hipótesis inductiva. Tenemos entonces:\n",
"\n",
"\\begin{align*}\n",
"\\left(\\frac{1}{1\\cdot 2} + \\frac{1}{2\\cdot 3} + \\ldots + \\frac{1}{n\\cdot (n+1)}\\right) + \\frac{1}{(n+1)(n+2)} &= \\frac{n}{n+1}+ \\frac{1}{(n+1)(n+2)}\\\\\n",
"&=\\frac{n(n+2)+(1)}{(n+1)(n+2)}\\\\\n",
"&=\\frac{n^2+2n+1}{(n+1)(n+2)}\\\\\n",
"&=\\frac{(n+1)^2}{(n+1)(n+2)}\\\\\n",
"&=\\frac{n+1}{n+2}.\n",
"\\end{align*}\n",
"\n",
"En la primera igualdad usamos la hipótesis inductiva. Luego, simplemente hicimos las operaciones con fracciones. Notemos que llegamos justo al lado derecho que queríamos llegar. Esto termina la prueba por inducción.\n",
"$\\square$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Inducción fuerte"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Existen variantes del principio de inducción que son igual de válidas. La siguiente se le conoce como el principio de inducción fuerte, pues en la hipótesis inductiva suponemos no solamente un caso, sino también todos los anteriores.\n",
"\n",
"**Principio de inducción fuerte.** Para mostrar que una afirmación $P(n)$ es cierta para todo entero positivo $n$ basta con:\n",
"\n",
"- Mostrar que $P(1)$ es cierta.\n",
"- Mostrar que para $n\\geq 2$, **todas** las afirmaciones $P(k)$ para $k$\\square$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La idea de usar inducción fuerte es muy buena: podemos demostrar cosas utilizando casos que ya hemos demostrado. Esta misma intuición la utilizaremos cuando diseñemos algoritmos recursivos. Mientras tanto, estudia el siguiente código para ver cómo llevamos la idea de la demostración anterior a un algoritmo que escribe a cualquier entero positivo como suma de Fibonaccis distintos."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"El número 553 es la suma de los Fibonaccis en la lista [377, 144, 21, 8, 3]\n",
"El número 53 es la suma de los Fibonaccis en la lista [34, 13, 5, 1]\n",
"El número 111 es la suma de los Fibonaccis en la lista [89, 21, 1]\n"
]
}
],
"source": [
"def sum_fibo(n):\n",
" fibo=[0,1]\n",
" while fibo[-1]$\\square$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Tarea moral"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1. Si no somos cuidadosos con los argumentos inductivos, podemos tener problemas y demostrar cosas falsas. Considera el siguiente \"argumento\" inductivo que muestra que todos los gatos son del mismo color. Procedemos por inducción. Si tenemos un gato, sólo hay un color que verificar. Supongamos que ya verificamos que siempre que tenemos $n$ gatos, entonces todos son del mismo color. Toma un conjunto $X$ de $n+1$ gatos y dos gatos $G$ y $H$ de $X$. Si a $X$ le quitamos el gato $G$, por hipótesis inductiva todos son del mismo color. Si a $X$ le quitamos el gato $H$, por hipótesis todos son del mismo color. Así, $G$ es del mismo color que los gatos de $X$, que son del mismo color que $H$, así que ya todos los $n+1$ gatos fueron del mismo color. Esto termina la \"demostración\". ¿Cuál es el problema?\n",
"2. Considera la matriz $A=\\begin{pmatrix} 1 & 2 \\\\ 0 & 1\\end{pmatrix}$. Encuentra a mano las matrices $A^2$, $A^3$, $A^4$, $A^5$. Obsérvalas con detenimiento. Conjetura una expresión cerrada para la matriz $A^n$ y demuéstrala por inducción.\n",
"3. Regresa al capítulo de \"Buscar un patrón\", a la sección de \"Triángulo de Pascal con saltos de tres en tres\". Demuestra por inducción todas las observaciones que se hicieron para obtener la solución.\n",
"4. Muestra que cualquier número entero positivo se puede expresar de manera única como suma de números de Fibonacci distintos, en donde ademas no usamos dos números de Fibonacci $F_n$ y $F_m$ con $n$ y $m$ consecutivos.\n",
"5. Hay otra variante del principio de inducción que se llama \"inducción de Cauchy\". Revisa la siguiente entrada de blog para averiguar en qué consiste: Variantes del principio de inducción."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.11"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autoclose": false,
"autocomplete": false,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}