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 k 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 |