Complexidade de Algoritmos
Indução Matemática
Indução Matemática
Indução matemática é uma técnica de prova
matemática muito poderosa. Usualmente trabalha como
segue:
● Seja T um teorema que queremos provar. Suponha
que T tenha um parâmetro n cuja o valor possa ser
qualquer número Natural (inteiro positivo).
● Ao invés de provarmos diretamente que T acontece
para todos os valores de n, provamos as seguintes
duas condições:
●
Indução Matemática
Condição 1: T acontece para n = 1
●Condição 2: para todo n > 1, se T acontece para n-1,
então T acontece para n.
●
As condições 1 e 2 implicam diretamente que T acontece
para n=2.
Se T acontece para n=2 então a condição 2 implica que
T acontece para n=3 , e assim por diante.
A condição 1(base de indução) geralmente é simples de
provar.
Provar a condição 2 muitas vezes é mais fácil que provar
o teorema diretamente, assim é melhor supor que T
acontece para n-1. A suposição é chamada de hipótese
de indução.
Exemplos
Teorema 1:
●
Para todo número natural x e n, xn – 1 é divisível
por x-1.
A prova é pela indução em n.
Prova:
(Base de Indução): T é verdadeiro para n=1
uma vez que :
(x1 – 1) / (x-1) = 1 e tem resto 0
●
Exemplo
Assumindo que o teorema é verdadeiro para n-1
(hipótese de indução); nominalmente assumimos
que xn-1 – 1 é divisível por x-1 para todos números
naturais x e n.
(Hipótese de Indução) Para n > 1 T é verdadeiro
para n-1, assim temos que:
●
(xn – 1) / (x-1) = q e tem resto 0
Exemplo
Agora temos que provar que x n – 1 é divisível por
x-1. A ideia é escrever a expressão x n – 1 usando
n-1
x – 1 que pela hipótese de indução é divisivel
por x-1
Exemplo
Xn – 1 = x.(xn-1 – 1) + (x-1)
e dessa forma temos que
x.(xn-1 – 1) é divisível por (x-1)
uma vez que pela hipótese de indução temos
(xn – 1) / (x-1) = q
e assim
n
x(x – 1) / (x-1) = xq
e por fim temos que
n-1
( x.(x – 1) + (x-1) ) / (x-1) = xq+1
●
Princípio da Indução
O princípio da indução é definido como:
Se uma sentença P, com um parâmetro n, é
verdadeira para n=1, e se,
para todo n > 1 a verdade de P para n-1 implica
sua verdade para n, então P é verdadeiro para
todo número natural.
Ou seja:
Condição 1: Se P(1) é verdadeira; e
Condição 2: Se P(n-1) é verdadeira
isso implica que P(n) é verdadeira.
Principio da Indução
Às vezes podemos usar o princípio da indução
como:
Se uma sentença P, com um parâmetro n, é
verdadeira para n=1, e se,
para todo n > 1 a verdade de P para n implica sua
verdade para n+1, então P é verdadeiro para todo
número natural.
ou seja:
Condição 1: Se P(1) é verdadeira; e
Condição 2: Se P(n) é verdadeira
isso implica que P(n+1) é verdadeira.
Exemplos
Teorema 2:
A soma dos n primeiros números naturais é
n(n+1)/2.
Exemplos
Prova:
● para n=1 temos que
1 = 1(1+1) / 2
1 = 1(2) / 2
1=2/2
1=1
●
temos como hipótese que:
1+2+3+...+n-1+n = n(n+1)/2 é verdadeiro
Exemplo
então para n+1 temos
1+2+3+..+n-1+n+n+1 = ((n+1)(n+2)) / 2
● pela hipótese de indução temos que:
1+2+3+..+n-1+n = n(n+1)/2
●substituindo na expressão do lado direito da
igualdade temos
n(n+1)/2 + n+1 = ((n+1)(n+2)) / 2
● multiplicando e divindo n+1 do lado direito por 2
n(n+1)/2 + 2(n+1)/2 = ((n+1)(n+2)) / 2
● colocando (n+1) em evidência do lado direito
((n+1)(n+2)) / 2 = ((n+1)(n+2)) / 2
cqd.
●
Indução Forte
Se uma sentença P, com um parâmetro n, é
verdadeira para n=1, e se,
para todo n > 1 a verdade de P para todo número
natural < n implica sua verdade para n, então P é
verdadeiro para todo número natural.
Exercicio
Teorema 3: Se n é um número natural e 1 + x > 0,
então
n
(1+x) ≥ 1 + nx