Invertida inducción

Question

Estoy trabajando en una prueba, y para hacerlo, creo que sería óptimo para el uso de la inducción hacia atrás.

Muestran que el 1 no funciona. Suponga que n no funciona. Probar que n+1 no funciona.

Es esto válido?

Answer 1

Lo que está describiendo es todavía una prueba por inducción. Una prueba por inducción es:

• Tomar declaración a $P(n)$ sobre enteros.
• Demostrar $P(1)$
• Demostrar $\forall n:P(n) \implies P(n+1)$

Lo que están haciendo es:

• Tomar declaración a $A(n)$
• Demostrar $\neg A(1)$
• Demostrar $\forall n: \neg A(n)\implies \neg A(n+1)$

Así que lo que están haciendo si simplemente realizar la inducción en la declaración de $\neg A$, es decir, va a realizar estándar de inducción, pero su declaración de $P$ es en realidad una negación de alguna otra instrucción. Es todavía una declaración, por lo que no hay nada realmente "invertida" sucediendo.

Answer 2

De hecho, puede ser visto como "invertida" de la inducción, es decir, como un caso especial de Fermat método de descenso infinito, desde el contrapositivo de su inducción paso es: $\ n$ obras $\,\Rightarrow\, n\!-\!1\,$ obras. Este descenso formulario de inducción es una manera muy natural para presentar muchos inductivo de las pruebas.