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) (3)
•
•
A chave da demonstração por indução é encontrar um modo de relacionar o que se deseja mostrar P(k+1), equação(3), com o que hipótese de indução da P(k), da equação 2, que assumimos como verdadeira
Reescrevendo P(k+1) usando a hipótese indutiva:
1 + 3 + 5 + ... + (2k – 1) + (2(k + 1) ­ 1) =
k
2 + 2k + 2 ­ 1 =
k
2 + 2k + 1 =
2
(k + 1)
cqd
2
3
n
n+1 2. Prove que 1 + 2 + 2 + 2 + ... + 2 = 2
­ 1 (1)
para qualquer inteiro n ≥ 1
•
Passo básico
P(1) (o valor da equação (1) quando n assume o valor 1)
n+1 •
2
•
1 + 2 = 2
­ 1 = 4 ­ 1 = 3
(verdadeira)
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
3
k
k+1 1 + 2 + 2 + 2 + ... + 2 = 2
­ 1 (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 k+1+1 •
•
valor de k+1, é igual 2
­ 1 (3)
A chave da demonstração por indução é encontrar um modo de relacionar o que se deseja mostrar P(k+1), equação(3), com o que hipótese de indução da P(k), da equação 2, que assumimos como verdadeira
Reescrevendo P(k+1) usando a hipótese indutiva:
2
3
k
k+1
1 + 2 + 2 + 2 + ... + 2 + 2
2
k+1 ­ 1 + 2
k+1
2(2
1
2 (2
2
k+1
=
=
) ­ 1 =
k+1
k+1+1 ) ­ 1 =
­ 1 cqd
3. Prove que 1 + 2 + 3 + ... + n = n(n + 1)/2 (1)
para qualquer inteiro positivo n •
Passo básico
P(1) (o valor da equação (1) quando n assume o valor 1)
•
1 = 1(1 + 1)/2 = 1
(verdadeira)
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
1 + 2 + 3 + ... + k = k(k + 1)/2 (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 valor de k+1, é igual (k + 1)[(k + 1) + 1]/2 (3)
A chave da demonstração por indução é encontrar um modo de relacionar o que se deseja mostrar P(k+1), equação(3), com o que hipótese de indução da P(k), da equação 2, que assumimos como verdadeira
Reescrevendo P(k+1) usando a hipótese indutiva:
1 + 2 + 3 + ... + k + k + 1 =
k(k + 1)/2 + k + 1 =
(k
2 + k)/2 + k + 1 =
[k
2 + k + 2(k + 1)]/2 =
[k
2 + k + (k + 1)+ (k + 1)]/2 =
2 [(k
+ 2k + 1)+ (k + 1)]/2 =
(k + 1)[(k + 1)+ 1] cqd
n
4. Prove que 2 > n (1)
para qualquer inteiro positivo n •
Passo básico
P(1) (o valor da equação (1) quando n assume o valor 1)
1
•
2 > 1
(verdadeira)
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
k
•
2 > 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 k+1
•
•
valor de k+1, é igual 2
> k+1 (3)
A chave da demonstração por indução é encontrar um modo de relacionar o que se deseja mostrar P(k+1), equação(3), com o que hipótese de indução da P(k), da equação 2, que assumimos como verdadeira
Reescrevendo P(k+1) usando a hipótese indutiva:
2
k+1
k = 2.2
k
2 > k
k 2.2
2
k+1
> 2.k = k + k ≥ K + 1, logo > k+1 cqd
2n
5. Prove que o número 2 – 1 (1)
para qualquer inteiro positivo n é divisível por 3
•
Passo básico
P(1) (o valor da equação (1) quando n assume o valor 1)
2.1
•
2
– 1 = 3
(verdadeira)
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
2k
•
2k
2 – 1 = 3.m 2 = 3.m + 1
(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(k+1)
•
•
valor de k+1, é igual 2
= 3.n (3)
A chave da demonstração por indução é encontrar um modo de relacionar o que se deseja mostrar P(k+1), equação(3), com o que hipótese de indução da P(k), da equação 2, que assumimos como verdadeira
Reescrevendo P(k+1) usando a hipótese indutiva:
2(k+1)
2k+2 2k
2 2k 2
– 1 = 2
– 1 = 2 .2 – 1 = 4.2
4.(3m + 1) ­ 1 = 12m + 4 – 1 = 12m + 3 =
3(4m + 1) = 3n
cqd – 1 =
INDUÇÃO COMPLETA OU INDUÇÃO FORTE

Princípio da Indução Matemática (INDUÇÃO FRACA):
•
P(1) verdadeira
•
(∀k)[P(k) verdadeira → P(k+1) verdadeira]
•
ENTÃO P(n) verdadeira para todos os n inteiros positivos

INDUÇÃO COMPLETA ou INDUÇÃO FORTE
1. P(1) verdadeira
2. (∀k)[P(r) verdadeira para todo r, 1 ≤ r ≤ k,
→ P(k+1) verdadeira]
ENTÃO P(n) verdadeira para todos os n inteiros positivos

Em algumas situações não conseguimos realizar uma demonstração por indução usando apenas a indução fraca. Nesses casos o uso da INDUÇÃO FORTE é absolutamente necessário.

Prove que para todo n ≥ 2, n é um número primo ou é um produto de números primos.
○ Porque não podemos usar a INDUÇÃO FRACA?
■ Propriedade: Todo inteiro n ≥ 2 é um número primo ou é um produto de números primos.
■ Usando a indução fraca:
•
Base: 2 é primo
VERDADE
•
Hipótese indutiva: k é primo ou produto de primos
 se k é primo, tudo bem
 se k NÃO É PRIMO, então k=a.b onde a e b são primos ou produtos de primos
 a e b devem estar nos intervalos: 1<a<k e 1<b<k, respectivamente, caso contrário, isto é, se 1≤ a≤ k e 1≤b≤k, e k=a.b, então k é primo (uma contradição)
 Logo, a< k e b< k
 De onde se conclui que precisamos de uma hipótese indutiva que possa valer para inteiros menores que k; na verdade, para inteiros no intervalo (fechado) [2,k]
 Isso nos obriga a tentar a INDUÇÃO FORTE, como descrito a seguir.
○ Base:
■ 2 é primo ou produto de primos. VERDADE
○ Hipótese indutiva: Vamos supor que para qualquer r no intervalo 2 ≤ r ≤ k, P(r) é verdadeira, isto é, r é primo ou é produto de números primos.
○ Tomemos agora o número k+1.
■ Se k+1 é primo, o resultado se verifica.
■ Se k+1 não é primo, então ele é um número composto e pode ser escrito como k+1=a.b, onde 1<a< k+1 e 1<b< k+1, ou 2≤a≤ k e 2≤b≤ k. Observe que a hipótese indutiva se aplica a a e b. Logo, ou a e b são primos ou são produto de primos. Isso verifica P(k+1) C.Q.D. (Como Queríamos Demonstrar)

Prove que qualquer valor postal maior ou igual a oito unidades monetárias pode ser obtido usando­se apenas selos com valores de 3 e 5. Em outras palavras, um inteiro positivo n, para todo n ≥ 8, pode ser representado como a soma de 3s e 5s
○ Porque não podemos usar a INDUÇÃO FRACA?
■ Propriedade: Todo inteiro n ≥ 8 pode ser representado como a soma de 3s e 5s
■ Usando a indução fraca:
•
Base: 8 = 3 + 5
VERDADE
•
Hipótese indutiva: k pode ser representado como a soma de 3s e 5s
 vamos verificar se k + 1 pode ser representado como a soma de 3s e 5s
 k + 1 = [(soma de 3s e 5s) + 1] ≠ (soma de 3s e 5s)  não consigo realizar a demostração indutiva considerando verdadeira a hipotese apenas para o item imediatamente anterior (k)
 é necessário considerar a hipótese verdadeira para um inteiro menor que k
 isso nos obriga a tentar a INDUÇÃO FORTE, como descrito a seguir.
○ Base: a base, por motivos óbvios será o 8. P(8) é a sentença de que 8 resulta da soma de 3s e 5s. De Fato, 8 = 3 + 5 e P(8) é verdadeira.
○ Hipótese indutiva: Vamos supor agora que para qualquer r, 8 ≤ r ≤ k, P(r) é verdadeira, isto é, P(r) é a sentença de que r resulta da soma de 3s e 5s.
○ Vejamos agora o ocorre com k+1. Queremos mostrar que k+1 pode ser representado como a soma de 3s e 5s. Então, para usar a hipótese indutiva, isto é, usar o fato de que a propriedade é verdadeira para r, onde 8 ≤ r ≤ k, devo considerar um inteiro menor que k
○ A fim de que a hipótese indutiva (8 ≤ r ≤ k) seja verdadeira, é necessário que (k+1)­3 ≥ 8. Assim k+1 precisa ser ≥ 11. Logo não podemos usar a hipótese indutiva para verificar P(9) e P(10). Mas podemos verificar P(9) e P(10) diretamente.
■ P(9) = 3 + 3 + 3
■ P(10) = 5 + 5
○ Uma vez que P(r) é verdadeira para 8, 9 e 10 (8 ≤ r ≤ k), podemos assumir que k+1 é no mínimo 11, isto é, k+1 ≥ 11.
■ (k+1) ­ 3 ≥ (11 – 3)
■ (k–2) ≥ 8
■ Pela H.I. P(r) é verdadeira para 8 ≤ r ≤ k
■ Logo P(k­2) é verdadeira (pode ser escrita como a soma de 3s e 5s)
■ (k­2)+3 = soma de 3s e 5s
■ (k­2+3) = k + 1 = soma de 3s e 5s c.q.d