¿Se puede utilizar la inducción matemática para refutar algo?

Question

He visto que ésta es la regla de inferencia de la inducción matemática:

Ahora considere :

como L.H.S.

y

como R.H.S. .

Ahora bien, si suponemos que, al tratar de demostrar P(k) -> P(k+1) en el lado izquierdo de la expresión, resulta ser falso para algún caso, entonces todo el lado izquierdo se convierte en falso.

Pero A -> B sólo impone la condición de que siempre que A sea verdadera, B también debe serlo. No hay ningún límite en B cuando A es falso.

Eso significa que aunque mi LHS sea Falso, el RHS podría ser Verdadero!.

Y por lo tanto, la inducción matemática sólo se puede utilizar para demostrar algo, y no para refutar ?

¿Es correcto mi argumento? ¿Si alguien puede arrojar más luz, por favor?

---

Editar:

Lo que quiero decir es esto :

Supongamos que se me ocurre una fórmula para algo y quiero demostrar que esa fórmula es correcta. Aplico la inducción matemática y el LHS resulta ser Falso. ¿Mi fórmula puede seguir siendo correcta, porque no depende de la falsedad de la verdad de LHS cuando la propia LHS es falsa, sólo que la inducción matemática no es capaz de demostrarlo?

Answer 1

(No me queda claro lo que preguntas, y tu pregunta podría aclararse ligeramente).

He aquí un ejemplo para que lo tengas en cuenta, que puede ser relevante para lo que estás pensando.

Supongamos que queremos encontrar cuando $n! \geq 3^n$ .

Ahora, supongamos que es cierto para algunos $k$ . Entonces, si $k + 1 \geq 3$ podemos aplicar la hipótesis de inducción para ver que

$$(k+1)! = (k+1) \times k! \geq (k+1) \times 3^k \geq 3^{k+1}$$

Sin embargo, esto no es cierto para $n=2, 3, 4, 5, 6$ . Pero es cierto para $n=7$ (y después).

Por lo tanto, tenemos un caso en el que
1. P(6) no es verdadera,
2. Si P(6) es verdadera, entonces P(7) es verdadera,
3. P(7) es verdadera.

Answer 2

Voy a responder a la pregunta del cuerpo, que me parece diferente a la respuesta del título.

Si el LHS es falso, entonces $P(0)$ es falso (el caso base falla) o hay un número natural $k$ de manera que la implicación $P(k) \implies P(k+1)$ es falso (el paso de inducción falla.)

Si $P(0)$ es falso, entonces $0$ es un contraejemplo de la afirmación universal $\forall n \, P(n)$ .

Si la implicación $P(k) \implies P(k+1)$ es falso, entonces esto significa que $P(k)$ tiene pero $P(k+1)$ falla. Por lo tanto, el número natural $n = k+1$ es un contraejemplo de la afirmación universal $\forall n \, P(n)$ .

Por lo tanto, en cualquiera de los dos casos la RHS, " $\forall n \, P(n)$ ", falla.

Lo que esto demuestra es que cualquier afirmación universal sobre los números naturales puede demostrarse por inducción. Sin embargo, esto sólo es cierto en un sentido trivial: podría ser que probar la implicación $P(k) \implies P(k+1)$ en general $k$ no es más fácil que demostrar la conclusión $P(k+1)$ en general $k$ .