¿Cómo escribir la inducción matemática?

Question

La lectura de la literatura acerca de la inducción matemática, he aprendido que hay entre los 4 y los 3 pasos en el razonamiento y la escritura de la prueba. Me dicen que entre 3 y 4 porque en realidad veo que los textos y los autores de las pruebas difieren ligeramente en su explicación y en el estilo en que la prueba está escrito. Esta es mi impresión, al menos.

(1) En general, todos estamos de acuerdo en que el primer componente es la instrucción que queremos demostrar y lo escribimos. (2) a Continuación, se sigue por el caso base, cuando se compruebe la fórmula para n=1, y vemos si la declaración contiene. Hasta el momento, no hay ninguna diferencia entre la prueba de los escritores. (3) Después de esto sigue la asunción, cuando escribimos k = n y decimos que k es un genérico número que appartains a N. Puede ser cualquier número natural. (4) por último, existe el paso inductivo, cuando escribimos n = k+1, y se procede a la manipulación algebraica.

Veo que algunos autores se concentran los pasos (3) y (4) en un único paso y en realidad me gusta más, como no veo la necesidad de escribir un pasaje exactamente el mismo que el anterior, pero con k en lugar de n! Estoy pidiendo su consejo como me gustaría para establecer de una vez por todas mi estilo en la redacción de este tipo de prueba, la agrupación de los pasos (3) y (4) en un lugar único. Sin embargo, desde que me gustaría presentarles verbalmente los pasos, estoy pensando en la manera correcta de introducir la suposición inductiva/paso. ¿Es correcto el siguiente formulario, en su opinión? Supongamos que existe un número general k+1, con k=n, tal que... etc... yo soy, de hecho, no estoy seguro acerca de cómo escribir esta frase, es por eso que pido aquí.

Por favor, hágamelo saber si, dónde y por qué yo estoy equivocado, y también puede que me señale si las palabras que elegir son las adecuadas - por ejemplo, acerca de "general". Por cierto, yo no soy inglés lengua materna del altavoz.

PS. Yo no uso lógico de los símbolos sólo porque no sé cómo editar, pero, obviamente, me gustaría escribir la frase en negrita el uso de conectivos lógicos.

Answer 1

Voy a responder a esta pregunta con four ejemplos típicos, todos diferentes en la naturaleza:

Ejemplo 1:

Demostrar por inducción que $n^3-n+3$ es divisible por $3$ $\forall \space n \in \mathbb{N^+}$.

Para la prueba por inducción; estas son las $\color{red}{\mathrm{three}}$ pasos para llevar a cabo:

Paso 1: Caso Base: Para $n=1 \implies n^3-n+3= 1^3-1+3=3$ que es divisible por $3$. Tal declaración tiene por $n=1$.

Paso 2: Inductivo Asunción: Asumir la afirmación es verdadera para $n=k$ tal que $n^3-n+3=\color{blue}{(k^3-k+3)}=\color{blue}{3p} \tag{1}$ Donde $p,k \in \mathbb{N^+}$.

Paso 3: Probar la Declaración tiene por $n=k+1$ tal que $$n^3-n+3=(k+1)^3-(k+1)+3$$ $$=k^3+3k^2+3k+1-k-1+3=3k^2+3k+\color{blue}{(k^3-k+3)}= 3(k^2+k)+\color{blue}{3p}=\color{#180}{3}(k^2+k+p)$$ using our inductive assumption $(1)$ the resulting expression clearly is divisible by $3$.

Hence $n^3-n+3$ is divisible by $3$ $\forall espacio \n \in \mathbb{N^+}$

QED.

(QED is an abbreviation of the Latin words "Quod Erat Demonstrandum" which loosely translated means "that which was to be demonstrated". It is usually placed at the end of a mathematical proof to indicate that the proof is complete). Alternatively, you can use $\fbox{}$

Example 2:

Use trigonometric identities and induction to prove that

$\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n} = \left(\begin{array}{cc} \cos (n \theta) & -\sin (n\theta)\\ \sin (n \theta) & \cos (n \theta) \end{array} \right)$

As before, for proof by induction; these are the $\color{red}{\mathrm{tres}}$ steps to carry out:

Step 1: Basis Case: For $n=1 \implica$ LHS $=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{1}$

$=\a la izquierda(\begin{array}{cc} \cos (1 \theta) & -\sin (1\theta)\\ \sin (1 \theta) & \cos (1 \theta) \end{array} \right)$

$=\left(\begin{array}{cc} \cos (\theta) & -\sin (\theta)\\ \sin ( \theta) & \cos ( \theta) \end{array} \right)=$ RHS. So statement holds for $n=1$.

Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that

$\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{k}$

$=\left(\begin{array}{cc} \cos (k \theta) & -\sin (k\theta)\\ \sin (k \theta) & \cos (k \theta) \end{array} \right)\etiqueta{1}$

Step 3: Prove Statement holds for $n=k+1$ such that

$\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{n}$

$=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{k+1}$

$=\a la izquierda(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{k}$ $\times \left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)^{1}$

$=\a la izquierda(\begin{array}{cc} \cos (k \theta) & -\sin (k\theta)\\ \sin (k \theta) & \cos (k \theta) \end{array} \right) \times \left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array} \right)$ [el uso de nuestra suposición inductiva $(1)$]

$=\left(\begin{array}{cc} \cos\theta\cos (k \theta)-\sin\theta \sin(k\theta) & -\left(\sin \theta\cos (k \theta)+\sin (k \theta)\cos \theta\right)\\ \cos\theta\sin (k \theta)+\sin\theta \cos(k\theta) & \cos\theta\cos (k \theta)-\sin\theta \sin(k\theta) \end{array} \right)$

$=\color{blue}{\left(\begin{array}{cc} \cos (\theta(k+1)) & -\sin (\theta(k+1))\\ \sin (\theta(k+1)) & \cos(\theta(k+1)) \end{array} \right)}$

Where in the last step I used the fact that $$\cos(A \mp B)=\cos A \cos B \pm \sin A \sin B$$ and $$\sin(A \pm B)=\sin A \cos B \pm \cos A \sin B$$ and $\color{blue}{\mathrm{esta}}$ is the same result if $n=k+1$ es sustituido en el lado derecho de su disposición original. De ahí la afirmación es verdadera para todos los $n \in \mathbb{N}.$

QED.

Ejemplo 3:

Demostrar por inducción que $3^{(3n+4)} + 7^{(2n+1)}$ es divisible por $11$ para todos los números naturales $n$:

Paso 1: Caso Base: para $n=1$: $P(1)= 3^{(3(1)+4)} + 7^{(2(1)+1)} = 2530$, que es divisible por $11$ tal declaración tiene por $n=1$.

Paso 2: Inductivo Asunción: Asumir la afirmación es verdadera para $n=k$: $P(k) =3^{(3k+4)} + 7^{(2k+1)} = 11a \implies 3^{3k+4} = \color{blue}{11a - 7^{2k+1}}$, donde $a \in \mathbb{N}$

Paso 3: Probar la Declaración tiene por $n=k+1$:

$P(k+1)= 3^{3k+7} + 7^{2k+3} = 27 \cdot 3^{3k+4} + 49\cdot 7^{2k+1}\tag{1}$

El uso de la suposición inductiva se muestra en la $\color{blue}{\mathrm{blue}}$, $(1)$ se convierte en:

$27(\color{blue}{11a - 7^{2k+1}})+49\cdot 7^{2k+1}=27\cdot 11a -27\cdot 7^{2k+1}+ 49\cdot 7^{2k+1}=27\cdot 11a +2\cdot 11\cdot 7^{2k+1}=\color{red}{11}(27a+2\cdot 7^{2k+1})$

Por lo tanto $3^{3n+4} + 7^{2n+1}$ es un múltiplo de a $\color{red}{11} \space\forall \space n\in \mathbb{N}$

QED.

Ejemplo 4:

Demostrar por inducción que $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \quad \forall \space n \in \mathbb{N}$$

Step 1: Basis Case: For $yo=1$: $$\sum^{i=k}_{i=1} i^2=\frac{1(1+1)(2\times 1+1)}{6}= \frac{2\times 3}{6}=1$$ So statement holds for $i=1$.

Step 2: Inductive Assumption: Assume statement is true for $i=k$:

$$\sum^{i=k}_{i=1} i^2=\frac{k(k+1)(2k+1)}{6} $$

Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$\sum^{i=k+1}_{i=1} i^2=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}$$

To do this you cannot use: $$\sum^{i=k}_{i=n} i^2=\color{red}{\frac{n(n+1)(2n+1)}{6}} $$ como este es lo que usted está tratando de demostrar.

Entonces, ¿qué puedes hacer en su lugar es un aviso de que: $$\sum^{i=k+1}_{i=1} i^2= \underbrace{\frac{k(k+1)(2k+1)}{6}}_{\text{sum of k terms}} + \underbrace{(k+1)^2}_{\text{(k+1)th term}}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^2}{6}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)\left(k(2k+1)+6(k+1)\right)}{6}$$ $$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)(2k^2+\color{green}{7k}+6)}{6}=\frac{(k+1)(2k^2+\color{green}{4k+3k}+6)}{6}=\frac{(k+1)\left(2k(k+2)+3(k+2)\right)}{6}=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}\quad \forall \space k,n \in \mathbb{N} \quad\fbox{}$$

Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $\color{blue}{\mathrm{blue}}$ equation at the end.

Observe that in the part marked $\color{green}{\mathrm{green}}$ $7k$ has simply been rewritten as $4k+3k$. From then on you simply take out common factors.

Note that this method is only valid when you have two numbers whose product is $12$ and sum is $7$.

Or, put in another way for the general quadratic $ax^2 +bx +c$, this inspection method is only valid iff you can find two numbers whose product is $ca$ and sum is $b$.

Answer 2

He aquí un caso que tiene el paso 1 en...

TEOREMA. Para $n=1,2,3,\cdots$, $$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}<2.$$

PASO 1. Vamos a probar por inducción: $$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\le 2-\frac{1}{n}\tag{1}$$

PASO 2 (caso base), Ya que $1\le 2-\frac{1}{1}$, $(1)$ es cierto para $n=1$.

PASO 3 (hipótesis de inducción) Ahora vamos a $k \ge 1$ y asumir que $(1)$ mantiene para $n=k$. Que es: $$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{k^2}<2-\frac{1}{k}$$

PASO 4 (inducción de paso) Ahora para $n=k+1$: $$ 1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} =1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{k^2}+\frac{1} {k(k+1)^2} . $$ Por la hipótesis de inducción, esto es $$ \le 2 - \frac{1}{k}+\frac{1} {k(k+1)^2} < 2 - \frac{1}{k}+\frac{1} {k(k+1)^2}+\frac{1}{k(k+1)} \\ = 2-\frac{1}{k+1} = 2-\frac{1}{n} . $$ Por lo tanto, $(1)$ mantiene para $n=k+1$.

PASO 5 (conclusión) por lo Tanto, por inducción, $(1)$ mantiene para $n=1,2,3,\dots$. De esto podemos obtener $$ 1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 2. $$ como se requiere.

Answer 3

Todos los ejemplos son excelentes, no creo que pueda aportar nada que no haya sido cubierto. Pero pensé que podría agregar que, para mí, probar el principio de inducción a través del principio de ordenación correcta es lo que realmente me aclaró lo que era suficiente y correcto al probar algo a través de la inducción.