3.9: Inducción Fuerte

Hay ocasiones en las que el Principio de Inducción Matemática, al menos tal como lo hemos estudiado hasta este punto, no parece suficiente. Aquí hay un ejemplo concreto. El profesor le pidió a Bob que estudiara una función\(f(n)\) definida recursivamente por\(f(n) = 2f(n-1) - f(n-2)\) con\(f(1) = 3\) y\(f(2) = 5\). Específicamente, el profesor le pidió a Bob que computara\(f(10^{10})\), lo que parece una tarea desalentadora. Sobre el café, Bob garabateó en una servilleta\(f(3)=7\) y determinó eso y\(f(4)=9\), y solo con base en estos cálculos, pensó que podría ser simplemente posible eso\(f(n)=2n+1\) para todos\(n \geq 1\). Si esto fuera cierto, simplemente podría reportarlo\(f(10^{10})=2 \cdot 10^{10}+1=20000000001\).

Bob empezaba a entender las pruebas por inducción, así que trató de probarlo\(f(n)=2n+1\) para todos\(n \geq 1\) por inducción. Para el escalón base, señaló que\(f(1)=3=2 \cdot 1+1\), así que todo está bien a este punto. Para el paso inductivo, asumió eso\(f(k)=2k+1\) para algunos\(k \geq 1\) y luego trató de demostrarlo\(f(k+1)=2(k+1)+1\). Si se pudiera completar este paso, entonces se haría la prueba por inducción.

Pero en este punto, Bob parecía chocar contra una barrera, porque

\(f(k+1) = 2f(k) - f(k-1) = 2(2k+1) - f(k-1)\),

utilizando la hipótesis inductiva para reemplazar\(f(k)\) por\(2k+1\). Sin embargo, él estaba totalmente perplejo sobre qué hacer con el\(f(k−1)\). Si lo supiera\(f(k−1)=2(k−1)+1\), entonces resultaría el lado derecho\(2(2k+1)−(2k−1)=2k+3=2(k+1)+1\), que es exactamente lo que quiere. Bob siempre juega según las reglas, y tiene que admitir que no lo sabe\(f(k−1)=2(k−1)+1\). Eso sólo lo sabe\(f(k) = 2k+1\).

Bob estaba a punto de tirar la toalla y pedirle a su computadora que comenzara a hacer los cálculos recursivamente, cuando Carlos venga y le pregunte qué está haciendo. Carlos ve de inmediato que el enfoque que estaba tomando Bob para demostrar que\(f(n)=2n+1\) por inducción no va a funcionar, pero después de un momento de reflexión, Carlos dice que hay una forma más fuerte de una prueba inductiva que hará el truco. Carlos le explicó pacientemente a Bob una proposición que se llama el Fuerte Principio de Inducción Matemática. Para probar que una declaración abierta\(S_n\) es válida para todos\(n \geq 1\), basta con

a) Demostrar que\(S_1\) es válido, y

b) Mostrar que\(S_{k+1}\) es válido siempre que\(S_m\) sea válido para todos los enteros\(m\) con\(1 \leq m \leq k\).

La validez de esta proposición es trivial ya que es más fuerte que el principio de inducción. Lo novedoso aquí es que para probar una afirmación, a veces es a su favor demostrar algo aún más fuerte. Los matemáticos combinatorios llaman a esto el fenómeno “bootstrap”.

Equipado con esta observación, Bob vio claramente que el fuerte principio de inducción era suficiente para demostrarlo\(f(n)=2n+1\) para todos\(n \geq 1\). Para que pudiera apagar su computadora y disfrutar de su café.