Como provar afirmações sobre infinitos casos de uma só vez? Esta série cobre o
Princípio de Indução Matemática, a Indução Forte e as Relações de Recorrência —
ferramentas essenciais para raciocinar sobre sequências e algoritmos recursivos.
Os artigos são listados abaixo, na ordem em que foram escritos.
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.
Se o primeiro dominó cai e cada dominó derruba o seguinte, todos caem. Essa é a lógica do Princípio de Indução Matemática. Veremos a estrutura da prova (base, hipótese e passo) em somas, divisibilidade e desigualdades, e a falsa prova de que todos os cavalos têm a mesma cor.
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.
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.
