Probablemente la pregunta que debe plantearse es si el resultado puede ser obtenido a partir de cero sin saber de ti! A menudo, muchos libros de texto o los problemas de la tarea pida a los estudiantes que el uso de la inducción para demostrar algún teorema, pero el estudiante no podrían venir con el teorema en el primer lugar. Este tipo de problemas no es bueno. Por ejemplo, en lugar de pedir una forma cerrada para $\sum_{k=1}^n k^2 2^k$ (usando sólo la aritmética y la exponenciación), dan la respuesta y solicitar una prueba por inducción, que es casi totalmente inútil.
Uno puede ver una clara distinción entre las pruebas por inducción, donde la hipótesis de "caídas del cielo" y de las pruebas que, naturalmente, se llega a la conclusión de que por otros medios. A pesar del hecho de que todas las pruebas deben utilizar la inducción en el nivel formal, se sienten más naturales, cuando no es extraño e inexplicable cancelación de los términos que se produce cuando se comprueba la respuesta correcta por inducción.
Como t.b. comentó, en una combinatoria general, prefieren bijective pruebas, básicamente, por esta razón; nada se cancela y hay una clara correspondencia directa entre uno y otro. Del mismo modo, es mejor mostrar cómo resolver una relación de recurrencia por un método general de que el estado de la solución y demostrarlo por inducción.
Estas consideraciones, y de las cancelaciones en las pruebas se producen en otras formas además de la utilización de la inducción. En geometría se prefiere una síntesis de la solución (el uso argumentos geométricos) en lugar de una solución analítica (mediante el uso de ecuaciones a través de una real-campo cerrado), simplemente porque en una analítica de soluciones normalmente hay inexplicable cancelación de los factores a lo largo de la manera que nunca aparecen en un puramente sintético de la prueba. Algunos incluso evitar la trigonometría por la misma razón, pero algunos teoremas son mucho más agradable cuando se expresa en la trigonometría.
La cantidad de redundancia en una prueba, correspondientes a los desvíos innecesarios en el resultado después de la cancelación puede ser algo cuantificados en la geometría Euclidiana por el total de grado de las funciones racionales que intervienen. En la zona más elegante sintético solución de una casi siempre trata lineal o cuadrática expresiones y no hay innecesarios cancelaciones, pero en una analítica de la solución de cada círculo de intersección de dobles en el grado dos. De hecho, esta es la razón por la automatizados teorema de provers todavía no puede manejar complicados teoremas geométricos que razonablemente corto sintético de pruebas, debido a que los seres humanos pueden construir nuevos puntos de enlace existentes en una forma sencilla que evita la posterior cancelación.
En la lógica que tiene el corte de la eliminación teorema de sequent de cálculo, que es un poco como decir que siempre hay una prueba directa de que no se utilice cualquier idea nueva que no está ya contenida en el teorema de ser probada. Sin embargo, como se ha demostrado por George Boolos, no permitiendo indirectos tales pruebas (mediante corte) puede obligar a la longitud mínima de la prueba a ser mucho mayor que de lo contrario. Así que si vamos por la prueba de longitud para comparar pruebas que puede necesitar un poco de "cancelación".
Por lo tanto, existe un trade-off entre la prueba de longitud y poder explicativo. En el ejemplo empecé con, la más corta de la prueba será probablemente por inducción! Pero el que más satisfacciones le mostrará cómo resolver este tipo de problemas en general, a través de la anti-operador diferencia y anti-diferencia por partes. Es muy claro que aquí una visión estructural es más importante que un corto de prueba, ya que los 'nuevas ideas' presentado no acaba de solucionar este problema, pero toda una clase de problemas. Además, estos permiten encontrar la forma cerrada sin saberlo. Esto recuerda a la de la distinción entre P y NP, donde un problema en NP tiene una solución que puede ser verificado en el polinomio tiempo, exactamente como la mayoría de los libros de texto de la inducción de los problemas pueden ser verificados en forma rutinaria, pero un problema en P tiene una solución que puede ser encontrado en el polinomio de tiempo.
De todos modos estos son sólo mis opiniones, ya que yo también he pensado mucho acerca de este tipo de problema con la inducción. Algunos casos de inducción son tan naturales que las personas no se dan cuenta de ello y a veces insisten en que no hay inducción, como siempre que se use un signo de suma. Otras veces la inducción se siente como la herramienta equivocada. Un simple ejemplo es el apretón de manos-lema de la teoría de grafos, donde hay una inducción de la prueba que se siente como que no explica nada, y la doble contabilización, la prueba de que lo explica todo. Muchos de los estudiantes afirman que el último no hace uso de la inducción, pero formalmente no!
