Exemplos de Indução
Matemática
Matemática Discreta
Exemplo1: Provar por indução que P(n) : n < 2n
a) P(1) é a proposição 1 < 21, que certamente é verdade.
b) Supondo (hipótese de indução) agora P(k): k < 2k,
tentamos concluir que P(k + 1): k + 1 < 2k + 1.
Lembrando que 2k + 1 = 2k.2
Usando a hipótese da indução k < 2k
E multiplicando os dois membros dessa desigualdade por 2,
Obtemos:
2 . k < 2. 2k
Tem-se que: 2 . k = k + k e 2 . 2k = 2k + 2k
Logo, k + k = 2k + 2k = 2k+1
Como k + 1 < k + k então, k + 1 < 2k + 1
Exemplo 2 : Prove que a equação 1+3+5+...+(2n-1) = n2 (1)
É verdadeira para qualquer inteiro positivo n.
a) P(1): 1 = 12
b) P(k): 1+3+5+...+(2k-1) = k2 (2)
P(k+1): 1+3+5+...+[(2(k+1)–1] = (k+1)2 (3)
A chave de uma demonstração por indução é encontrar um modo de
relacionar o que queremos saber (3) e o que supusemos(2).
O lado esquerdo de (3) pode ser reescrito mostrando-se a penúltima
parcela:
1+3+5+...+(2k-1) +[(2(k+1) -1] está equação contém
o termo a esquerda do sinal de igualdade da equação (2).
Como estamos supondo que P(k) é válida, então:
1+3+5+...+[2(k+1) -1] = 1+3+5+...+(2k-1) + [2(k+1) – 1]
= k2 + [2(k + 1)- 1]
= k2 + (2k +2 -1)
= K2 + 2K + 1
= (k + 1)2
Portanto,
1+3+5+...+[2(k + 1) – 1] = (k + 1)2