Técnicas de Demonstração, Indução e Teoria dos Números

2.1 TÉCNICAS DE DEMONSTRAÇÃO

Nesta seção aprendemos formas formais de transformar uma conjectura em teorema dentro de um contexto específico. Em vez de provar universalmente, muitas vezes queremos demonstrar que P → Q é verdadeiro sob hipóteses relevantes do contexto. Veremos várias técnicas úteis.

Provar ou não Provar

Um contraexemplo é suficiente para mostrar que uma conjectura é falsa. Às vezes uma conjectura parece verdadeira para muitos casos, mas falha em algum exemplo.

• Exemplo: n! ≤ n^2 falha em n = 4 (24 ≤ 16 é falso).

Demonstração por Exaustão

Usada apenas se o conjunto de casos for finito. Prova-se P → Q verificando cada elemento da coleção.

Observação prática: funciona para problemas com número finito de casos, mas não para generalizações.

Demonstração Direta

Suponha P e deduza Q passo a passo. É a abordagem padrão.

Exemplo informal: “Se x e y são pares, então xy é par” — escrevemos x = 2m, y = 2n e concluímos xy = 2(2mn).

Contraposição

Se não é fácil provar P → Q diretamente, prove Q′ → P′. Então, por tautologia, P → Q é verdadeiro.

Exemplo: Se n^2 é ímpar, então n é ímpar. Provar que n é par implica n^2 é par, pela contraposição.

Por Absurdo

Suponha P ∧ Q′ e deduza uma contradição. Assim, P → Q é verdadeiro.

Este método é útil para mostrar que uma conclusão não pode ser falsa sob a hipótese dada.

Acidentes Felizes

Observações engenhosas que às vezes surgem incidentalmente durante a prova, levando a soluções elegantes (ex.: soma de partidas em um torneio)

Dicas rápidas

Lembrete: teoremas são enunciados com P → Q, e muitas demonstrações úteis combinam diferentes técnicas.

Exemplos e Exercícios relevantes

Exemplo 4 demonstração direta de que o produto de dois inteiros pares é par, formalmente.

Exemplo 5 demonstração informal direta: se x = 2m e y = 2n, então xy = 2(2mn).

Exercícios rápidos

Ver também os problemas práticos de 2.1 para prática de contraposição, absurdo, etc.

Observação prática

Em muitos casos, uma demonstração informal já é suficiente, desde que as hipóteses e a conclusão estejam claras e fundamentadas pela definição (quando necessário).

2.2 Indução Matemática

A indução matemática é uma técnica poderosa para provar propriedades que valem para todos os inteiros positivos (ou para todos os n em um intervalo).

Princípio da Base

Mostra que a proposição P(n) é verdadeira para o caso inicial (geralmente n = 0 ou n = 1).

Passo de Indução

Suponha que P(k) seja verdadeira para um k arbitrário. Então prove que P(k+1) é verdadeira com base nessa suposição. Isso completa o passo indutivo.

Primeiro Princípio de Indução

Usado quando a propriedade é demonstrada para o primeiro caso e, assumindo que funciona para n, mostra-se que funciona para n+1.

Segundo Princípio de Indução

Semelhante ao primeiro, mas pode envolver demonstrar P(n) assumindo que P(0), P(1), ..., P(n) são verdadeiras (indução sobre o completo conjunto de casos menores que n).

Exemplo simples

Provar que a soma dos primeiros n inteiros é n(n+1)/2 por indução em n.

Base: para n = 1, 1 = 1(1+1)/2. Passo: assume que S(k) = k(k+1)/2 e mostra S(k+1) = (k+1)(k+2)/2.

2.3 Demonstração de Correção com Laços

Quando se escreve programas que utilizam laços, a demonstração da correção envolve raciocínio sobre invariantes de laço.

Conceito-chave: invariantes de laço

Um invariantes de laço é uma propriedade que é verdadeira a cada iteração do laço e útil para provar a corretude do programa, incluindo a saída esperada ao final do laço.

Exemplo típico

Suponha um laço que soma os primeiros n inteiros. O invariante pode ser: “ao final de cada iteração i, a soma até i é correta”. Assim, ao terminar, a soma até n é correta.

2.4 Teoria dos Números: fatoração, MDC e φ de Euler

Nessa parte aprendemos conceitos elementares de teoria dos números. Principais tópicos abordados:

• Fatoração em primos: cada inteiro > 1 pode ser escrito como produto de primos (unicamente, até ordem). Ex.: 360 = 2^3 × 3^2 × 5.
• Número primo: inteiro maior que 1 que só é divisível por 1 e por si mesmo.
• Número composto: não primo; pode ser escrito como produto de inteiros estritamente maiores que 1.
• Máximo divisor comum (MDC): maior inteiro que divide dois inteiros sem deixar resto.
• Função fi de Euler φ(n): número de inteiros entre 1 e n que são coprimos com n (gcd(k, n) = 1).

Exemplo prático com MDC: Doação: 792 sabonetes e 400 frascos de xampus. Para embalar de modo que cada pacote tenha o mesmo número de frascos e sabonetes, a quantidade de pacotes é o MDC(792, 400) = 8. Observação: isso equivale a distribuir cada tipo de item em quantidades iguais por pacote.

Exemplo com φ: Se n = 12, então φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 4. Logo, existem 4 inteiros coprimos com 12 no intervalo [1, 12].

Mapa mental (Resumo visual)