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
continuando os cálculos |
demonstração: Fórmula de Binet (começo) |
||
Linha 237:
Mas <math>\frac{1}{\log \varphi} < 5\,\!</math>, então:
:<math>n\le \frac{1}{\log \varphi}\cdot \log a < 5\log_{\varphi}a < 5N\,\!</math>, onde <math>N\,\!</math> é o número de dígitos de <math>a\,\!</math>
== Demonstração da fórmula de Binet ==
Nesta seção, será deduzida a [[w:Fórmula de Binet|fórmula de Binet]]:
:<math>F\left(n\right) = \frac{1}{\sqrt{5}}\left ( \left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{2} \right )^n \right ) = \frac{\varphi ^n - \hat{\varphi}^n}{\sqrt{5}}\,\!</math>
onde <math>\varphi = \frac{1 + \sqrt{5}}{2}\,\!</math> e <math>\hat{\varphi} = \frac{1 - \sqrt{5}}{2}\,\!</math>.
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>.
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:
:<math>Q = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\,\!</math>
A partir de um simples argumento de indução (veja [[#Exercícios|exercício 1]]), obtem-se:
:<math>\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = Q^n \cdot \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix}\,\!</math>
Neste ponto, recorre-se à [[Álgebra linear]], para obter um jeito simples de calcular o produto acima.
== Exercícios ==
# Verifique, utilizando o princípio de indução, que:
Por enquanto, não há exercícios sobre este capítulo. O leitor está convidado a adicionar exercícios nesta seção, para ajudar a melhorar o texto.▼
::<math>\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n \cdot \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix}\,\!</math>
# Escreva outra demonstração para a fórmula de Binet, utilizando o princípio de indução.
▲Por enquanto, não há muitos exercícios sobre este capítulo. O leitor está convidado a adicionar
[[Categoria:
| |||