Princípio de Indução Finita

Se alguém puder resolver esse problema por indução, eu agradeço.
Seja [latex]F_1=F_2=1[/latex] e [latex]F_n=F_{n-1}+F_{n-2},n\geq 3[/latex], a sequência de Fibonacci. Mostre que [latex]F_n< \left (\frac{7}{4} \right )^n[/latex].


Eu resolvi de uma maneira, mas não sei se está correta.

Casos iniciais:

[latex]F_1 = 1 < (7/4) [/latex] ok

[latex]F_2 = 1 < (7/4)^2 [/latex] ok

[latex] F_3 = 2 < (7/4)^3 [/latex] ok

[latex]F_4 = 3 < (7/4)^4 [/latex] ok


Conjectura: [latex] F_n < (7/4)^n \: \forall \, \: \: k \leq n,\:\: k\: \:  \epsilon \: \mathbb{N}  [/latex]

Da hipótese [latex] F_{n-1} < (7/4)^{n-1} [/latex],

Então 

[latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex]

[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]

 [latex]F_{n+1} < (7/4)^{n-1} \times 11/4 <  (7/4)^{n-1}*49/16 [/latex]

[latex]F_{n+1} < (7/4)^{n+1} [/latex]

Está provado, por indução forte.

Vitor Ahcor escreveu:Casos iniciais:

[latex]F_1 = 1 < (7/4) [/latex] ok

[latex]F_2 = 1 < (7/4)^2 [/latex] ok

[latex] F_3 = 2 < (7/4)^3 [/latex] ok

[latex]F_4 = 3 < (7/4)^4 [/latex] ok


Conjectura: [latex] F_n < (7/4)^n \: \forall \, \: \: k \leq n,\:\: k\: \:  \epsilon \: \mathbb{N}  [/latex]

Da hipótese [latex] F_{n-1} < (7/4)^{n-1} [/latex],

Então 

[latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex]

[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]

 [latex]F_{n+1} < (7/4)^{n-1} \times 11/4 <  (7/4)^{n-1}*49/16 [/latex]

[latex]F_{n+1} < (7/4)^{n+1} [/latex]

Está provado, por indução forte.

Vitor, por que você substituiu o [latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex] por 
[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]? Não entendi de onde veio o [/latex] (7/4 + 1)  [/latex].

Perceval escreveu:

Vitor Ahcor escreveu:Casos iniciais:

[latex]F_1 = 1 < (7/4) [/latex] ok

[latex]F_2 = 1 < (7/4)^2 [/latex] ok

[latex] F_3 = 2 < (7/4)^3 [/latex] ok

[latex]F_4 = 3 < (7/4)^4 [/latex] ok


Conjectura: [latex] F_n < (7/4)^n \: \forall \, \: \: k \leq n,\:\: k\: \:  \epsilon \: \mathbb{N}  [/latex]

Da hipótese [latex] F_{n-1} < (7/4)^{n-1} [/latex],

Então 

[latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex]

[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]

 [latex]F_{n+1} < (7/4)^{n-1} \times 11/4 <  (7/4)^{n-1}*49/16 [/latex]

[latex]F_{n+1} < (7/4)^{n+1} [/latex]

Está provado, por indução forte.

Vitor, por que você substituiu o [latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex] por 
[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]? Não entendi de onde veio o [/latex] (7/4 + 1)  [/latex].

Perceba que o termo (7/4)^n-1 ficou em evidência, assim como em:

x^n + x^(n-1) = x^(n-1) * x + x^(n-1) = x^(n-1)*(x+1)

Vitor Ahcor escreveu:

Perceval escreveu:

Vitor Ahcor escreveu:Casos iniciais:

[latex]F_1 = 1 < (7/4) [/latex] ok

[latex]F_2 = 1 < (7/4)^2 [/latex] ok

[latex] F_3 = 2 < (7/4)^3 [/latex] ok

[latex]F_4 = 3 < (7/4)^4 [/latex] ok


Conjectura: [latex] F_n < (7/4)^n \: \forall \, \: \: k \leq n,\:\: k\: \:  \epsilon \: \mathbb{N}  [/latex]

Da hipótese [latex] F_{n-1} < (7/4)^{n-1} [/latex],

Então 

[latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex]

[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]

 [latex]F_{n+1} < (7/4)^{n-1} \times 11/4 <  (7/4)^{n-1}*49/16 [/latex]

[latex]F_{n+1} < (7/4)^{n+1} [/latex]

Está provado, por indução forte.

Vitor, por que você substituiu o [latex]F_n + F_{n-1} <(7/4)^n + (7/4)^{n-1} [/latex] por 
[latex]F_{n+1} < (7/4)^{n-1} \times (7/4 + 1)  [/latex]? Não entendi de onde veio o [/latex] (7/4 + 1)  [/latex].

Perceba que o termo (7/4)^n-1 ficou em evidência, assim como em:

x^n + x^(n-1) = x^(n-1) * x + x^(n-1) = x^(n-1)*(x+1)

Entendi! Obrigado!