Prueba de derivación de Fibonacci

¿Se puede hacer esto con inducción?

Puede. Más específicamente, se puede hacer con una fuerte inducción sobre dos variables. Primero sugiero mirar https://math.stackexchange.com/a/7665/146030 y pensar por qué, en ambos casos, las primeras tres declaraciones implican la cuarta.

Probaremos la afirmación de que

Para empezar definimos la sucesión de fibonacci como

Cuando$n=0$y$m=0$entonces

y entonces la proposición es verdadera cuando$n=m=0$.

Para probar que el enunciado es verdadero para todos los no negativos$n,m$, primero inducimos en$n=k$por un fijo$m$. Suponga que el enunciado es verdadero para todos$0\leq k\leq n$. Probamos ahora el enunciado para$k+1$.

Y así, por inducción matemática, la afirmación es verdadera para todos$n$y eso fijo$m$. Podemos ver que una prueba inductiva similar funciona para un fijo$n$y$m=k$. Por lo tanto, podemos concluir que la afirmación es verdadera.

Me temo que esta afirmación es imposible de probar porque es incorrecta. De hecho, esto se puede ver con$n=1, m=0$:

En cuanto a la inducción de Trevor Fancher, es completamente correcta excepto que su paso básico está incompleto.

(Me referiré a la declaración como$P(n,m)$). De hecho, lo que hace es probar que para un p fijo,$P(n,p)$y$P(n+1,p)$verdadero$\Rightarrow P(n+2,p)$verdadero$\forall n \in \mathbb{N}$. Por simetría también prueba que para un p fijo,$P(p,m)$y$P(p,m+1) \Rightarrow P(p,m+2)$ $\forall m \in \mathbb{N}$. Entonces para concluir la prueba lo que hacemos es:

1. $P(0,0)$verdadero + P(1,0) verdadero + Inducción en n$\Rightarrow P(n,0)$verdadero$\forall n$
2. $P(0,1)$verdadero + P(1,1) verdadero + Inducción en n$\Rightarrow P(n,1)$verdadero$\forall n$
3. $P(n,0)$verdadero + P(n,1) verdadero + Inducción en m$\Rightarrow P(n,m)$verdadero$\forall n, m$

Pero en esta prueba solo vemos que$P(0,0)$es cierto, no$P(0,1)$,$P(1,0)$ni$P(1,1)$por lo tanto, esta prueba es incorrecta ya que son necesarios para concluir la prueba (y por lo tanto para que la inducción sea válida).

Creo que la verdadera declaración similar que buscabas probar es

Su proposición no es verdadera (como se puede ver por$P(0,1) : f_{0+1+2} ≠ f_{0+1}f_{1+1} + f_{0}f_{1}$). Faltan algunos elementos para construir una prueba de este tipo de manera rigurosa: usa ambos rangos$𝑘−1$y$𝑘$. Luego, su paso inductivo se basa en dos rangos consecutivos, lo que significa que queremos usar esto para nuestra inducción:$P(k,n) \land P(k+1,n)\implies P(k+2,n)$. Viene que tienes que demostrar$P(0,n)\implies P(1,n)$: lo cual es falso. Se debería haber probado que la proposición se cumple para$P(0,0), P(0,1), P(1, 0), P(1,1)$poder utilizar 2 rangos consecutivos en la inducción. La proposición correcta es más bien$f_{m+n+1}$=$f_{m+1}f_{n+1} + f_mf_n$ $(Analysis II w/ Anna) > All$