Indução finita
A indução finita é uma técnica de demonstração matemática usada para provar que uma certa propriedade é verdadeira para todos os números naturais. Podemos usar como analogia uma fileira infinita de peças de dominó. Se dizemos que a primeira peça cai, com a garantia de que a queda de uma peça implica a queda da peça seguinte, teremos a certeza de que todas as peças cairão. Vejamos alguns exemplos:
Primeira Forma
Exemplo 1
Seja a ∈ N, e P uma propriedade, temos que:
- P(a) é verdadeira.
- Para k ≥ a, se P(k) é verdadeira, então P(k + 1) é verdadeira.
Nessas condições, P(n) é verdadeira para todo n ≥ a.
Exemplo 2
Seja a ∈ N, consideramos S o conjunto com as seguintes propriedades:
- a ∈ S.
- Para k ≥ a, se k ∈ S, então k + 1 ∈ S.
Nessas circunstâncias, S é o conjunto de todos os naturais maiores ou iguais a a.
Exemplos Resolvidos
- Dado n ∈ N, temos:
0 + 1 + 2 + … + n = n (n + 1) 2 Primeiro devemos provar que a propriedade é verdadeira para o primeiro
elemento, ou seja, o zero.0 = 0 (0 + 1) 2 = 0 Agora, assumimos que, para um k ∈ N a propriedade também é válida.
Dessa forma temos:0 + 1 + 2 + … + k = k (k + 1) 2 Vamos agora provar a propriedade para um elemento k + 1. Já sabemos provar
até um certo k.0 + 1 + 2 + … + k + k + 1 = k (k + 1) 2 + k + 1 0 + 1 + 2 + … + k + k + 1 = k (k + 1) 2 + 2 (k + 1) 2 0 + 1 + 2 + … + k + k + 1 = (k + 1)(k + 2) 2 0 + 1 + 2 + … + k + k + 1 = (k + 1)((k + 1) + 1) 2
Subconjuntos
Um subconjunto de um conjunto A é um conjunto cujos elementos são todos pertencentes ao conjunto A. Em outras palavras, se B é um subconjunto de A, então todo elemento de B também é um elemento de A. Matematicamente, isso é escrito como B ⊆ A.
Exemplos
Se A = {1,2,3}, então {1,2}, {2}, {1,3}, e até mesmo o conjunto vazio {} são
subconjuntos de A.
Quantidade de subconjuntos
A quantidade de subconjuntos de um conjunto A com n elementos pode ser
calculada usando a fórmula 2n. Isso ocorre porque cada elemento do
conjunto pode ou não estar em um subconjunto específico, resultando em 2
opções (incluir ou não incluir o elemento) para cada um dos n elementos.
Exemplo
Vamos considerar o conjunto A com 3 elementos: A = {a,b,c}.
- Conjunto vazio {}
- Subconjuntos com 1 elemento: {a}, {b}, {c}
- Subconjuntos com 2 elementos: {a,b}, {b,c}, {a,c}
- Subconjunto com todos os elementos: {a,b,c}
No total teremos 8 subconjuntos. Usando a fórmula temos 2³ = 8, onde o
expoente equivale a quantidade de elementos do conjunto. Do exposto acima
vamos analisar a correspondência com o número binomial. Dados dois números n,
p ∈ N denotamos
|
= |
|
como o número de subconjuntos de p elementos de um conjunto de n elementos. A
estrutura acima pode ser lida como “combinações de n elementos tomados p a p”.
No exemplo acima temos 3 subconjuntos com 1 elemento.
|
= | 3 |
Temos também 3 subconjuntos com 2 elementos.
|
= | 3 |
Indução Forte
Indução forte é uma variação do princípio da indução matemática, muito usada para provar afirmações sobre números naturais. A diferença entre indução fraca e indução forte está na hipótese de indução.
Diferença entre Indução Fraca e Forte:
Indução fraca: Você supõe que a propriedade é verdadeira para um número n, e prova que ela também é verdadeira para n + 1.
Indução forte: Você supõe que a propriedade é verdadeira para todos os números até n (ou seja, para 1,2,…,n), e prova que ela também é verdadeira para n + 1.
Estrutura da Indução Forte
Para provar que uma afirmação P(n) é verdadeira para todo n ≥ n0, você faz:
- Motra que P(n0) é verdadeiro.
- Supõe que P(n0), P(n0 + 1), …, P(k) são verdadeiros (hipótese de indução), e prove que P(k + 1) também é verdadeiro.
Exemplo 1
Provar que todo número natural n ≥ 2 pode ser escrito como produto de números primos.
Primeiro passo: provar que a propriedade é válida para n = 2.
2 é primo, portanto ele já é um produto de primos (ele mesmo).
Passo indutivo: suponhamos que todos os números de 2 até k podem ser escritos como produto de primos. Em seguida devemos provar que k + 1 também pode.
- Se k + 1 é primo, então ele já é um produto de primos (ele mesmo).
- Se k + 1 não é primo, então ele pode ser escrito como a * b, com 2 ≤ a, b ≤ k.
Como exemplo para visualizar melhor vamos supor que todos os números de 2 até 10 podem ser escritos como produto de primos e em seguida afirmamos que 11 também pode.
- 2 é primo, logo o produto é ele mesmo.
- 3 é primo, logo o produto é ele mesmo.
- 4 → 2 * 2
- 5 é primo, logo o produto é ele mesmo.
- 6 → 2 * 3, sendo que 2 ≤ 2,3 ≤ 10
- 7 é primo, logo o produto é ele mesmo.
- 8 → 2 * 2 * 2, sendo que 2 ≤ 2 ≤ 10
- 9 → 3 * 3, sendo que 2 ≤ 3 ≤ 10
- 10 → 2 * 5, sendo que 2 ≤ 2,5 ≤ 10
- 11 é primo, logo o produto é ele mesmo.
Exemplo 2
Considere a sequência definida pelos termos:
a1 = 1, a2 = 3, ak = ak – 2 + 2 ak – 1 com k ≥ 3.
Prove que an é ímpar para todo n ≥ 1.
Vamos escrever alguns termos dessa sequência.
a1 = 1
a2 = 3
a3 = a3 – 2 + 2 a3 – 1
a3 = a1 + 2 a2 = 1 + 2 * 3 = 7
a4 = a4 – 2 + 2 a4 – 1
a4 = a2 + 2 a3 = 3 + 2 * 7 = 17
Logo, a sequência possue a seguinte estrutura 1, 3, 7, 17, … .
Pela indução forte vamos provar para n de 1 até k. Para n = 1 e n = 2, o resultado é imediato, ou seja, a1 e a2 são ímpares.
Agora, assumimos que, para determinado k, os termos ai da sequência são ímpares, com 1 ≤ i ≤ k, e devemos provar que ak é ímpar.
Visto que nossa intensão é provar que até k os termos serão ímpares, logo ak – 2 e ak – 1 são ímpares, isto é, podem ser escritos, para certos r e s ∈ Z, como:
ak – 2 = 2r + 1
ak – 1 = 2s + 1
Logo:
ak = ak – 2 + 2 ak – 1
ak = (2r + 1) + 2(2s + 1)
ak = 2r + 1 + 4s + 2
ak = 2r + 4s + 2 + 1
ak = 2(r + 2s + 1) + 1
ak = 2t + 1, sendo t = r + 2s + 1
Portanto, ak é ímpar como objetivamos provar.