Demostracion de induccion matematica

Principio de inducciónLa propiedad fundamental que define al conjunto N$\mathbb{N}$ es la propiedad de inducción. Esta nos dice que si A$A$ es un conjunto de números naturales que cumple que

1. A$A$ contiene al uno.
2. Si A$A$ contiene a un número n$n$, entonces también contiene a n+1$n+1$.

Entonces A$A$ contiene a todos los números naturales.

Es fácil darse cuenta de por qué este principio es cierto. Supongamos que un conjunto de números naturales A$A$ cumple las condiciones (a) y (b) anteriores y cojamos un número natural: el 5$5$, por ejemplo. Para responder a la pregunta de si 5$5$ pertenece a A$A$, razonamos como sigue: según (a) tenemos que 1∈A$1\in A$, de que 1∈A$1\in A$ deducimos que 2∈A$2\in A$ usando ahora (b), volviendo a usar (b) (y como 2∈A$2\in A$) tenemos que 3∈A$3\in A$; usando (b) dos veces más tenemos que 4∈A$4\in A$ y 5∈A$5\in A$. Es obvio que este proceso se podría haber hecho con cualquier número natural en lugar de 5$5$, aunque hubiera sido más tedioso escribir todos los pasos.

La principal utilidad del principio de inducción es que nos permite demostrar una gran cantidad de propiedades concernientes a números naturales. Concretamente, si P(n)$P(n)$ es una afirmación para cada número natural n$n$ y probamos que P(1)$P(1)$ es cierta y que si P(k)$P(k)$es cierta también lo es P(k+1)$P(k+1)$, habremos probado que P(n)$P(n)$ es cierta para cualquier número natural n$n$. Esto es consecuencia de tomar en el principio de inducción ???$\text{???}$ el conjunto A$A$ como el conjunto de los números naturales k$k$ para los que P(k)$P(k)$ es cierta. Veamos cómo se aplica todo esto con un ejemplo.

Ejercicio resueltoDemostrar que, para cualquier número natural n$n$, se cumple que

1+2+…+n=12n(n+1).$$1+2+\dots +n=\frac{1}{2}n(n+1).$$

Solución. En este caso, la afirmación P(n)$P(n)$ es 1+2+…+n=12n(n+1)$1+2+\dots +n=\frac{1}{2}n(n+1)$; por ejemplo,

P(1)⟶1=12⋅1⋅(1+1)P(3)⟶1+2+3=12⋅3⋅(3+1)P(2)⟶1+2=12⋅2⋅(2+1)P(4)⟶1+2+3+4=12⋅4⋅(4+1) …$$\begin{array}{lcl}P(1)⟶1=\frac{1}{2}\cdot 1\cdot (1+1)& & P(2)⟶1+2=\frac{1}{2}\cdot 2\cdot (2+1)\\ P(3)⟶1+2+3=\frac{1}{2}\cdot 3\cdot (3+1)& & P(4)⟶1+2+3+4=\frac{1}{2}\cdot 4\cdot (4+1)\dots \end{array}$$

es decir, la fórmula que queremos probar para un valor concreto. P(1)$P(1)$ es cierta ya que ambos miembros de la igualdad toman el valor 1. Supongamos que k$k$ es un número natural para el que P(k)$P(k)$ es cierta, es decir, tal que se cumple que 1+2+…+k=12k(k+1)$1+2+\dots +k=\frac{1}{2}k(k+1)$ y veamos que P(k+1)$P(k+1)$ es cierta, es decir, tendremos que probar que 1+2+…+(k+1)=12(k+1)(k+2)$1+2+\dots +(k+1)=\frac{1}{2}(k+1)(k+2)$. Observemos que

1+2+…+(k+1)==(1+2+…+k)+(k+1)12k(k+1)+(k+1)=12(k+1)(k+2),$$\begin{array}{rcl}1+2+\dots +(k+1)& =& (1+2+\dots +k)+(k+1)\\ & =& \frac{1}{2}k(k+1)+(k+1)=\frac{1}{2}(k+1)(k+2),\end{array}$$

lo que nos da la demostración buscada. Obviamente, hemos tenido que usar que P(k)$P(k)$es cierta para probar que también lo es P(k+1)$P(k+1)$ y es por esto que suele llamarse hipótesis de inducción a la suposición de que P(k)$P(k)$ es cierta (si no usáramos la hipótesis de inducción, no estaríamos demostrando el enunciado por el principio de inducción).

Conviene aquí resaltar que no es usual ni necesario especificar con tanto detalle las demostraciones en que se usa el método de inducción ni tampoco es necesario usar la variable genérica n$n$ y cambiarla a otra variable k$k$ cuando se pasa al caso concreto. La solución del problema anterior podría escribirse mucho más resumida pero igualmente válida de la siguiente manera.

Solución. La igualdad es cierta para n=1$n=1$ pues ambos miembros son iguales a 1$1$. Supuesto que es cierta para n∈N$n\in \mathbb{N}$, para n+1$n+1$ tendremos que

1+2+…+(n+1)==(1+2+…+n)+(n+1)12n(n+1)+(n+1)=12(n+1)(n+2),$$\begin{array}{rcl}1+2+\dots +(n+1)& =& (1+2+\dots +n)+(n+1)\\ & =& \frac{1}{2}n(n+1)+(n+1)=\frac{1}{2}(n+1)(n+2),\end{array}$$

lo que prueba por inducción la igualdad del enunciado.

Ejercicio propuestoComprobar que, para cualquier número natural n$n$, se cumple que

1. 12+22+…+n2=16n(n+1)(2n+1)$1^2+2^2+\dots +n^2=\frac{1}{6}n(n+1)(2n+1)$
2. 13+23+…+n3=14n2(n+1)2$1^3+2^3+\dots +n^3=\frac{1}{4}{n}^2(n+1{)}^2$
3. 1+x+x2+…+xn=xn+1−1x−1$1+x+x^2+\dots +x^n=\frac{x^{n+1}-1}{x-1}$ para cualquier número real x≠1$x\ne 1$.

Otro caso en el que vamos a usar el principio de inducción y que conviene destacar ahora es el cálculo de la suma de los términos de una progresión aritmética y de una progresión geométrica.

1. Una progresión aritmética es una sucesión de números en la que la diferencia entre dos términos consecutivos es constante (por ejemplo, la sucesión 1,5,9,13,17,…$1,5,9,13,17,\dots$, donde la diferencia es 4$4$). Las progresiones aritméticas vienen determinadas por el término inicial y la diferencia: si el término inicial es a1$a_1$ y la diferencia es d$d$, los siguientes términos serán a2=a1+d$a_2=a_1+d$, a3=a2+d=a1+2d$a_3=a_2+d=a_1+2d$, a4=a3+d=a1+3d$a_4=a_3+d=a_1+3d$, etc,... y, en general, an=a1+(n−1)d$a_n=a_1+(n-1)d$. La suma de los términos de esta sucesión está dada por
   a1+(a1+d)+…+(a1+(n−1)d)==na1+d(1+2+…+(n−1))na1+12dn(n−1),$$\begin{array}{rcl}{a}_1+(a_1+d)+\dots +(a_1+(n-1)d)& =& n{a}_1+d(1+2+\dots +(n-1))\\ & =& n{a}_1+\frac{1}{2}dn(n-1),\end{array}$$
   donde se ha usado la fórmula del ejercicio resuelto para 1+2+…+n$1+2+\dots +n$.
2. Una progresión geométrica es una sucesión de números en la que cada término se obtiene multiplicando el anterior por una constante, que se llama razón de la progresión (por ejemplo, la sucesión 1,2,4,8,16,…$1,2,4,8,16,\dots$, donde la razón es 2$2$). Las progresiones geométricas vienen determinadas por el término inicial y la razón: si el término inicial es a1$a_1$ y la razón es r$r$, los siguientes términos serán a2=ra1$a_2=r{a}_1$, a3=ra2=r2a1$a_3=r{a}_2=r^2{a}_1$, a4=ra3=r3a1$a_4=r{a}_3=r^3{a}_1$, etc,... y, en general, an=rn−1a1$a_n=r^{n-1}{a}_1$. La suma de los términos de esta sucesión está dada por
   a1+ra1+r2a1+…+rn−1a1=a1(1+r+r2+…+rn−1)=a1rn−1r−1=an+1−a1r−1,$$a_1+r{a}_1+r^2{a}_1+\dots +r^{n-1}{a}_1=a_1(1+r+r^2+\dots +r^{n-1})=a_1\frac{r^n-1}{r-1}=\frac{a_{n+1}-a_1}{r-1},$$
   donde se ha usado la fórmula del apartado c del ejercicio propuesto anteriormente.