Teoria de números/Eficiência do algoritmo de Euclides: diferenças entre revisões
[edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m + img. +cm |
+ propriedades de \phi |
||
Linha 116:
Também é possível demonstrar que é válida a [[w:Fórmula de Binet|fórmula de Binet]]:
:<math>F_n = \frac
onde:
* <math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\,\!</math>, que é conhecido como o [[w:número de ouro|número de ouro]];
* <math>\hat{\varphi} = \frac{1 - \sqrt{5}}{2} = \approx -0.618\,\!</math>
}}
Linha 189 ⟶ 193:
|}
Para demonstrar o [[w:teorema de Lamé|teorema de Lamé]], é importante ter em mente algumas propriedades relacionadas a [[w:sequência de Fibonacci|sequência de Fibonacci]] e ao [[w:Proporção áurea|número de ouro]]:
:<math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\,\!</math>
Tem-se:
* <math>F_n = \frac{\varphi^n}{\sqrt{5}}\,\!</math>, arredondado para o inteiro mais próximo.
{{Demonstração|
Utilizando a fórmula de Binet, basta observar que o módulo de <math>\hat{\varphi}\,\!</math> é menor que <math>1\,\!</math>, e consequentemente, quando <math>n \to \infty\,\!</math>, tem-se <math>\hat{\varphi}^n \to 0\,\!</math>
}}
* <math>F_n \ge \varphi^{n-1}\,\!</math>
{{Demonstração|
Segue facilmente por indução.
}}
== Exercícios ==
|