Indução

Indução Matemática


Princípio da Indução Matemática:
•
P(1) verdadeira
•
(∀k)[P(k) verdadeira → P(k+1) verdadeira]
•
ENTÃO P(n) verdadeira para todos os n inteiros positivos



O Princípio da Indução Matemática é uma implicação, cuja tese é: “Uma sentença da forma P(n) é verdadeira para todos os inteiros n positivos”.
Portanto, quando desejarmos demonstrar que alguma propriedade é válida para qualquer inteiro positivo n,podemos tentar usar a indução matemática como técnica de demonstração.





Demonstração por indução:
•
estabelecemos inicialmente a veracidade da sentença P(1), que é chamada BASE DA INDUÇÃO ou PASSO BÁSICO DA INDUÇÃO
•
Estabelecer que P(k) → P(k+1), que é chamado PASSO
INDUTIVO
•
P(k) é chamada SUPOSIÇÃO INDUTIVA ou HIPÓTESE INDUTIVA quando assumimos que P(k) é verdadeira com o objetivo de demonstrar o passo indutivo



A indução, apesar do nome, é uma técnica de demonstração dedutiva, isto é, uma forma de demonstrar uma conjectura que possivelmente foi formulada por um raciocínio indutivo.



EXEMPLOS:
2

1. Prove que 1 + 3 + 5 + ... + (2n – 1) = n
(1)
para qualquer inteiro positivo n
•
A propriedade P(n) é a equação (1) acima (a soma de todos os inteiros positivos ímpares menores que n são igual ao quadrado de n)
•
Podemos provar que a equação (1) é verdadeira para um determinado valor de n, pela substituição de n na equação. Contudo não poderemos substituir todos os valores inteiros positivos.
•
Demonstração por indução matemática:
•
Passo básico
P(1) (o valor da equação (1) quando n assume o valor 1)
2

•

1 = 1
Hipótese de indução: assuma que P(k) é verdadeira para um inteiro positivo arbitrário k, que é o valor da equação (1) quando n vale k, ou seja
2

•

1 + 3 + 5 + ... + (2k ­ 1)= k
(2)
Usando a hipótese de indução, queremos mostrar que
P(k+1), que é o valor da equação (1) quando n assume o
2

valor de k+1, é igual (k+1)