Propriedades da Sequência de Fibonacci

1. mdc(fib(n), fib(m)) = fib(mdc(n, m))

Prova: Por contradição, mostra-se primeiro que quaisquer dois termos consecutivos da sequência de Fibonacci são coprimos. Depois, para n > m, demonstra-se que mdc(fib(n), fib(m)) = mdc(fib(n-m), fib(m)). Aplicando recursivamente, obtém-se mdc(fib(n), fib(m)) = mdc(fib(k), fib(l)) até que k = l, caso contrário a recursão continua. O valor de k é obtido por subtrações sucessivas, e prova-se que k = mdc(n, m). Protanto, mdc(fib(n), fib(m)) = fib(mdc(n, m)).

2. Se fib(k) é divisível por x, então fib(k·i) também é divisível por x.

3. f(0) + f(1) + f(2) + … + f(n) = f(n+2) - 1

4. f(1) + f(3) + f(5) + … + f(2n-1) = f(2n)

5. f(2) + f(4) + f(6) + … + f(2n) = f(2n+1) - 1

6. [f(0)]² + [f(1)]² + … + [f(n)]² = f(n) · f(n+1)

7. f(0) - f(1) + f(2) - … + (-1)^n · f(n) = (-1)^n · [f(n+1) - f(n)] + 1

8. f(m+n) = f(m-1) · f(n-1) + f(m) · f(n)

9. [f(n)]² = (-1)^(n-1) + f(n-1) · f(n+1)

10. f(2n-1) = [f(n)]² - [f(n-2)]²

11. 3·f(n) = f(n+2) + f(n-2)

12. f(2n-2m-2) · [f(2n) + f(2n+2)] = f(2m+2) + f(4n-2m) [ n > m ≥ -1, n ≥ 1 ]

Observação: A soma dos primeiros n termos da sequência de Fibonacci é igual ao termo de índice n+2 subtraído de 1.

Implementações da Sequência de Fibonacci em Go

A sequência de Fibonacci é definida como: F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ para n ≥ 2. Abaixo estão quatro maneiras de implementá‑la em Go.

1. Implementação Recusriva

package main

import "fmt"

const LIMITE = 40

func main() {
    var sequencia [LIMITE]int
    for i := 0; i < LIMITE; i++ {
        sequencia[i] = fibonacci(i)
    }
    fmt.Println(sequencia)
}

func fibonacci(indice int) (resultado int) {
    if indice <= 1 {
        resultado = 1
    } else {
        resultado = fibonacci(indice-1) + fibonacci(indice-2)
    }
    return
}

2. Implementação Recursiva com Memoização

package main

import "fmt"

const LIMITE = 40

var memoria [LIMITE]uint64

func main() {
    var sequencia [LIMITE]uint64
    for i := 0; i < LIMITE; i++ {
        sequencia[i] = fibonacci(i)
    }
    fmt.Println(sequencia)
}

func fibonacci(indice int) (resultado uint64) {
    if memoria[indice] != 0 {
        return memoria[indice]
    }
    if indice <= 1 {
        resultado = 1
    } else {
        resultado = fibonacci(indice-1) + fibonacci(indice-2)
    }
    memoria[indice] = resultado
    return
}

3. Implementação Iterativa com Array

package main

import "fmt"

const LIMITE = 40

func main() {
    fmt.Println(criarArrayFib(LIMITE))
}

func criarArrayFib(termos int) []int {
    lista := make([]int, termos)
    lista[0], lista[1] = 1, 1
    for i := 2; i < termos; i++ {
        lista[i] = lista[i-1] + lista[i-2]
    }
    return lista
}

4. Implementação com Closure

package main

import "fmt"

const LIMITE = 40

func main() {
    gerador := fibonacci()
    var sequencia [LIMITE]int
    for i := 0; i < LIMITE; i++ {
        sequencia[i] = gerador()
    }
    fmt.Println(sequencia)
}

func fibonacci() func() int {
    anterior, atual := 0, 1
    return func() int {
        anterior, atual = atual, anterior+atual
        return anterior
    }
}