7.3: Forma fuerte de inducción matemática
- Page ID
- 118361
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Supongamos que\(P(n)\) es un predicado donde la variable\(n\) tiene dominio el positivo, números enteros. Si
\(P(1)\)es verdad, y
\((\forall k)( (P(1) \land P(2) \land \cdots \land P(k)) \rightarrow P(k+1))\)es verdad,
entonces\((\forall n)P(n)\) es cierto.
La idea aquí es la misma que para la inducción matemática regular. No obstante, en la forma fuerte, nos permitimos más que el caso inmediatamente anterior para justificar el caso actual.
Si el primer caso\(P(1)\) es cierto, y\(P(1) \rightarrow P(2)\text{,}\) entonces\(P(2)\) debe ser cierto también. Ahora bien, si\(P(1) \land P(2) \rightarrow P(3)\text{,}\) y ya tenemos\(P(1)\) y\(P(2)\) ambos son verdaderos, entonces\(P(3)\) debe ser cierto también. Además, si\(P(1) \land P(2) \land P(3) \rightarrow P(4)\text{,}\) y ya lo tenemos\(P(1)\text{,}\)\(P(2)\text{,}\) y\(P(3)\) todo es cierto, entonces\(P(4)\) debe ser cierto también. Y así sucesivamente, hasta que hayamos alcanzado\(P(n)\text{,}\) el\(n\) valor que deseemos.
Estuche base.
Comience por probar la declaración para el caso base\(n = 1\text{.}\)
Paso de inducción.
A continuación, supongamos que\(k\) es un número fijo tal que\(k \ge 1\text{,}\) y que la afirmación es cierta para todos\(n \le k\text{.}\) Con base en esta suposición, tratar de probar que el siguiente caso, también\(n=k+1\text{,}\) es cierto.
Demostrar que cada número entero mayor que\(1\) puede ser factorizado en un producto de (uno o más) primos.
Solución
Estuche base.
El primer número mayor que\(1\) es\(n = 2\text{,}\) y es primo. Por lo que puede considerarse un producto de un prime.
- Nota
-
Nuestro caso base está en\(n = 2\) porque nuestra declaración original solo se refiere a números mayores que\(1\text{.}\)
Paso de inducción.
Dejar\(k\) representar un número entero que es mayor que\(1\text{.}\) Supongamos que cada uno\(2,3,4,\ldots ,k\) puede ser factorizado en primos. Queremos mostrar también se\(k + 1\) puede factorizar en primos.
Romper en casos.
Caso\(k + 1\) prime.
En este caso ya\(k+1\) es un producto de un solo prime, en sí mismo.
Caso\(k + 1\) no primo.
Si no\(k + 1\) es primo, entonces tiene divisores no triviales. Entonces existen enteros\(m_1,m_2\text{,}\) con\(2\le m_1, m_2 \le k\text{,}\) tal que\(k+1 = m_1 m_2\text{.}\) Por nuestra hipótesis de inducción, cada uno de\(m_1,m_2\) puede ser factorizado en un producto de primos, por lo que su producto también\(k+1\) puede.
Si tu prueba del paso de inducción requiere saber que un número muy específico de casos previos son ciertos, es posible que necesites usar una variante de la forma fuerte de inducción matemática donde primero se prueben varios casos base. Por ejemplo, si, en el paso de inducción, demostrar que eso\(P(k+1)\) es cierto se basa específicamente en saber que ambos\(P(k-1)\) y\(P(k)\) son ciertos, entonces este argumento no prueba eso\(P(1)\rightarrow P(2)\text{,}\) y por lo tanto debes probar tanto casos base de\(P(1)\) como\(P(2)\) explícitamente.