Demonstração por Indução

Escolha uma proposição sobre cada número natural n. Cada dominó abaixo é um n, colorido consoante a proposição seja verdadeira nesse ponto, verificada diretamente. A seta que sai de um dominó é o passo indutivo de n para n + 1. Apenas um dominó base verdadeiro com uma cadeia ininterrupta de setas a seguir constitui uma demonstração, e os dominós que essa cadeia alcança caem.

Exemplo resolvido — Demonstração por Indução

Passo de 1 para 2	falha
Demonstrado, para n até 12	1
Primeiro n falso, até 12	2

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Demonstração por Indução

A Demonstração por indução demonstra uma proposição P(n) para cada número natural n a partir de um certo n₀, em duas partes: o caso base, P(n₀) verificado diretamente, e o passo indutivo, um argumento de que P(k) implica P(k + 1) para todo o k ≥ n₀. Juntos alcançam cada n, tal como cada dominó que cai derruba o seguinte.

O que significa cada símbolo

P(n): a proposição sobre n; em cada n é simplesmente verdadeira ou falsa
n₀: o caso base, onde a demonstração começa, verificado manualmente
k: um n genérico dentro do passo: o argumento assume P(k) e deve chegar a P(k + 1)

De onde vem a fórmula

Por que razão as duas partes são suficientes. Suponha que o caso base se verifica e o passo funciona para cada k ≥ n₀, mas P é falso nalgum ponto a partir de n₀. Entre os n onde é falso existe um menor; chamemos-lhe m. Não é n₀, porque P(n₀) foi verificado, logo m − 1 ≥ n₀, e P(m − 1) é verdadeiro porque m era a menor falha. O passo fornece então P(m), o que contradiz o facto de P(m) ser falso. Por conseguinte, não há falhas. Ambas as partes são utilizadas: sem a base, m poderia ser n₀; se faltasse o passo num único k, m poderia ser k + 1.
Por que razão n² + n + 41 tinha de falhar. Em n = 40 os primeiros dois termos combinam-se, 40² + 40 = 40 × 41, de modo que 40² + 40 + 41 = 40 × 41 + 41 = 41 × 41. Em n = 41 todos os termos são múltiplos de 41, e o valor é 41 × 43. A ideia vai mais além: nenhum polinómio não constante com coeficientes inteiros pode gerar apenas números primos, por muitos que produza inicialmente (Lehman, Leighton e Meyer demonstram-no no Problema 1.25). Portanto, nunca poderia ter existido um passo indutivo para esta proposição.
2ⁿ > n² para cada n ≥ 5, feito corretamente. Caso base: 2⁵ = 32 > 25 = 5². Passo: seja k ≥ 5 e assuma que 2ᵏ > k². Então 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k². Dado que k ≥ 5, k² ≥ 5k = 2k + 3k > 2k + 1, logo 2k² > k² + 2k + 1 = (k + 1)², e 2ᵏ⁺¹ > (k + 1)², que é P(k + 1). O próprio passo apenas necessita de k ≥ 3. A base teve de ser 5 porque P(2), P(3) e P(4) são falsas.

Quarenta casos verdadeiros, depois 41 × 41 🖖

Selecione n² + n + 41. Os valores 41, 43, 47, 53, 61, … são primos para cada n de 0 a 39, quarenta seguidos, e em n = 40 o valor é 1.681 = 41 × 41. Consegue-se prever o resultado ao observar com atenção: 40² + 40 + 41 = 40 × 41 + 41. O gráfico não tem setas porque não existe passo. Saber que p(39) = 1.601 é primo não diz nada sobre p(40), que é p(39) + 80. Dos primeiros mil valores 581 são primos, razão pela qual o padrão é tão persuasivo.

O passo para 2ⁿ > n² funciona desde k = 3; a proposição apenas desde n = 5 🖖

Selecione 2ⁿ > n² desde 1. O caso base verifica-se, visto que 2 > 1. O passo diz que se 2ᵏ > k², então 2ᵏ⁺¹ > 2k², e 2k² ≥ (k + 1)² exatamente quando k² ≥ 2k + 1, o que é verdadeiro desde k = 3. Logo, a partir de n₀ = 1 as setas que saem de 1 e de 2 estão quebradas, e a proposição é falsa em 2, 3 e 4. As setas que saem de 3 e de 4 funcionam enquanto P(3) e P(4) são ambas falsas: um passo correto com um dominó falso atrás não empurra nada. Selecione 2ⁿ > n² desde 5 e as mesmas setas demonstram todos os n de 5 em diante.

O argumento dos cavalos está certo em cada passo exceto num 🖖

Selecione Os cavalos. O passo leva n + 1 cavalos, aplica a proposição aos primeiros n e aos últimos n, e une-os através dos cavalos que os dois grupos partilham. A partir de n = 2 isso funciona, e todas as setas de 2 em diante são sólidas. De 1 para 2 os grupos têm um cavalo cada e não partilham nenhum, pelo que o argumento não demonstra nada no único lugar onde é necessário. Se colocar a base em 5, cada passo funcionará, mas P(5) é falso e a cadeia não tem nada para empurrar.

Problema resolvido na íntegra

A partir de que valor 2ⁿ se mantém superior a n³? 4 passos
Demonstre que 2ⁿ > n³ para qualquer n suficientemente grande. O passo é fácil de formular. Onde começa a funcionar e onde deve estar o caso base?

Abrir este problema na ferramenta
1. Assuma P(k): 2ᵏ > k³. Dobrar é o único movimento disponível:
  
  $2^{k} > k^{3} \Rightarrow 2^{k + 1} = 2 \cdot 2^{k} > 2 k^{3}$
2. Logo o passo funciona quando 2k³ ≥ (k + 1)³. Divida ambos os lados por k³:
  
  $2 k^{3} \geq (k + 1)^{3} ⟺ (1 + \frac{1}{k})^{3} \leq 2 ⟺ k \geq \frac{1}{3 2 - 1} = 3.847$
3. O passo funciona desde k = 4, não de 3:
  
  $k = 3 : 2 \cdot 27 = 54 < 64 = 4^{3}, k = 4 : 2 \cdot 64 = 128 \geq 125 = 5^{3}$
4. Mas a própria proposição é falsa de n = 2 a n = 9. O caso base é o primeiro n onde volta a ser válida:
  
  $2^{9} = 512 < 729 = 9^{3}, 2^{10} = 1, 024 > 1, 000 = 1 0^{3}$
Resposta

2ⁿ > n³ verifica-se para cada n ≥ 10, e em n = 0 e 1. O passo funciona desde k = 4, portanto, para k = 4 a 9, um passo correto encontra-se atrás de uma proposição falsa, tal como acontece com 2ⁿ > n² em 3 e 4 nesta página. Selecione 2ⁿ > n² desde 5 para comparar.

$2^{n} > n^{3} for every n \geq 10 (and n = 0, 1); step from k = 4, base n_{0} = 10$

Percurso de aprendizagem

Métodos de demonstração

Referências (3)

Both of this page's broken arguments, worked through: n² + n + 41 prime through n = 39 and 41·41 at n = 40 (§1.1), and the horses, whose failure the text pins to the one step P(1) → P(2) (§5.1): E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §1.1 and §5.1.
The primes n² + n + 41 takes, with the forty consecutive prime values from n = 0 to 39: OEIS Foundation, "A005846: Primes of the form k² + k + 41", The On-Line Encyclopedia of Integer Sequences.
Where the horses come from: George Pólya posed the argument as an induction exercise in 1954: ProofWiki, "All Horses are the Same Colour/Historical Note", citing G. Pólya, Induction and Analogy in Mathematics (Princeton University Press, 1954).

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.