Prueba de inducción con números de Fibonacci

Question

Prueba de inducción con números de Fibonacci

inducción
Matemáticas
redacción de pruebas
números de fibonacci

JZ555

Demuestre por inducción que para los números de Fibonacci de algún índice $i > 10$

$1.5^i ≤ f_i ≤ 2^i$

¡Aviso! Debido a que el número de Fibonacci es una suma de 2 números de Fibonacci anteriores, en la hipótesis de inducción debemos asumir que la expresión se cumple para k+1 (y en ese caso también para k) y en base a esto demostrar que también se cumple para k+ 2.

Esto es lo que tengo hasta ahora:

Caso base: $i = 11$
$f_{11} = 89$
$1.5^{11} ≤ 89 ≤ 2^{11}$ ¡DE ACUERDO!

Hipótesis de inducción:
$1.5^{k+1} ≤ f_{k+1} ≤ 2^{k+1}$

Paso de inducción:
$1.5^{k+2} ≤ f_{k+2} ≤ 2^{k+2}$

Ahora no tengo idea de cómo continuar desde aquí. ¿Alguien podría ayudar?

Respuestas (3)

Prueba de inducción con números de Fibonacci

Hagen von Eitzen · Answer 1

Si $\alpha^k\le f_k\le \beta^k$ y $\alpha^{k+1}\le f_{k+1}\le \beta^k$ , entonces

F_{k + 2} = F_{k} + F_{k + 1} \geq α^{k} + α^{k + 1} = α^{k + 2} \cdot (\frac{1}{α^{2}} + \frac{1}{α})

$f_{k+2}=f_k+f_{k+1}\ge \alpha^k+\alpha^{k+1}=\alpha^{k+2}\cdot(\frac1{\alpha^2}+\frac1\alpha)$ y

F_{k + 2} = F_{k} + F_{k + 1} \leq β^{k} + β^{k + 1} = β^{k + 2} \cdot (\frac{1}{β^{2}} + \frac{1}{β}),

$f_{k+2}=f_k+f_{k+1}\le \beta^k+\beta^{k+1}=\beta^{k+2}\cdot(\frac1{\beta^2}+\frac1\beta),$ así que para concluir

α^{k + 2} \leq F_{k + 2} \leq β^{k + 2}

$\alpha^{k+2}\le f_{k+2}\le \beta^{k+2}$ es suficiente tener

\frac{1}{α^{2}} + \frac{1}{α} \geq 1

$\frac1{\alpha^2}+\frac1\alpha\ge 1$ y

\frac{1}{β^{2}} + \frac{1}{β} \leq 1

$\frac1{\beta^2}+\frac1\beta\le 1$ . Puede verificar que esto es cierto para

α = \frac{3}{2}

$\alpha=\frac32$ y

β = 2

$\beta=2$ .

cameron buie · Answer 2

Cuando se trata de resultados de inducción sobre números de Fibonacci, normalmente necesitaremos dos casos base y dos hipótesis de inducción, como lo insinuó su problema.

Olvidó verificar su segundo caso base: $1.5^{12}\le 144\le 2^{12}$

Ahora, para su paso de inducción, debe asumir que $1.5^k\le f_k\le 2^k$ y eso $1.5^{k+1}\le f_{k+1}\le 2^{k+1}.$ Inmediatamente podemos ver, entonces, que

F_{k + 2} = F_{k} + F_{k + 1} \leq 2^{k} + F_{k + 1} \leq 2^{k} + 2^{k + 1} = 2^{k} (1 + 2) \leq 2^{k} \cdot 4 = 2^{k + 2}

$f_{k+2}=f_k+f_{k+1}\le 2^k+f_{k+1}\le 2^k+2^{k+1}= 2^k(1+2)\le 2^k\cdot 4=2^{k+2}$ En cuanto a la otra desigualdad, vemos de manera similar que

F_{k + 2} = F_{k} + F_{k + 1} \geq {1.5}^{k} + {1.5}^{k + 1} = {1.5}^{k} (1 + 1.5) = {1.5}^{k} \cdot 2.5 \geq {1.5}^{k} \cdot 2.25 = {1.5}^{k + 2}

$f_{k+2}=f_k+f_{k+1}\ge 1.5^k+1.5^{k+1}=1.5^k(1+1.5)=1.5^k\cdot 2.5\ge1.5^k\cdot 2.25=1.5^{k+2}$

G. Khanna · Answer 3

Este problema/prueba plantea una pregunta interesante: mostrar que, en algún momento, el crecimiento de los números de Fibonacci está limitado por dos funciones exponenciales: $1.5^i$ desde abajo y $2^i$ desde arriba. De inmediato, sabemos que la proporción de números de Fibonacci secuenciales se aproxima a la Proporción Áurea = 1,618..., por lo que sabemos que las funciones de límite superior e inferior encuadrarán el crecimiento de los números de Fibonacci.

Otra forma de ver la respuesta que proporcionó @Hagen von Eitzen es la siguiente. Ambos $\frac{1}{\alpha^2} + \frac{1}{\alpha} = 1$ y $\frac{1}{\beta^2} + \frac{1}{\beta} = 1$ conducen a la misma expresión polinomial de la forma: $x^2 - x - 1 = 0$ . Una de las soluciones a esta expresión es $x = 1.61803...$ que es la proporción áurea. El polinomio y sus raíces se muestran en la figura siguiente.

Para la expresión con $\alpha$ , necesitas $\frac{1}{\alpha^2} + \frac{1}{\alpha} \geq 1$ , lo que lleva a $0 \geq \alpha^2 - \alpha - 1$ . Las soluciones (positivas) para $\alpha$ será menor que 1.618..., y $\alpha = 1.5$ trabajará.

Para la expresión con $\beta$ , necesitas $\frac{1}{\beta^2} + \frac{1}{\beta} \leq 1$ , lo que lleva a $0 \leq \beta^2 - \beta - 1$ . Las soluciones para $\beta$ será mayor que 1.618..., y $\beta = 2$ trabajará.

Su respuesta no agrega nada nuevo a las respuestas ya existentes.
@JoséCarlosSantos - Discrepo respetuosamente. Estaba agregando a la muy buena respuesta de Hagen y simplemente estaba tratando de afirmar que la proporción áurea es en realidad el límite para $\alpha$ y $\beta$ . Las funciones exponenciales donde la base es menor que la proporción áurea serían el límite inferior y las funciones donde la base es mayor que la proporción áurea serían el límite superior. Lamento que piense que esto no agrega valor; quizás para usted no lo sea, pero puede que lo sea para otros. Además, si no agrega valor, nadie en la comunidad lo votará. Déjalo ser. ¡Disfruté respondiéndola!

Prueba de inducción con números de Fibonacci

JZ555

Respuestas (3)

Hagen von Eitzen

cameron buie

JZ555

G. Khanna

jose carlos santos

G. Khanna

Prueba inductiva de codificación de Fibonacci

Demostrar el número de adiciones del algoritmo del número de Fibonacci

Explicando la prueba del número de Fibonacci usando razonamiento inductivo

Demostración por inducción sobre los números de Fibonacci: demuestre que fn∣f2nfn∣f2nf_n\mid f_{2n}

Pregunta sobre una prueba de inducción de (Principio de inducción matemática, Capítulo 4 en el libro de texto NCERT)

Prueba de derivación de Fibonacci

Probar que f2+f4+⋯+f2n=f2n+1−1f2+f4+⋯+f2n=f2n+1−1f_2+f_4+\cdots+f_{2n}=f_{2n+1}-1 para números de Fibonacci por inducción

Coloración de gráficos -- Número cromático e inducción

Ayuda sobre cómo preparar el paso inductivo de un ejercicio de inducción fuerte.

Prueba por inducción de que si n∈Nn∈Nn \in \mathbb N entonces se puede escribir como la suma de diferentes números de Fibonacci [duplicado]