Já que o Ralph mandou uma solução "recorrência mate-mágica", eu vou completar com uma solução "Força bruta mate-mágica".
Você conhece a fórmula dos números de Fibonacci, né? F(n) = (a^n - b^n)/raiz(5), onde 2a = 1 + raiz(5) e 2b = 1 - raiz(5). Bom, isso quer dizer que 5 * F(n)^2 = (a^n - b^n)^2 = a^(2n) - 2 a^n b^n + b^(2n). Bom, 5 * F(n)^2 é um quadrado (mas de um número irracional, porque tem um raiz(5)). Mas não é isso que a gente quer. Lembra que tem um "-4". Mas como conseguir fazer o -4 ajudar a formar um quadrado ??? É aqui que entra a mágica dos Fibonacci: a*b = -1. Assim, o termo cruzado é simplesmente -2 * (-1)^n. Que é -2 quando n é par, +2 quando n é ímpar. E quando n é impar, somando com o -4, isso vira "-2", ou seja, troca o sinal. Trocando o sinal, fica a^(2n) + 2 a^n b^n + b^(2n) = (a^n + b^n)^2. Aqui, você pode terminar de vários jeitos. Note que os termos com "raiz(5)" vão cancelar (porque "a" tem 1 + raiz(5) e "b" tem 1 - raiz(5)), mas o maior problema mesmo é que tem um fator 2^n no denominador. Eu faria assim (pensando um pouco como o Ralph) : a^n + b^n satisfaz a mesma recorrência de Fibonacci (porque a^2 = a + 1 e b^2 = b + 1, portanto a^(n+2) = a^(n+1) + a^n e idem para b, e daí a soma também). Vejamos os primeiros valores a^0 + b^0 = 1 + 1 = 2 (inteiro) a^1 + b^1 = (1 + raiz(5))/2 + (1 - raiz(5))/2 = 1 (inteiro) Daí, todos os valores de a^n + b^n são inteiros também ! Pra conferir: n : F(n) : a^n + b^n 0 : 0 : 2 (5*0 + 4 = 4 = 2^2) 1 : 1 : 1 (5*1 - 4 = 1 = 1^2) 2 : 1 : 3 (5*1 + 4 = 9 = 3^2) 3 : 2 : 4 (5*4 - 4 = 16 = 4^2) 4 : 3 : 7 (5*9 + 4 = 49 = 7^2) 5 : 5 : 11 (5*25 - 4 = 121 = 11^2) 6 : 8 : 18 (5*64 + 4 = 324 = 18^2) 7 : 13 : 29 (5*169 - 4 = 841 = 29^2) (eu pensei que isso ia dar certo porque, veja bem, 5 * F(2n+1)^2 quer dizer que a raiz(5) do denominador vai embora, daí que devia dar pra simplificar) Antes de acabar, também uma fórmula com quadrados dentro de Fibonacci: F(n)^2 = F(n-1)*F(n+1) - (-1)^n, e no nosso caso, a gente tem um treco do tipo 5 F(n)^2 - 4(-1)^n = C(n)^2, e eu quase aposto que dá pra mostrar isso direto... E como disse o Ralph: é claro que as soluções de 5n^2 - 4 = m^2 vão satisfazer uma recorrência (Pell), e ele sabia disso, portanto ele fez as contas e achou a recorrência. Eu tive preguiça de achar a recorrência, mas acabei achando uma fórmula com um - 4 (-1)^n ;) Abraços, -- Bernardo Freitas Paulo da Costa 2012/1/16 Ralph Teixeira <[email protected]>: > Bom, eu não sabia disso mas agora que você falou... > > A recorrência que define os termos de ordem ímpar da seq. de Fibonacci > pode ser obtida assim: > > F(2n+1)=F(2n)+F(2n-1) > F(2n)=F(2n-1)+F(2n-2) > F(2n-2)=F(2n-1)-F(2n-3) (tô fazendo um esforço para só deixar os de > ordem ímpar do lado direito) > > Então > > F(2n+1)=3F(2n-1)-F(2n-3) > > Agora deixa eu ver os "alegados" quadrados. Seriam: > F(n) 5F(n)^2-4 > 1 1=1^2 > 2 16=4^2 > 5 121=11^2 > 13 841=29^2 > ... ... > > Será que a sequencia da direita tem alguma ordem razoável... Digo, > olhando para 1,4,11,29..., qual é a recorrência? Hmmm, parece que cada > termo é 3 vezes o anterior menos ao anteanterior, de novo! Bom, mas > isso tudo é chute, vamos ver se a gente consegue MOSTRAR isso. > > TEOREMA: Defina A(0)=1, A(1)=2 e A(n+1)=3A(n)-A(n-1) (n>=2). Defina > também B(0)=1, B(1)=4 e B(n+1)=3B(n)-B(n-1). Afirmo que: > > i) 5A(n)^2-4=B(n)^2 > ii) você já vai ver que preciso de algo mais aqui. > > Prova: i) Para n=0 e n=1 é só verificar direto. Por indução, se a > propriedade vale para n=k e n=k-1, então: > 5A(k+1)^2-4 = 5(3A(k)-A(k-1))^2-4 = 45A(k)^2-30A(k)A(k-1)+5A(k-1)^2-4 > = (9B(k)^2+36)-30A(k)A(k-1)+B(k-1)^2 > > Ah, droga, eu não tenho a mínima ideia do que fazer com aquele > A(k)A(k-1)... Se fosse algo conhecido, razoável.... tipo, eu acho que > a coisa toda vai dar (3B(k)-B(k-1))^2, né? Para isso valer, eu > precisava que fosse 36-30A(k)A(k-1)=-6B(k)B(k-1), isto é, eu queria > que fosse 5A(k)A(k-1)=B(k)B(k-1)+6... Como provar isto? Façamos por > indução, ora! Então adicione lá no enunciado o seguinte: > > ii) 5A(n)A(n-1)=B(n)B(n-1)+6 > > Esta propriedade claramente vale para n=1 e n=2. Agora o passo de > indução (note que estou usando (i) com n=k, então a indução é feita > com (i) e (ii) ao mesmo tempo!): > > 5A(k+1)A(k) = 5(3A(k)-A(k-1))A(k) = 15A(k)^2-5A(k)A(k-1) = > (3B(k)^2+12)-B(k)B(k-1)-6 = > = 3B(k)^2-B(k)(3B(k)-B(k+1))+6 = B(k)B(k+1)+6 > > Pronto! Este era o pedaço que faltava para terminar a indução em (i). Acabou! > > Abraço, > Ralph > > P.S.: Agora, para DESCOBRIR que estes números funcionam, dê uma olhada > na teoria de Equação de Pell, que ajuda a resolver coisas do tipo > 5n^2-4=p^2. > > 2012/1/15 marcone augusto araújo borges <[email protected]>: >> Provar q a equação x^2+y^2+z^2=3xyz tem infinitas soluções inteiras. >> >> Essa questão ja foi resolvida na lista >> Um colega tentou uma soluçao diferente: >> Fez y=n e z=1,encontrando x^2 - 3nx +n^2 +1=0 >> x= (3n + - raiz(5n^2 - 4))/2 >> 5n^2 - 4 deve ser um quadrado perfeito >> Tentei mostrar q existem infinitos valores de n para os quais 5n^2 - 4 é um >> quadrado perfeito e não consegui >> Mas o colega me informou q para n igual aos termos de ordem impar da >> sequencia de fibonacci, a referida expressão >> é um quadrado perfeito(1,2,5,13,34,...) >> Não sabemos provar >> Alguem poderia esclarecer? > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > ========================================================================= ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
