Inducción - ejemplos donde el paso de la inducción es correcto pero el caso base siempre es malo

Question

Me gustaría presentar a mis alumnos algunos ejemplos de inducción que siempre satisfacen el paso inductivo pero nunca el caso base. Es posible para números naturales, gráficos o cualquier otra cosa.

Answer 1

Algunos ejemplos sencillos:

• $2.5 + k$ es un número natural para todos los $k \in \mathbb N$

• $\int_1^{\infty} \frac{1}{xn} dx<\infty$ todos los $n\in \mathbb N$

• $\mathbb R^{2^n}$ es contable para todos los $n\in \mathbb N$

• 7 divide $10^n$

---

El siguiente ejemplo también podría ser interesante para usted:

Se trata de un ejemplo donde la inducción paso va mal.

Declaración: Todos los caballos tienen el mismo color

1) caso Base: Esto es obviamente cierto

2) la Inducción paso: vamos a considerar $(n+1)$ caballos. Si queremos eliminar un caballo, entonces la hipótesis de inducción nos dice que el resto de los $n$ caballos tienen el mismo color. Ahora ponemos el caballo y quitar otro. Aplicando la hipótesis de inducción, una vez más los rendimientos que todos los $(n+1)$ caballos tienen el mismo color. Sin embargo, esta argumentación no funciona para $n=1$ $n=2$porque necesitamos un caballo que se "conecta" los dos caballos.

Answer 2

Permítanme ampliar razón por la que hice el comentario a tu pregunta (y voy a seguir este con (1) lo que yo creo que es un significativo ejemplo a su pregunta y (2) un ejemplo de un sutil error en una inducción de la prueba).

---

Motivo de comentario: Observe que cualquier declaración que nunca es la verdadera voluntad de satisfacer las condiciones para un ejemplo. Es decir, tendríamos la siguiente de algunos declaración de $P(n)$:

• Caso Base: $P(m)$ es falso. [Este es claramente el caso, ya que hemos elegido una declaración de $P(n)$ que es falsa para todos los de $n$.]
• Inductivo paso: $P(n)\to P(n+1)$ siempre es cierto, porque la $P(n)$ es siempre falso. [Esto es debido a que una implicación sólo es falsa cuando la hipótesis es verdadera y la conclusión es falsa.]

Pueden ver ahora por qué me dijo que tales ejemplos son propensos a ser de poco valor?

---

Ejemplo para tu pregunta: El más significativo (esto es ciertamente una horridly término subjetivo) ejemplo de lo que podía pensar fuera de la parte superior de mi cabeza, era la siguiente, donde $P(n)$ indica la siguiente instrucción para todos los $n\in\mathbb{N}$: $$ P(n) : \text {$n$th el primer número es impar.} $$ Bueno, el caso base $P(1)$ es claramente falso (el primer número primo, $2$, no es impar). Casi todas las implicaciones de la forma $P(n)\to P(n+1)$ son verdaderas y no en un vacío manera (es decir, la única vacuo implicación va a ser al $P(1)\to P(2)$).

---

Sutilmente defectuosa de la inducción de la prueba: Tratar de encontrar el error en la siguiente "prueba" de que el $a^n=1$ para todos los números enteros no negativos $n$, siempre que $a$ es un número real distinto de cero.

Caso Base: $a^0=1$ es verdadero por la definición de $a^0$.

Inductivo paso: Supongamos que $a^m=1$ para todos los números enteros no negativos $m$$m\leq k$. A continuación, observe que $$ a^{k+1}=\frac{a^k\cdot a^k}{a^{k-1}}=\frac{1\cdot 1}{1}=1. $$ Se puede detectar la falla? Si no, aquí está (pase el cursor sobre el gris de la zona para revelar respuesta):

La falla se produce en el paso inductivo donde nos supone implícitamente que $n\geq 1$ para que podamos hablar de $a^{n-1}$ en el denominador; de lo contrario, el exponente no es un entero no negativo, lo que significa que no se puede aplicar la hipótesis inductiva. Hemos comprobado en el caso base sólo para $n=0$; por lo tanto, no somos justificados en el supuesto de que $n\geq 1$ cuando tratamos de demostrar a la declaración de la $n+1$ en el paso inductivo. Es exactamente en $n=1$ que la proposición se rompe.

Answer 3

Todos los números naturales son mayores que 1.

es extraño para cualquier número natural $2+4+6+8+\cdots+2n$ $n$.

$n(n+1)$ es siempre impar.

Answer 4

Así que tenemos una declaración falsa de algún tipo. Un ejemplo sencillo podría ser una "prueba" de que el $\mathbb{N}=\{1\}$. Si $n=n-1$,$n+1=n-1+1=n$. Pero, por supuesto, no hay ninguna base de caso de uso aquí.

Si quieres hablar de los gráficos, se podría decir algo como, un árbol de $T$ $n$ vértices ha $n$ bordes. Supongamos que usted tiene un árbol de $T$. Encontrar una hoja, eliminar a obtener un árbol en $n-1$ vértices (y por lo $n-1$ bordes). Por lo tanto $T$ $n$ bordes.

Usted puede utilizar el "show" que para cada plano gráfico con $v$ vértices, $e$ bordes y $f$ caras, una de ellas ha $v-e+f=1$. Supongamos que esto es cierto para todos los grafos planares con menos de $e$ bordes. Si $G$ es un árbol, a continuación, $G$ tiene una cara y por lo $v-e+f= n-n+1=1$.

Si $G$ tiene un ciclo, quitar un borde de ella. A continuación, el gráfico resultante tiene uno menos borde y uno menos cara, por lo $v-(e-1)+(f-1)=1$$v+e-f=1$.

Answer 5

por ejemplo $n(n+1)$ es siempre impar... Si usted asume $k(k+1)$ es impar entonces $(k+1)(k+2)=k(k+1)+2(k+1)$ pero impar + incluso = impar por inducción es verdad... pero para $n=1$ no es cierto...