¿Por qué ' t esta inducción "prueba"Mostrar $f_n = (\phi)^n + (1-\phi)^n$?

Question

Aquí,$\phi$ es la proporción áurea y$f_n$ es el número de$n^{th}$ de Fibonacci. La fórmula que estoy usando es en realidad la forma cerrada de los números de Lucas.

Dejar $n = 1$. Entonces y $f_n = 1$. Por lo tanto, el caso se mantiene donde$\phi + 1 - \phi = 1$, estableciendo nuestro caso base.

Supongamos que el caso se cumple para todos los números naturales inferiores o iguales a$n = 1$. Entonces $k$. Por lo tanto, el caso se mantiene donde$f_{n+1} = f_n + f_{n-1} = \phi^k + (1-\phi)^k + \phi^{k-1} + (1-\phi)^{k-1} = \phi^{k-1}(1 + \phi) + (1-\phi)^{k-1}(2-\phi) = \phi^{k-1}\phi^2 + (1 - \phi)^{k-1}(1-\phi)^2 = \phi^{k+1} + (1-\phi)^{k+1}$. Por inducción matemática, la afirmación es válida para todos$n = k+1$.

Sin embargo,$n \in N$ y$f_3 =2$. ¿Por qué es esto?

Answer 1

Su inductivo paso es la verificación de que $\rm\:g_n = \phi^n + (1-\phi)^n\:$ también satsifies la de fibonacci de la recurrencia de la $\rm\:f_{n+2} = f_{n+1}\! + f_{n}.\,$ Las soluciones de tales lineal de segundo orden homogénea ecuaciones de diferencia está únicamente determinado por los valores iniciales $\rm\,f_0, f_1,\:$ como un trivial inductivo prueba de muestra. Sin embargo, su "caso base" solo verifica que están de acuerdo para $\rm\:n = 1.\:$ Pero no están de acuerdo para $\rm\:n = 0\:$ desde $\rm\:f_0 = 0\:$ pero $\rm\:g_0 = \phi^0 + (1-\phi)^0 = 2.\:$ Estas condiciones iniciales definir los números de Lucas.

Entonces, ¿por qué la prueba de fallar? Si usted examina la prueba del paso inductivo para $\rm\:n = 1\:$ tenga en cuenta que, para deducir la verdad de la identidad de $\rm\:n = 2,\:$ emplea a la verdad en $\rm\;n = 1\:$ $\rm\:n = 0.\:$ sin Embargo, nunca se demostró que es cierto para $\rm\:n = 0;\:$, de hecho, como vimos, no es: $\rm\:f_0\ne g_0.$

Answer 2

Tenga en cuenta que ha definido$f_{n+1}=f_{n}+f_{n-1}$, por lo que para utilizar la inducción, debe saber que se cumple para los dos casos anteriores, en lugar de solo para el anterior. Eso significa que$n=0$ también es parte del caso base, pero$\phi^{0}+(1-\phi)^{0}=2$, que no es lo mismo que$f_{0}$.

Answer 3

Voy a intentar explicar la sutileza que he notado desde un ángulo diferente. Para referencia, estoy reimpresión de su argumento aquí, nombrando a la proposición $P(n) : F_n = \phi^n+(1-\phi)^n$.

Deje $n = 1$. A continuación,$F_n = 1$$\phi + 1 - \phi = 1$. Por lo tanto, la proposición $P(1)$ mantiene, estableciendo nuestro caso base.

Tan lejos, tan bueno.

Suponga que $P(k)$ tiene para todos los números naturales $k\leq n$. A continuación,$F_{n+1} = F_n + F_{n-1} = \phi^n + (1-\phi)^n + \phi^{n-1} + (1-\phi)^{n-1} = \phi^{n-1}(1 + \phi) + (1-\phi)^{n-1}(2-\phi) = \phi^{n-1}\phi^2 + (1 - \phi)^{n-1}(1-\phi)^2 = \phi^{n+1} + (1-\phi)^{n+1}$. Por lo tanto $P(n+1)$ mantiene. Por inducción matemática, tenemos $P(n)$ todos los $n \in N$.

Este usa$P(n)$$P(n-1)$, que en la superficie se ve bien - pero tenga en cuenta que esto requiere tanto $P(n)$ $P(n-1)$ explícitamente. La falsa declaración de que usted está confiando en la declaración '$(\forall k\leq n P(k)) \implies (P(n) \wedge P(n-1))$', porque esta declaración está mal definida al $n=1$ (suponiendo que el "caso base" es $n=1$, por supuesto, y por lo tanto $P(0)$ es técnicamente indefinido.) Esto significa que usted en realidad no ha mostrado $\forall n \bigl(\left(\forall k\leq n P(k)\right)\implies P(n+1)\bigr)$, que es lo que necesita para su inducción al trabajo.

Esto explicaría por qué prácticamente todos los de Fibonacci pruebas necesitan dos 'de la base de casos": porque generalmente se utiliza el principio de inducción $P(n-1)\wedge P(n)\implies P(n+1)$, que necesitan tanto $n=1$ $n=2$ 'los casos de base' para obtener todo el problema con la definición de $P(0)$ (o, alternativamente, $n=0$ $n=1$ base de los casos).