Pensando Sobre Matemática #69 - Fibonnaci #2

Vamos retomar o raciocínio de uns dias atrás, vou aproveitar que eu estou bastante matemático esses dias.

Então liga o seu Javascript e prepara o Mathjax que hoje tem bastante número!

A gente vai demonstrar que isso aqui funciona: $$\mathrm{F(n)}=\frac{{(1+\sqrt{5})}^n-{(1-\sqrt{5})}^n}{2^n.\sqrt{5}}$$ Pra fazer isso a gente vai usar o Princípio da Indução Finita. A primeira coisa que a gente tem que ver é se essa fórmula fechada funciona pra algum valor da sequência de Fibonnaci. Aqui eu vou dizer que $F_0$ é o primeiro termo da sequência de Fibonnaci pra poder alinhar a fórmula fechada com a sequência, caso contrário teríamos que voltar no capítulo anterior e fazer um novo sistema linear. Em outras palavras: $$0=F_0=\mathrm{F(0)}$$ Pela definição da sequência, o primeiro termo é 0. Vejamos como F(0) se sai nessa brincadeira: $$\mathrm{F(0)}=\frac{{(1+\sqrt{5})}^0-{(1-\sqrt{5})}^0}{2^0.\sqrt{5}}$$ $$\mathrm{F(0)}=\frac{1-1}{1.\sqrt{5}}=\frac{0}{1.\sqrt{5}}=0$$ Opa, deu 0! Até aí ta tudo bem. Só que essa relação de recorrência de Fibonacci usa dois termos. Então a gente vai verificar se F(1) também ta valendo: $$\mathrm{F(1)}=\frac{{(1+\sqrt{5})}^1-{(1-\sqrt{5})}^1}{2^1.\sqrt{5}}$$ $$\mathrm{F(1)}=\frac{(1+\sqrt{5})-(1-\sqrt{5})}{2.\sqrt{5}}$$ $$\mathrm{F(1)}=\frac{1+\sqrt{5}-1+\sqrt{5}}{2.\sqrt{5}}=\frac{1-1+\sqrt{5}+\sqrt{5}}{2.\sqrt{5}}=\frac{2.\sqrt{5}}{2.\sqrt{5}}=1$$ Show de bola. Então a base da indução está construída, então agora vem o passo de indução. Suponha que F(k) é verdadeiro. Então se F(k) implica em F(k+1) confirmamos que a fórmula fechada é válida. É importante frisar que a relação de recorrência é válida para qualquer membro da sequência que nao sejam os iniciais, até porque é dessa relação que saiu isso tudo. Enfim: $$\mathrm{F(k)}\to \mathrm{F(k\; +\; 1)}$$ $$\mathrm{F(k)}+\mathrm{F(k\; +\; 1)}=\mathrm{F(k\; +\; 2)}$$ Vamos usar a recorrência para chegar em F(k+1) da seguinte forma: $$\mathrm{F(k)}=\frac{{(1+\sqrt{5})}^k-{(1-\sqrt{5})}^k}{2^k.\sqrt{5}}$$ $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{{(1+\sqrt{5})}^k-{(1-\sqrt{5})}^k}{2^k.\sqrt{5}}+\frac{{(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}-{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}}}{2^{\mathrm{k\; -\; 1}}.\sqrt{5}}$$ Essa é uma expressão particularmente grande. A gente vai fazer uma pequena mágica aqui só pra poder fatorá-la 2 vezes. Vamos multiplicar o denominador e o numerador da segunda parcela por dois, pra igualar o denominador das duas frações: $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{{(1+\sqrt{5})}^k-{(1-\sqrt{5})}^k}{2^k.\sqrt{5}}+\frac{2.{(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}-2.{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}}}{2.2^{\mathrm{k\; -\; 1}}.\sqrt{5}}$$ $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{{(1+\sqrt{5})}^k-{(1-\sqrt{5})}^k}{2^k.\sqrt{5}}+\frac{2.{(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}-2.{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}}}{2^k.\sqrt{5}}$$ Daí podemos fator não só uma: $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{1}{2^k.\sqrt{5}}({(1+\sqrt{5})}^k-{(1-\sqrt{5})}^k+{(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}-{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}})$$ Mas 2 vezes: $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{1}{2^k.\sqrt{5}}({(1+\sqrt{5})}^k-{(1-\sqrt{5})}^k+{2.(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}-{2.(1-\sqrt{5})}^{\mathrm{k\; -\; 1}})$$ $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{1}{2^k.\sqrt{5}}({(1+\sqrt{5})}^k+{2.(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}-{(1-\sqrt{5})}^k-{2.(1-\sqrt{5})}^{\mathrm{k\; -\; 1}})$$ $$\mathrm{F(k)}+\mathrm{F(k\; -\; 1)}=\frac{1}{2^k.\sqrt{5}}({(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}.(1+\sqrt{5}+2)-{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}}.(1-\sqrt{5}+2))$$ Deixa eu aproveitar aqui pra acertar a relação de recorrência do lado esquerdo: $$\mathrm{F(k\; +\; 1)}=\frac{1}{2^k.\sqrt{5}}({(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}.(3+\sqrt{5})-{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}}.(3-\sqrt{5}))$$ Putz! E agora? como aquelas potências vão se ajeitar!? Seria muito legal se esses produtos gerassem as parcelas elevadas a k+1 pra poder fechar a demonstração... Mas... pera... $${(1+\sqrt{5})}^2=1+2.\sqrt{5}+5=6+2.\sqrt{5}$$ $$\frac{{(1+\sqrt{5})}^2}{2}=\frac{6+2.\sqrt{5}}{2}$$ $$\frac{{(1+\sqrt{5})}^2}{2}=3+\sqrt{5}$$ WHAT!? $${(1-\sqrt{5})}^2=1-2.\sqrt{5}+5=6-2.\sqrt{5}$$ $$\frac{{(1-\sqrt{5})}^2}{2}=\frac{6-2.\sqrt{5}}{2}$$ $$\frac{{(1-\sqrt{5})}^2}{2}=3-\sqrt{5}$$ Caceta! $$\mathrm{F(k\; +\; 1)}=\frac{1}{2^k.\sqrt{5}}({(1+\sqrt{5})}^{\mathrm{k\; -\; 1}}.\frac{{(1+\sqrt{5})}^2}{2}-{(1-\sqrt{5})}^{\mathrm{k\; -\; 1}}.\frac{{(1-\sqrt{5})}^2}{2})$$ $$\mathrm{F(k\; +\; 1)}=\frac{1}{2^k.\sqrt{5}}(\frac{{(1+\sqrt{5})}^{\mathrm{k\; +\; 1}}}{2}-\frac{{(1-\sqrt{5})}^{\mathrm{k\; +\; 1}}}{2})$$ $$\mathrm{F(k\; +\; 1)}=\frac{{(1+\sqrt{5})}^{\mathrm{k\; +\; 1}}-{(1-\sqrt{5})}^{\mathrm{k\; +\; 1}}}{2^{\mathrm{k\; +\; 1}}.\sqrt{5}}$$ Gente, não é que funcionou mesmo!?(Mentira. eu já sabia que ia funcinar)


Imagens:
https://gigantesdamatematica.wordpress.com/2015/12/18/leonardo-fibonacci-1170-1250/