Como você provaria que \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\) é verdadeiro para todo número natural? Verificar caso por caso é impossível: os naturais são infinitos. Precisamos de um argumento diferente — um que percorra todos os casos de uma só vez.
Essa é a questão central desta série, e a resposta é o Princípio de Indução Matemática.
O que você vai aprender #
O artigo Indução Matemática: Provando Propriedades para Todos os Naturais apresenta a estrutura clássica da prova por indução — base, hipótese indutiva e passo — com exemplos completos de somas, produtos e divisibilidade. Inclui também a versão generalizada com base em \(n_0 \neq 1\).
Já o artigo Indução Forte: Quando o Passo Precisa de Mais Contexto estende o método clássico para situações onde o passo \(k+1\) depende de múltiplos casos anteriores. A sequência de Fibonacci, a prova da decomposição em primos e a Fórmula de Binet ilustram quando — e por que — a hipótese mais forte é necessária.
Por fim, o artigo Relações de Recorrência: Definindo Sequências por si Mesmas generaliza a ideia de recorrência: como montar a equação que descreve uma sequência e como resolvê-la pelo método de substituição para obter fórmulas fechadas. A Torre de Hanoi, as expressões aritméticas válidas e o problema dos ovais no plano são os exemplos centrais. O artigo apresenta ainda a equação característica, técnica sistemática para resolver recorrências de ordem 2 — aquelas em que cada termo depende dos dois anteriores, como Fibonacci.
Por que indução e recorrência? #
A indução matemática e as relações de recorrência aparecem em praticamente todo o restante da matemática discreta:
- Análise de algoritmos: a complexidade do MergeSort satisfaz \(T(n) = 2T(n/2) + n\) — uma recorrência que determina que o algoritmo é \(O(n \log n)\).
- Combinatória: as fórmulas de combinação e os coeficientes do Binômio de Newton têm provas naturais por indução.
- Grafos: propriedades de árvores (número de arestas, caminhos) são provadas por indução na quantidade de vértices.
- Teoria dos números: divisibilidade, fatoração em primos e a própria estrutura dos naturais dependem do princípio indutivo.
Dominar essas ferramentas é indispensável para raciocinar com precisão sobre estruturas discretas.
Pré-requisitos #
Familiaridade com números naturais, álgebra básica e a notação de somatório (\(\sum\)). A série anterior — A Linguagem dos Conjuntos — cobre os fundamentos de teoria dos conjuntos, mas não é pré-requisito estrito para este material.
Se quiser entender o plano geral das séries de Matemática Discreta do site — quais tópicos serão cobertos, por que foram escolhidos e qual a motivação por trás deles — o artigo Matemática Discreta: Apresentação e Roadmap traça o mapa completo das quatro séries previstas.
Até a próxima!
