Princípio da Indução Matemática

Prévia do material em texto

Análise Combinatória, Probabilidades e Aplicações
Curso de Verão 2024 - IME/USP
Indução matemática
Indução
A indução é uma das técnicas utilizada para demonstrar propriedades que valem para qualquer n ∈ N
(ou variações disso).
Prinćıpio da Indução. Seja P (n) uma propriedade que depende de um valor n. Assuma que
1) P (n0) é válida (caso base)
2) Para todo k ∈ {n0, n0+1, n0+2, ...}: P (k) é válida implica que P (k+1) é válida (passo indutivo)
Então, P (n) é válida para todo n ∈ {n0, n0 + 1, n0 + 2, ...}
Considerando 1) e 2) com n0 = 1 no prinćıpio da indução, vale, por exemplo, que P (483) é válida,
pois
P (1) válida =⇒ P (2) válida
=⇒ P (3) válida
...
=⇒ P (482) válida
=⇒ P (483) válida
Exemplo 1: Defina a propriedade P (n) :
∑n
i=1(2i−1) = n2. Queremos mostrar que P (n) é válida
para todo n ∈ N.
Para isso, vamos:
• Mostrar P (1) é verdadeira.
1∑
i=1
(2i− 1) = 2.1− 1 = 12
• Para todo k ∈ N: supondo P (k) verdadeira, mostrar que P (k + 1) também é verdadeira
Suponha que P (k) é verdadeira, ou seja
k∑
i=1
(2i− 1)
(∗)
= k2
Então
k+1∑
i=1
(2i− 1) =
k∑
i=1
(2i− 1) + [2(k + 1)− 1]
=
k∑
i=1
(2i− 1) + 2k + 1
(∗)
= k2 + 2k + 1
= (k + 1)2
e portanto P (k + 1) é verdadeira.
1
Exemplo 2: Seja a1 =
√
2 e an =
√
2 + an−1 para n ∈ {2, 3, ...}. Em outras palavras, a sequência
a1, a2, a3, ... é tal que 
a1 =
√
2
a2 =
√
2 +
√
2
a3 =
√
2 +
√
2 +
√
2
...
Mostre que an n2 é válida para todo n ≥ 5.
• P (5) é verdadeira, pois 25 = 32 > 25 = 52
• Seja k ≥ 5. Suponha que P (k) é verdadeira, ou seja
2k > k2
Vale que
2k+1 = 2.2k > 2.k2 = k2 + k2
(∗)
> k2 + 2k + 1 = (k + 1)2,
em que em (∗) foi utilizado que k2 > 2k + 1 (ou equivalentemente, k(k − 2) > 1), o que é válido
quando k ≥ 5.
Portanto P (n) está demonstrada para n ∈ {5, 6, 7, ...} por indução.
Prinćıpio da indução forte
Indução forte. Seja P (n) uma propriedade que depende de um valor n. Assuma que
1) P (n0) é válida (caso base)
2) Para todo k ∈ {n0, n0 + 1, n0 + 2, ...}: P (j) é válida para todo j ∈ {n0, n0 + 1..., k} implica que
P (k + 1) é válida (passo indutivo)
Então, P (n) é válida para todo n ∈ {n0, n0 + 1, n0 + 2, ...}
Ou seja, para concluir a validade de P (k + 1), podemos partir não só de P (k), mas também (se
necessário) de P (k − 1), P (k − 2), ..., P (n0).
Exemplo: Se x+ 1
x é inteiro, vale que xn + 1
xn também é inteiro para todo n ∈ N.
• x1 + 1
x1 = x+ 1
x é inteiro pela própria suposição da propriedade. Válido para n = 1
• Suponha x+ 1
x inteiro. Suponha que a propriedade é válida para {1, 2, ..., k}. Segue que
xk+1 +
1
xk+1
=
(
x+
1
x
)(
xk +
1
xk
)
−
(
xk−1 +
1
xk−1
)
.
Os termos
(
xk−1 + 1
xk−1
)
e
(
xk + 1
xk
)
são todos inteiros pela hipótese de indução. Por ser
multiplicação/subtração de inteiros, xk+1+ 1
xk+1 também é inteiro, demonstrando a propriedade.
OBS: Note que essa demonstração não funcionaria utilizando o prinćıpio da indução habitual.
2