Quem acompanhou as contas na caixa azul do post sobre o Pokèmon Twitch deve ter notado que eu pulei um pedaço. Em certo ponto da demonstração, eu magicamente tirei do chapéu uma fórmula nada óbvia:
E como foi que eu cheguei nessa fórmula? Simples, eu calculei no Wolfram Alpha:
"Ricbit, você trapaceou! Que roubalheira! Um matemático de verdade jamais faria isso!"
Mas será que é trapaça mesmo? Nesse post, eu vou mostrar como se resolve essa conta sem usar o Wolfram Alpha; e, se você acha que é trapaça, talvez acabe mudando de idéia :)
Para resolver essa somatória sem usar o Wolfram Alpha, nós precisamos relembrar as progressões que aprendemos no colégio. A primeira delas foi a progressão aritmética, onde a diferença entre dois números consecutivos é constante:
A segunda delas é a progressão geométrica, onde a razão entre dois números consecutivos é constante:
Uma progressão extremamente útil que não ensinam no colégio é a progressão hipergeométrica. Ela parece com a progressão geométrica, porque é definida a partir da razão entre dois elementos consecutivos. Mas agora, ao invés dessa razão ser constante, nós permitimos que a razão seja uma função racional (que é só um jeito chique de dizer que ela é o quociente entre dois polinômios):
Naquela somatória que queremos resolver, os termos sendo somados formam uma progressão hipergeométrica. Confira:
O numerador é um polinômio em q, o denominador é um polinômio em q. Então confere com a nossa definição de progressão hipergeométrica.
Certamente vocês lembram que as progressões do colégio tinham uma fórmula para a soma de seus termos. A soma dos n primeiros termos da progressão aritmética é:
A soma dos n primeiros termos da progressão geométrica é:
A soma dos n primeiros termos da progressão hipergeométrica é... oops! Não existe uma fórmula geral para a soma de termos hipergeométricos.
Antigamente, achar uma fórmula para uma soma hipergeométrica era tão raro que elas até ganhavam nomes especiais. Por exemplo, a igualdade abaixo tem um nome, é o Binômio de Newton:
Outras somas hipergeométricas não tem fórmula, mas são tão úteis, que a própria soma ganha um nome e passa a valer como se fosse uma fórmula:
Por muitos séculos esse foi o estado da arte. Alguém acha uma fórmula aqui, alguém nomeia uma soma ali. Mas isso mudou no meio do século 20.
O primeiro progresso na direção de um método geral de resolução de somas hipergeométricas foi feito pela Mary Celine Fasenmyer em 1945. Depois de se formar em matemática, ela se juntou à ordem religiosa Sisters of Mercy (sim, a mesma que inspirou o nome da banda), e lá ela criou o Método da Irmã Celine, um algoritmo que consegue resolver automaticamente alguns tipos de somas hipergeométicas.
Em 1978 o método foi aprimorado por Bill Gosper e se tornou o algoritmo de Gosper (muito embora eu desconfie que, se a Irmã Celine fosse homem, o algoritmo seria de Gosper-Celine). O método de Gosper se baseia em um teorema surpreendente: A solução de uma soma hipergeométrica é outro hipergeométrico, se e somente se ela puder ser escrita na forma abaixo, onde R[j] é uma função racional.
Essa somatória parece esquisita. Se j é o índice da somatória, então o que ele está fazendo no lado direito da equação? E cadê os limites da somatória?
A resposta é que essa é uma somatória indefinida. Funciona do mesmo jeito que no cálculo: lá você tem integrais definidas e integrais indefinidas, aqui nós temos somatórias definidas (com limites), e somatórias indefinidas (sem limites). Para uma somatória indefinida, sempre vale a propriedade abaixo:
Essas duas equações são tudo que nós precisamos para usar o algoritmo de Gosper. Vamos à caixa azul calcular a nossa somatória original:
No final do século 19, o Bertrand Russell e o Alfred Whitehead tiveram uma idéia. Ele bolaram um plano para axiomatizar toda a matemática, de uma maneira completa e livre de contradições. Se o plano funcionasse, então toda a Matemática seria reduzida à manipulação de símbolos, que é um processo puramente mecânico e automatizável. O plano começou muito bem, a ponto do Whitehead fazer a seguinte declaração:
"A Civilização avança estendendo o número de operações importantes que podemos fazer sem ter que pensar."
Baseado nessa citação, o Concrete Mathematics
do Knuth vai além e conclui:
"O objetivo final da matemática é eliminar a necessidade de todo pensamento inteligente."
É verdade, o objetivo sempre foi esse. Para os babilônios, resolver uma equação de segundo grau era dificílimo, só os grandes mestres conseguiam. Hoje em dia, nós transformamos a equação de segundo grau em uma fórmula que é ensinada para crianças de 14 anos. Você não precisa ser inteligente para usar a fórmula, é só substituir os números e fazer as contas.
Imagine se fosse possível fazer isso com toda a matemática, ao invés de só com equações de segundo grau! Você poderia usar computadores para fazer as contas, no lugar de crianças de 14 anos. A Matemática seria um problema resolvido, e aí você pode se concentrar no que interessa, que são as aplicações. Um físico acabou de descobrir uma propriedade quântica nova, será que ela permite criar um aparelho de teletransporte? Eu monto a equação, jogo no computador, e tcharam! Está aqui a resposta!
Toda a saga por trás do plano do Russell e do Whitehead é contada em quadrinhos no fabuloso Logicomix
. Infelizmente, o final da história é que o plano falhou. E falhou espetacularmente. Em 1931, o Gödel provou que nenhum sistema axiomático é capaz de provar todas as sentenças verdadeiras que é capaz de descrever, acabando de uma vez por todas com o sonhado plano da axiomatização completa.
E o século 20 desceu ladeira abaixo. O Church provou que, mesmo se a axiomatização completa tivesse tido sucesso, seria impossível criar um método que prove um teorema qualquer a partir dos axiomas. O Turing provou que é impossível criar um método que analise um programa de computador e diga se ele termina ou se entra em loop infinito. O Matiyasevich provou que é impossível criar um método que resolva todas as equações diofantinas. O Richardson provou que é impossível criar um método que prove todas as identidades trigonométricas. Foi o fim da matemática automatizada... ou não?
Claro que não! Todos esses teoremas provam a impossibilidade do caso geral. Mas você sempre pode automatizar um caso específico. Não existe uma fórmula geral para a soma hipergeométrica, mas o algoritmo de Gosper prova que pelo menos um caso especial pode ser automatizado: o caso da soma hipergeométrica cujo resultado também é um termo hipergeométrico. E esse caso é imensamente útil na prática, especialmente se você estuda computação ou combinatória.
E no fim das contas, usar o Wolfram Alpha para resolver uma somatória é trapacear ou não? Por dentro, tudo que o Wolfram Alpha faz é usar o algoritmo de Gosper. Se você acredita que usar um método computacional é roubar, então por consistência precisa abrir de mão de todos os outros métodos computacionais. Não pode mais resolver a equação de segundo grau usando a fórmula de Bhaskara, não pode mais calcular o máximo divisor comum com o algoritmo de Euclides, não pode nem calcular quanto é 463 vezes 367 sem antes decorar a tabuada do 367.
Para mim isso não faz sentido. E por isso eu uso o Wolfram Alpha sem medo de ser feliz :)
E como foi que eu cheguei nessa fórmula? Simples, eu calculei no Wolfram Alpha:
"Ricbit, você trapaceou! Que roubalheira! Um matemático de verdade jamais faria isso!"
Mas será que é trapaça mesmo? Nesse post, eu vou mostrar como se resolve essa conta sem usar o Wolfram Alpha; e, se você acha que é trapaça, talvez acabe mudando de idéia :)
A progressão hipergeométrica
Para resolver essa somatória sem usar o Wolfram Alpha, nós precisamos relembrar as progressões que aprendemos no colégio. A primeira delas foi a progressão aritmética, onde a diferença entre dois números consecutivos é constante:
A segunda delas é a progressão geométrica, onde a razão entre dois números consecutivos é constante:
Uma progressão extremamente útil que não ensinam no colégio é a progressão hipergeométrica. Ela parece com a progressão geométrica, porque é definida a partir da razão entre dois elementos consecutivos. Mas agora, ao invés dessa razão ser constante, nós permitimos que a razão seja uma função racional (que é só um jeito chique de dizer que ela é o quociente entre dois polinômios):
Naquela somatória que queremos resolver, os termos sendo somados formam uma progressão hipergeométrica. Confira:
O numerador é um polinômio em q, o denominador é um polinômio em q. Então confere com a nossa definição de progressão hipergeométrica.
A soma da progressão hipergeométrica
Certamente vocês lembram que as progressões do colégio tinham uma fórmula para a soma de seus termos. A soma dos n primeiros termos da progressão aritmética é:
A soma dos n primeiros termos da progressão geométrica é:
A soma dos n primeiros termos da progressão hipergeométrica é... oops! Não existe uma fórmula geral para a soma de termos hipergeométricos.
Antigamente, achar uma fórmula para uma soma hipergeométrica era tão raro que elas até ganhavam nomes especiais. Por exemplo, a igualdade abaixo tem um nome, é o Binômio de Newton:
Outras somas hipergeométricas não tem fórmula, mas são tão úteis, que a própria soma ganha um nome e passa a valer como se fosse uma fórmula:
Por muitos séculos esse foi o estado da arte. Alguém acha uma fórmula aqui, alguém nomeia uma soma ali. Mas isso mudou no meio do século 20.
O algoritmo de Gosper
O primeiro progresso na direção de um método geral de resolução de somas hipergeométricas foi feito pela Mary Celine Fasenmyer em 1945. Depois de se formar em matemática, ela se juntou à ordem religiosa Sisters of Mercy (sim, a mesma que inspirou o nome da banda), e lá ela criou o Método da Irmã Celine, um algoritmo que consegue resolver automaticamente alguns tipos de somas hipergeométicas.
Em 1978 o método foi aprimorado por Bill Gosper e se tornou o algoritmo de Gosper (muito embora eu desconfie que, se a Irmã Celine fosse homem, o algoritmo seria de Gosper-Celine). O método de Gosper se baseia em um teorema surpreendente: A solução de uma soma hipergeométrica é outro hipergeométrico, se e somente se ela puder ser escrita na forma abaixo, onde R[j] é uma função racional.
Essa somatória parece esquisita. Se j é o índice da somatória, então o que ele está fazendo no lado direito da equação? E cadê os limites da somatória?
A resposta é que essa é uma somatória indefinida. Funciona do mesmo jeito que no cálculo: lá você tem integrais definidas e integrais indefinidas, aqui nós temos somatórias definidas (com limites), e somatórias indefinidas (sem limites). Para uma somatória indefinida, sempre vale a propriedade abaixo:
Essas duas equações são tudo que nós precisamos para usar o algoritmo de Gosper. Vamos à caixa azul calcular a nossa somatória original:
Começamos substituindo uma equação na outra:
Podemos então dividir tudo por h[j]:
Opa, a razão entre os h nós já calculamos lá em cima para a nossa somatória!
Falta achar R[j]. Eu sei que ele é um quociente de polinômios, mas não sei qual o grau desses polinômios. Eu vou chutar que o grau é 1, se der errado depois eu volto e aumento o grau. Pois bem, se o grau é 1, então R[j] é da forma abaixo:
Agora eu vou substituir. Aperte o cinto que lá vem turbulência:
O resultado é um polinômio gigante em j que é identicamente nulo. Se ele é identicamente nulo, então cada um dos seus coeficientes precisa ser zero. Com isso podemos montar um sistema de equações:
Agora é "só" resolver o sistema! Vou poupá-los de páginas e páginas, o resultado é o seguinte:
Se o sistema não tivesse solução, eu teria que voltar lá em cima e aumentar o grau do polinômio (se as contas foram titânicas com grau 1, imagine com grau 2). Mas o processo não é infinito, existem métodos que permitem achar um limite superior para o grau do polinômio. Se você atingir esse limite sem achar nenhuma solução, então você provou que sua somatória não pode ser escrita como um hipergeométrico.
Voltando à nossa equação original, agora nós sabemos quanto vale a somatória indefinida:
Nós queremos a soma de 1 até m, então precisamos converter a soma indefinida em uma soma definida, usando o teorema fundamental do cálculo discreto:
Aplicando o teorema, temos:
Pronto, esse é o resultado final. Eu acho muito importante que a pessoa resolva o algoritmo de Gosper uma vez na vida, para nunca mais cometer a sandice de repetir o processo. O método é mecânico, você só precisa seguir as regras e não errar as contas. O computador faz isso melhor que você. Use o Wolfram Alpha e economize grafite.
Podemos então dividir tudo por h[j]:
Opa, a razão entre os h nós já calculamos lá em cima para a nossa somatória!
Falta achar R[j]. Eu sei que ele é um quociente de polinômios, mas não sei qual o grau desses polinômios. Eu vou chutar que o grau é 1, se der errado depois eu volto e aumento o grau. Pois bem, se o grau é 1, então R[j] é da forma abaixo:
Agora eu vou substituir. Aperte o cinto que lá vem turbulência:
O resultado é um polinômio gigante em j que é identicamente nulo. Se ele é identicamente nulo, então cada um dos seus coeficientes precisa ser zero. Com isso podemos montar um sistema de equações:
Agora é "só" resolver o sistema! Vou poupá-los de páginas e páginas, o resultado é o seguinte:
Se o sistema não tivesse solução, eu teria que voltar lá em cima e aumentar o grau do polinômio (se as contas foram titânicas com grau 1, imagine com grau 2). Mas o processo não é infinito, existem métodos que permitem achar um limite superior para o grau do polinômio. Se você atingir esse limite sem achar nenhuma solução, então você provou que sua somatória não pode ser escrita como um hipergeométrico.
Voltando à nossa equação original, agora nós sabemos quanto vale a somatória indefinida:
Nós queremos a soma de 1 até m, então precisamos converter a soma indefinida em uma soma definida, usando o teorema fundamental do cálculo discreto:
Aplicando o teorema, temos:
Pronto, esse é o resultado final. Eu acho muito importante que a pessoa resolva o algoritmo de Gosper uma vez na vida, para nunca mais cometer a sandice de repetir o processo. O método é mecânico, você só precisa seguir as regras e não errar as contas. O computador faz isso melhor que você. Use o Wolfram Alpha e economize grafite.
O objetivo final da Matemática
No final do século 19, o Bertrand Russell e o Alfred Whitehead tiveram uma idéia. Ele bolaram um plano para axiomatizar toda a matemática, de uma maneira completa e livre de contradições. Se o plano funcionasse, então toda a Matemática seria reduzida à manipulação de símbolos, que é um processo puramente mecânico e automatizável. O plano começou muito bem, a ponto do Whitehead fazer a seguinte declaração:
"A Civilização avança estendendo o número de operações importantes que podemos fazer sem ter que pensar."
Baseado nessa citação, o Concrete Mathematics
do Knuth vai além e conclui:"O objetivo final da matemática é eliminar a necessidade de todo pensamento inteligente."
É verdade, o objetivo sempre foi esse. Para os babilônios, resolver uma equação de segundo grau era dificílimo, só os grandes mestres conseguiam. Hoje em dia, nós transformamos a equação de segundo grau em uma fórmula que é ensinada para crianças de 14 anos. Você não precisa ser inteligente para usar a fórmula, é só substituir os números e fazer as contas.
Imagine se fosse possível fazer isso com toda a matemática, ao invés de só com equações de segundo grau! Você poderia usar computadores para fazer as contas, no lugar de crianças de 14 anos. A Matemática seria um problema resolvido, e aí você pode se concentrar no que interessa, que são as aplicações. Um físico acabou de descobrir uma propriedade quântica nova, será que ela permite criar um aparelho de teletransporte? Eu monto a equação, jogo no computador, e tcharam! Está aqui a resposta!
Toda a saga por trás do plano do Russell e do Whitehead é contada em quadrinhos no fabuloso Logicomix
. Infelizmente, o final da história é que o plano falhou. E falhou espetacularmente. Em 1931, o Gödel provou que nenhum sistema axiomático é capaz de provar todas as sentenças verdadeiras que é capaz de descrever, acabando de uma vez por todas com o sonhado plano da axiomatização completa.E o século 20 desceu ladeira abaixo. O Church provou que, mesmo se a axiomatização completa tivesse tido sucesso, seria impossível criar um método que prove um teorema qualquer a partir dos axiomas. O Turing provou que é impossível criar um método que analise um programa de computador e diga se ele termina ou se entra em loop infinito. O Matiyasevich provou que é impossível criar um método que resolva todas as equações diofantinas. O Richardson provou que é impossível criar um método que prove todas as identidades trigonométricas. Foi o fim da matemática automatizada... ou não?
Claro que não! Todos esses teoremas provam a impossibilidade do caso geral. Mas você sempre pode automatizar um caso específico. Não existe uma fórmula geral para a soma hipergeométrica, mas o algoritmo de Gosper prova que pelo menos um caso especial pode ser automatizado: o caso da soma hipergeométrica cujo resultado também é um termo hipergeométrico. E esse caso é imensamente útil na prática, especialmente se você estuda computação ou combinatória.
E no fim das contas, usar o Wolfram Alpha para resolver uma somatória é trapacear ou não? Por dentro, tudo que o Wolfram Alpha faz é usar o algoritmo de Gosper. Se você acredita que usar um método computacional é roubar, então por consistência precisa abrir de mão de todos os outros métodos computacionais. Não pode mais resolver a equação de segundo grau usando a fórmula de Bhaskara, não pode mais calcular o máximo divisor comum com o algoritmo de Euclides, não pode nem calcular quanto é 463 vezes 367 sem antes decorar a tabuada do 367.
Para mim isso não faz sentido. E por isso eu uso o Wolfram Alpha sem medo de ser feliz :)
Nenhum comentário:
Postar um comentário