Seja P(n) uma sentença aberta sobre N, e seja a in N. Suponha que:
i. P(a) é verdadeira, e
ii. qualquer que seja n in N, com n >= a, sempre que P(n) for verdadeira, segue-se que P(n+1) é verdadeira.
Então, P(n) é verdadeira para todo número natural n >= a.
Use a técnica de demonstração apresentada no item (a) e prove que n!>2^n, para todo n in N com n >= 4.

Passo 1

Beleza, vamos recapitular a parada. A questão quer que a gente use indução (esse esquema que diz “se P(a) é verdade e P(n) ⇒ P(n+1), então P(n) vale pra todo n≥a”) para provar que
P(n): “
é verdade para todo com .
O que precisamos saber:
  • Definição de fatorial: .
  • Propriedade de potências: .
  • Esquema de indução: base (checar o caso inicial) + passo indutivo (assumir P(n) e provar P(n+1)).

Passo 2

Base da indução ( 4! = 1cdot2cdot3cdot4 = 24, 2^4 = 16).
Calcular:
Logo, .
Então P(4) é verdadeira.

Passo 3

Hipótese indutiva.
Suponha que para algum k! > 2^k valha P(k), ou seja:

Passo 4

Passo indutivo: provar P(k+1).
Começamos com a definição de fatorial:
(k+1)! = (k+1)times k!
Pela hipótese indutiva (k+1)! = (k+1),k! > (k+1),2^k , então
(k+1),2^k > 2cdot2^k = 2^k+1
Agora, como (k+1)! > (k+1),2^k > 2^k+1, temos , e aí . Multiplicando por um número maior que 2, a gente obtém algo maior que . Ou seja,
Juntando tudo:
que é exatamente P(k+1).

Resposta

Pela base n! > 2^n e pelo passo indutivo, concluímos por indução que
para todo com .

Exercícios relacionados