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 atualizando sintaxe usada nas predefinições |
m atualizando |
||
Linha 205:
Tem-se:
* <math>\varphi^2 = \varphi + 1\,\!</math>
{{
* <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
|A justificativa será dada por indução:
# <math>F_1 = 1 \ge 1 = \varphi^0\,\!</math>
# Se for verdade que <math>F_n \ge \varphi^{n-1}\,\!</math>, então:
Linha 221:
* <math>\log \varphi < \frac{1}{5}\,\!</math>
{{Demonstração
|De fato, valem as seguintes equivalências:
<math>\log \varphi < \frac{1}{5} \Leftrightarrow 5\log \varphi < 1 \Leftrightarrow \log \varphi^5 < 1 \,\!</math>
Linha 249:
A principal razão para se utilizar está fórmula, em vez da definição recursiva da sequência de Fibonacci, é que ela permite a obtenção de um termo da sequência <u>sem precisar calcular os anteriores</u>.
{{Demonstração
|A relação entre os termos da sequência pode ser descrita matricialmente da seguinte forma:
:<math>\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}\,\!</math>
Para simplificar, será adotada a seguinte notação:
| |||