Quantos movimentos resolvem a Torre de Hanói? A resposta sai de uma relação de recorrência, que escreve o problema em função dele mesmo com um disco a menos. Montamos recorrências e as resolvemos por substituição, pela equação característica e pelo Teorema Mestre, usado no merge sort.
E quando o passo depende de mais de um caso anterior, como em Fibonacci? A indução forte assume todos os casos anteriores. Veremos a técnica na decomposição em primos, na barra de chocolate, no franqueio postal e na fórmula de Binet, que em ponto flutuante erra a partir do 71º termo.
Como provar que uma fórmula vale para todos os números naturais, se eles são infinitos? Com a indução matemática. Esta apresentação mostra o caminho da série: indução clássica, indução forte e relações de recorrência, de Fibonacci à Torre de Hanói.
