8.3: Otras Versiones de Inducción

A veces es difícil aplicar el Principio de Inducción Matemática en la forma que hemos manifestado en Axioma\(8.1.2\). La siguiente proposición proporciona algunas versiones alternativas que son más útiles en algunas de esas situaciones. Todos ellos siguen con bastante facilidad desde el enfoque utilizando “bien ordenado” que se discutirá en la siguiente sección.

Proposición\(8.3.1\).

Supongamos que\(P(n)\) es un predicado de números naturales, y\(m \in \mathbb{N}^{+}\).

1. (Inducción fuerte) Si
   1. \(​​​​​​P(1)\)es verdad, y
   2. para cada\(n \geq 2\),\[((\text { for every } k \in\{1,2, \ldots, n-1\}, P(k)) \Rightarrow P(n)) .\]
      entonces\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).
2. (Inducción generalizada) Si
   1. \(P(m)\)es verdad, y
   2. para cada\(n > m\),\((P(n-1) \Rightarrow P(n))\),
      entonces\(P(n)\) es cierto para todos\(n \geq m\).
3. (Inducción fuerte con múltiples casos base) Si
   1. \(P(k)\)es cierto para todos\(k \in\{1,2, \ldots, m\}\), y
   2. para cada\(n > m\),\[((\text { for every } k \in\{1,2, \ldots, n-1\}, P(k)) \Rightarrow P(n)),\]
      entonces\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).
4. Si
   1. \(P(1)\)es verdad, y
   2. para cada\(k \in \mathbb{N}^{+}\),\(P(k) \Rightarrow P(k+1)\),
      entonces\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).
5. Supongamos\(S \subset \mathbb{N}^{+}\). Si
   1. \(1 \in S\), y
   2. para cada\(n \in S\),\((n+1 \in S)\),
      entonces\(S = \mathbb{N}^{+}\).

Leer después de terminar Ejemplo\(8.3.3.\)

Prueba

POR INDUCCIÓN.

Definir\(P(n)\) para ser la aserción\[F_{n}<2^{n}.\]

Utilizamos inducción fuerte con 2 casos base.

1. Casos base. Tenemos\[F_{1}=1<2=2^{1}\]
   y\[F_{2}=1<4=2^{2},\]
   así\(P(1)\) y\(P(2)\) somos verdad.
2. Paso de inducción. Asumir\(n \geq 3\), y eso\(P(n − 1)\) y\(P(n − 2)\) son verdad. Tenemos\ [\ begin {aligned}
   F_ {n} &=F_ {n-1} +F_ {n-2}\\
   &<2^ {n-1} +2^ {n-2}\\
   &<2^ {n-1} +2^ {n-1}\\
   &=2^ {n}
   \ end {alineado}\]
   (Hipótesis de Inducción)
   así\(P(n)\) es cierto.

Por el Principio de Inducción Matemática (en forma de inducción fuerte con múltiples casos base), concluimos que eso\(P(n)\) es cierto para todos\(n \in \mathbb{N}^{+}\).

Obrar\(8.3.2\).

Hay muchas otras versiones de inducción. Por ejemplo, si deseas demostrar que eso\(P(n)\) es cierto para todos\(n \in \mathbb{N}\) (en lugar de solo para todos\(n \in \mathbb{N}^{+}\)), entonces

1. su caso base sería probar\(P(0)\), y
2. tu paso de inducción sería probar\(P(n-1) \Rightarrow P(n)\), para todos\(n \geq 1\).

Ejemplo\(8.3.3\).

Demostrar\(F_{n} < 2^{n}\), para cada\(n \in \mathbb{N}^{+}\).