¿Cómo se escribe una función recursiva de forma que sea fácil compararla con otra mientras se hace una prueba por inducción?

Question

¿Cómo escribirías la siguiente función recursiva de tal manera que sea fácil compararla con otra al hacer una prueba por inducción?

Caso base: $F(0) = 0; F(1) = 1$ .

Paso recursivo: $ F(n) = F(n - 1) + F(n - 2)$ para todos $n \geq 2$

Me quedo atascado cuando tienes que mostrar que $f(k+1) \leq g(k+1)$ donde $g(n)$ es alguna función arbitraria, en este caso cómo definiría $f(k+1)$ para compararlo?

¿Y si $g(x) = (\frac{1+\sqrt{5}}{2})^{n-1}$ como ejemplo?

Answer 1

Dejemos que $\varphi=\frac12\left(1+\sqrt5\right)$ . Entonces tienes $g(n)=\varphi^{n-1}$ . Ahora bien, tenga en cuenta que $\varphi$ es una de las soluciones de la ecuación cuadrática $x^2-x-1=0$ : sólo hay que comprobar la fórmula cuadrática. Así, $\varphi^2=\varphi+1$ y por lo tanto

$$g(n)=\varphi^{n-1}=\varphi^{n-3}\varphi^2=\varphi^{n-3}(\varphi+1)=\varphi^{n-2}+\varphi^{n-3}=g(n-1)+g(n-2)$$

para $n\ge 2$ . En otras palabras, $g$ satisface la misma recurrencia que los números de Fibonacci, y una prueba por inducción es muy sencilla: si $F_{n-1}\le g(n-1)$ y $F_{n-2}\le g(n-2)$ , entonces automáticamente $$F_n=F_{n-1}+F_{n-2}\le g(n-1)+g(n-2)=g(n)\;.$$

Esta es la mejor configuración posible para una prueba por inducción: las dos secuencias satisfacen la misma recurrencia.