Universidade Tecnológica Federal do Paraná
Professor Murilo V. G. da Silva
Notas de aula – Matemática Discreta (Aula 03)
Na aula passada assumimos que dada uma proposição P , podemos usar a “técnica” de indução para fornecer
uma prova para P . A técnica consistia em 3 passos: (1) Base (2) Hipótese de indução (3) Passo indutivo.
Por quê isso é verdade? As outras duas técnicas de demonstração (prova direta e prova por contradição)
são embasadas em mecanismos de dedução lógica (visto no Curso de Introdução a Lógica), mas a técnica da
indução é um pouco menos óbvia e precisamos nos convencer que ela funciona. Discutimos em sala a noção
intuitiva de que uma prova por indução funciona como uma “reação em cadeia” e este é um argumento bem
razoável. Ainda assim, vamos fornecer a seguir um argumento mais formal para nos convencermos que a técnica
da indução é uma forma válida de se provar teoremas.
Indução: Seja uma proposição P sobre os números naturais. Se for verdade que:
(i) P (0) é verdadeiro.
(ii) ∀k ∈ N, se P (k) é verdadeiro, então P (k + 1) é verdadeiro.
Então podemos concluir que ∀n ∈ N, P (n) é verdadeiro.
Prova: Provaremos por contradição. Suponha que (i) e (ii) são ambos verdadeiros, mas a conclusão é falsa,
ou seja, ∃n ∈ N, P (n) é falso. Seja S = {x ∈ N; P (x) é falso }. Como S 6= ∅, S contém um menor elemento
n0 . Como (i) é verdadeiro x0 > 0, e portanto x0 − 1 ∈ N. Como x0 é o menor elemento de S, então P (x0 − 1) é
verdadeiro. Com isso temos que pois P (x0 − 1) é verdadeiro e P (x0 ) é falso, contradizendo o item (ii) que diz
que ∀k ∈ N, P (k) → P (k + 1).
Observe que na demostração anterior, usamos o seguinte argumento: Como S 6= ∅, S contém um menor
elemento x0 . Este argumento é conhecido como princı́pio da boa ordenação. Como ele parece algo óbvio
demais para ser provado ele é em geral considerado um “axioma” quando lidamos com números naturais. Por
isso, em geral chamamos este argumento de “princı́pio” ao invés de “teorema”. Formalmente temos:
O princı́pio da boa ordenação: Dado X ⊆ N. Se X 6= ∅, então X contém um menor elemento.
Entretando, poderı́amos ter assumido como princı́pio que o raciocı́nio indutivo é algo que “não precisa ser
provado”. De fato, se tivéssemos feito isso, então poderı́amos ter invertido os papéis e provado, a partir do
princı́pio da indução, que a boa ordenação é um argumento válido. Com isso, temos que os dois conceitos são
na realidade equivalentes.
Para finalizar, observamos que desde a aula passada, vı́nhamos nos referindo prinı́pio da indução como
“técnica da indução”. Na realidade essa terminologia é bem incomum e não será utilizada no restante do curso.
De agora em diante em nossas provas por indução diremos que estamos usando o Princı́pio da Indução.
1
Agora que estamos familiarizados com o princı́pio da indução, vamos apresentar um “segundo” princı́pio da
indução. Este segundo princı́pio, também conhecido como:
Princı́pio da Indução Forte: Seja uma proposição P sobre os naturais. Se for verdade que:
(i) P (0) é verdadeiro.
(ii) ∀k ∈ N, se P (r) é verdadeiro para todo 0 ≤ r ≤ k, então P (k + 1) é verdadeiro.
Então podemos concluir que ∀n ∈ N, P (n) é verdadeiro.
Prova: Exercı́cio.
Abaixo um teorema extremamente importante que pode ser provado usando indução forte:
Teorema Fundamental da Aritmética: Todo número natural maior que 1 pode ser decomposto em fatores
primos (ou seja, ∀n > 1, n = p1 · p2 · ... · pk , onde pi é primo, i = 1, 2, ..., k).
Prova: Vista em sala de aula.
A seguir um exemplo de um teorema que podemos provar usando indução forte. Note que neste exemplo
precisamos provar mais de um caso base:
Teorema: Se n é um número natural maior que 8, então ∃i, j ∈ N tal que n = 3i + 5j.
Prova: Vista em sala de aula.
2