Principio de inducción

[pod]

Tenemos un enunciado A(n) que depende de un número natural, $n \in \mathbb{N}$. Queremos demostrar que ese enunciado es cierto para todos los valores de n. Una forma de hacerlo sería tomar todos los valores posibles y ver que se cumple; es decir, A(1), A(2), A(3)... Pero como hay infinitos números naturales, sería un coñazo por que no terminaríamos a tiempo para la cena.

A alguien que tenía muchas ganas de cenar ya se le ocurrió una forma de hacer todas esas demostraciones a la vez. Se dio cuenta que, tras hacer muchas demostraciones de estas, cada vez que iba al siguiente número tenía que repetir prácticamente el mismo procedimiento. Pensó que sería fantástico que, una vez hecha una demostración, la siguiente ya estuviera hecha por si sola, ya que sería similar. Entonces, se le ocurrió lo siguiente.

Supongamos que A(n) es cierta. Fíjate que aquí n es un número natural cualquiera. Es un número fijo, pero puede ser cualquiera de ellos. Este A(n) no hay que demostrarlo, supongo que es cierto. Esto es lo que llamamos hipótesis.

Entonces, si soy capaz de demostrar que el hecho que A(n) sea cierto, implica necesariamente que A(n+1) también es cierto, tendré mucho trabajo hecho. Es decir, utilizando el hecho que A(n) se cumple, tengo llegar a demostrar que A(n+1) también es cierto.

Si consigo hacer esa demostración, entonces siempre que encuentre un A(m) que sea cierto, entonces automáticamente sabré que A(m+1) también es cierto. Repitiendo el razonamiento, sabré que A(m+2) también es cierto. Y así sucesivamente.

Una vez hecho esto, si yo consigo demostrar que A(1) es cierto (es decir, la proposición para el primer número natural posible), entonces automáticamente sabré que A(2) es cierto. Y A(3)... y de hecho, saltando de uno en uno podré llegar a cualquier número natural.

A la práctica, para usar el método de inducción, tengo que seguir los siguientes pasos.

1) Demostrar que la proposición es cierta para el primer valor posible, A(1). A veces, puede ser que el primer valor posible sea cero; o puede que sea para un valor mayor.

2) Suponer que A(n) es cierto para un valor general de n. Fijaos que aquí no tengo que demostrar nada, supongo que es cierto. Es mi hipótesis de inducción.

3) Haciendo uso de que sé que A(n) es cierto, tengo que demostrar que A(n+1) también es cierto. Éste es el paso más complicado. En general, hay dos vías para hacer esa demostración: partir de lo que sabemos que es cierto y, tras ciertas manipulaciones, obtener la expresión A(n+1) (esto es lo que hacemos en este problema). O bien, partir de A(n+1) y haciendo uso de la hipótesis, demostrar que es cierta (como en este otro problema).

En definitiva, el paso tres nos asegura que siempre que encontremos un A(n) que se cumple, podemos pasar al siguiente automáticamente. Al final, recorremos todos los números, saltando de uno en uno:

$$<br /> A(1) \Rightarrow A(2) \Rightarrow A(3) \Rightarrow A(4) \Rightarrow \cdots \Rightarrow A(n) \Rightarrow A(n+1) \Rightarrow A(n+2) \Rightarrow \ldots \ .$$

Hagamos un par de ejemplos.


Ejemplo 1

Queremos demostrar que $2^n > n$.

1) El primer valor es n = 1. Simplemente tenemos que substituir,

$$2 > 1\ ,$$

lo cual es cierto. Por lo tanto, el enunciado es cierto para el primero de los números posibles.

2) Suponemos que la expresión es cierta para un n arbitrario,

$$2^n >n \ .$$

Esto es algo que es cierto, por hipótesis, y por lo tanto lo puedo utilizar siempre que lo necesite.

3) Ahora, haciendo uso de lo anterior, tengo que demostrar que también es cierto

$$2^{n+1} > n+1\ .$$

¿Cómo demuestro que (2) es cierto? Pues parto de (1), que sé que es cierto. Multiplico por dos ambos lados de la desigualdad,

$$2^{n+1} > 2n\ .$$

Como he multiplicado por dos una desigualdad que sé que es cierta, esta última desigualdad también debe serlo, forzosamente. Ahora bien, comparando (2) y (3), se me ocurre escribir la cadena de desigualdades

$$2^{n+1} > 2n \ge n+1\ .$$

Fíjate que si esta cadena de desigualdades se cumple, se deduce que (2) es cierta. Así que ahora tengo que demostrar esta cadena de igualdades.

La primera desigualdad de la cadena yo sé que es cierta, por que no es más que (3). Sólo me queda demostrar la segunda desigualdad,

$$2n \ge n+1 \Longrightarrow n \ge 1 \ .$$

Como n es mayor (o igual) a 1, entonces este eslabón de la cadena también es cierto. En resumen, ya hemos demostrado toda la cadena. De esa cadena, se deduce que la ecuación (2) es cierta. Eso completa la demostración.


Ejemplo 2

Queremos demostrar

$$\sum_{i=1}^n \frac{1}{i (i+1)} = \frac{n}{n+1}\ .$$

1) Lo primero a hacer es demostrar que se cumple para n = 1. Es decir, escribir lo mismo poniendo n = 1, simplemente.

$$\sum_{i=1}^1 \frac{1}{i (i+1)} = \frac{1}{1+1}\ .$$

Este sumatorio sólo tiene un término, ya que i empieza en uno y termina en 1. O sea, operando tenemos que ambos lados de la igualdad dan 1/2. Por lo tanto, la igualdad se cumple, está bien.

2) El siguiente paso, es suponer que la proposición es válida para n,

$$\sum_{i=1}^n \frac{1}{i (i+1)} = \frac{n}{n+1}\ .$$

3) Una vez supuesto eso, tienes utilizarlo para demostrar que también es cierto para n+1. Por lo tanto, se trata de escribir lo mismo substituyendo n por n+1,

$$\sum_{i=1}^{n+1} \frac{1}{i (i+1)} = \frac{n+1}{n+2}\ .$$

Esto es lo que queremos demostrar. Si comparas esta ecuación con la original, la única diferencia es que el sumatorio tiene un término más: antes terminaba en n, y ahora termina en n+1. Lo que hacemos es separar ese término,

$$\sum_{i=1}^{n+1} \frac{1}{i (i+1)} = \sum_{i=1}^{n} \frac{1}{i (i+1)} +\left. \frac{1}{i(i+1)}\right|_{i=n+1} = \sum_{i=1}^{n} \frac{1}{i (i+1)} + \frac{1}{(n+1)(n+2)}\ .$$

Como veis, lo único que he hecho es separar el último término, que es el que i = n+1, y por eso hago esa substitución al final. Ahora bien, el sumatorio hasta n ya sabemos cuanto vale, antes hemos hecho la suposición de que la ecuación original era válida, lo que nos permite substituir

$$<br /> \sum_{i=1}^{n+1} \frac{1}{i (i+1)} = \underbrace{\sum_{i=1}^{n} \frac{1}{i (i+1)}}_{n/(n+1)} + \frac{1}{(n+1)(n+2)} = \frac{n}{n+1} + \frac1{(n+1)(n+2)}\ .<br />$$

Para terminar, sólo tenemos que hacer la suma de fracciones,

$$<br /> \sum_{i=1}^{n+1} \frac{1}{i (i+1)} = \frac{1}{n+1} \left( n + \frac{1}{n+2} \right) = \frac1{n+1} \dfrac{n(n+2) + 1}{n+2}<br /> = \frac1{n+1} \frac{(n+1)^2}{n+2}\ .<br />$$

Juntándolo todo, llegamos exactamente a (5), que es lo que queríamos demostrar. Esto completa la demostración por inducción.

[er_javivi]

¿Como lo podemos ver para las matrices? Por ejemplo:

La matriz A 1 1 elevado a n = 1 n
0 1 0 1

[er_javivi]

Perdonad, no se mostro la operacion como deseaba.

Sea A una matriz con la siguiente estructura (a11=1 a12 = 1 a21 = 0 a22 = 1)^n me dice que es igual a esta otra matriz (a11=1 a12 = n a21 =0 a22 = 1)

El enunciado me dice que demuestre por induccion la igualdad previamente descrita.

Entiendo mas o menos como es el proceso que habeis descrito para los dos ejercicicos anteriores, pero no se exactamente como he de ponerlo para que se vea claramente que lo he demostrado.

No se si me explico, si no entendeis algo lo aclarare mas detalladamente.

Un saludo y muchas gracias.

[GNzcuber]

¡Hola er_javivi!
Bueno veo que tu post tiene más de un mes, pero como no veo respuesto, no sé si te la han dado por mensaje privado, porque esto es un blog, y eso se debería preguntar en el foro.
Sin embargo te la contestaré:

Tenemos la siguiente igualdad:

$$\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)^{n} = \left( \begin{matrix} 1 & n \\ 0 & 1 \end{matrix} \right)$$

1) Debemos mostrar que se cumple para n=1:

$$\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)^{1} = <br /> \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)<br />$$

Que es cierto.

2) Suponemos cierto para n y lo demostraremos para n+1:

$$\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)^{n+1} = \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)^{n} \cdot \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}\right) = \left( \begin{matrix} 1 & n \\ 0 & 1 \end{matrix} \right) \cdot \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right) = \left( \begin{matrix} 1 & n+1 \\ 0 & 1 \end{matrix} \right)$$

Que es efectivamente lo que tendríamos al sustituir n por n+1 (La tercera igualdad de la ecuación es la hipótesis de la inducción).
P.D.: Es la primera vez que utilizo LaTex, y me he tirado mi horita con esto, pero debo confesar que fue algo divertido .