Indução matemática: como se faz?

Entenda o significado da indução matemática, a sua origem e como aplicá-la corretamente para provar teoremas que envolvem números naturais.

Origem da indução matemática

Podemos definir da maneira mais simplificada possível a indução matemática (também conhecida como indução finita) como o processo que busca provar um determinado teorema ou propriedade que envolve números naturais (N = {0, 1, 2, 3, 4, 5, 6, …}).

Antes de abordá-la, vamos analisar a aplicação da técnica de indução vulgar, que era a maneira usual de se provar teoremas antes da existência da indução matemática. Para tanto, vamos analisar o teorema do número de Fermat. O teorema define que:

= um número primo, para qualquer valor de n

O matemático Pierre de Fermat tentou provar o seu teorema de números primos, no século XVII, através desse método. Veja abaixo:

é igual a 3 e 3 é um número primo
é igual a 5 e 5 é um número primo
é igual a 17 e 17 é um número primo
é igual a 257 e 257 é um número primo
é igual a 65537 e 65537 é um número primo

A princípio parece que temos um padrão, uma regra aparente. Parece que a fórmula proposta sempre gera números primos. Mas será que essa regra se mantém para todos os infinitos possíveis valores de n?

A princípio, o teorema era considerado verdadeiro apenas pela demonstração dos quatro primeiros valores dos números naturais (indução vulgar). Até que em 1732 o matemático Leonhard Euler mostrou o que se chama em matemática de contraexemplo. Euler calculou o resultado do número de Fermat para n = 5:

Acontece que este valor encontrado por Euler não é um número primo, pois pode ser representado como 641 × 6.700.417. Vale ressaltar que estamos falando de uma época em que não havia computadores e nem máquinas de calcular!

Este contraexemplo derrubou o teorema do número de Fermat e mostrou o equívoco de tentar provar propriedades de números naturais através da demonstração de alguns valores. Isso mostra não só a importância de não se considerar resultados iniciais aparentes, mas também a importância de utilizar métodos logicamente corretos para provar fórmulas e teoremas.

Algumas fórmulas e teoremas

Para compreender o processo de indução matemática, precisamos visualizar alguns teoremas sobre os quais podemos aplicá-la.

Somatório da progressão aritmética

O teorema propõe uma formula fechada para a soma consecutiva dos n primeiros números naturais positivos não nulos:

Somatório dos n primeiros números ímpares

O teorema propõe uma formula fechada para a soma consecutiva dos n primeiros números naturais ímpares, positivos e não nulos:

Número piramidal quadrado

O teorema propõe uma formula fechada para a soma consecutiva do quadrado dos n primeiros números naturais positivos não nulos:

Contudo, sabemos que não é possível testar todos os valores possíveis de n para provar a validade desses teoremas, pois os números naturais são infinitos!

Obs: Você deve ter percebido o uso do símbolo de somatório ∑ (letra sigma) nas fórmulas expressas acima. Se você ainda não sabe o que é um somatório, clique aqui e acesse o artigo onde te explicamos detalhadamente sobre o assunto.

Definição da indução matemática

A indução matemática é uma técnica utilizada para provar uma determinada propriedade que envolve todos os infinitos números naturais. Ela é composta por dois princípios básicos: a base e o passo indutivo. Primeiro, começamos provando a base:

Base:

T(n0)

Precisamos apenas provar que o teorema é válido para um número n inicial qualquer.

Após testada a base, realizamos o passo indutivo, onde verificamos se o teorema é válido para um determinado valor k (hipótese), e depois verificamos se ele também é válido para o próximo valor k+1 (Tese):

Passo indutivo:
Hipótese:
Se ele também é valido para um determinado valor k.
Tese:
Ele também deve ser válido para o próximo valor ( k+1).

Simples assim! A base e o passo indutivo representam as etapas realizadas durante o processo de indução. Mostramos que o teorema é válido para um valor n0 inicial e depois mostramos que ele também é válido para um valor k e para o próximo valor k+1. Mas como assim?

Imagine um efeito dominó: se é válido para 1 é válido para 1+1, ou seja, é válido para 2. Mas se é válido para 2 é válido para 2+1, ou seja, é válido para 3. Mas se é válido para 3 é válido para 3+1… Em resumo, se o teorema é válido para um número  e o seu sucessor, então o efeito dominó está provado e o teorema é valido para todos os infinitos números naturais.

Parece até brincadeira de criança, mas acredite, essa é uma lógica perfeitamente válida para provar propriedades e teoremas envolvendo números naturais.

Aplicando a indução matemática

Apesar de parecer simples por definição, o processo de indução envolve certas transformações algébricas que podem complicar a sua cabeça se não for demonstrado com bastante cuidado. Por este motivo, vamos te mostrar o passo-a-passo dessa demonstração para provar o teorema do “somatório da progressão aritmética”, abordado na sessão anterior.

Prepare o seu espírito e vamos lá:

O teorema determina a seguinte fórmula para a soma consecutiva dos n primeiros números naturais positivos não nulos:

Começamos com a base, testando se o teorema é válido para n=3:

O valor n=3 foi apenas um palpite, poderíamos ter utilizado qualquer valor. O importante é mostrar que o teorema é valido para um valor.

Agora começamos o passo indutivo definindo a hipótese.

Começamos com a hipótese de que o teorema é válido para um valor k

Já demonstramos anteriormente que isso é válido!

Se o teorema é válido para um determinado valor k, então ele também deve ser válido para o próximo valor.

Desta forma, estendemos a equação. Agora, tudo o que precisamos fazer é resolvê-la algebricamente e, ao final, verificar se ambos os lados são iguais. Vamos resolver:

Observe que o trecho em verde abaixo nada mais é do que a própria fórmula do teorema.
​Portanto, podemos substituí-lo na equação.
Simplificamos o lado direito da equação.
No lado esquerdo, colocamos as parcelas sobre o mesmo denominador comum.
Perceba que o (k+1) se repete em ambas as parcelas. Portanto, podemos colocá-lo em evidência.
Reduzimos a equação e mostramos que ambos os lados são equivalentes.

Pronto! A indução foi concluída e provamos que o teorema do somatório funciona para todos os infinitos números naturais positivos não nulos.

Mais um exemplo de indução matemática

Vamos realizar a indução matemática para mais um exemplo, para que você possa compreender de uma forma mais clara como acontece o processo. Desta vez, vamos utilizá-lo para provar o teorema do “somatório dos n primeiros números ímpares”:

O teorema relata uma fórmula fechada para a soma consecutiva dos primeiros números ímpares naturais positivos não nulos:

Começamos com a base, testando se o teorema é válido para n=3:

Agora começamos o passo indutivo definindo a hipótese.

Começamos com a hipótese de que o teorema é válido para um determinado valor k.

Já demonstramos anteriormente que isso é válido!

Se o teorema é válido para um determinado valor k, então ele também deve ser válido para o próximo valor.

Desta forma, estendemos a equação. Agora, tudo o que precisamos fazer é resolvê-la algebricamente e, ao final, verificar se ambos os lados são iguais. Vamos resolver:

Observe que o trecho em verde abaixo nada mais é do que a própria fórmula k2
do teorema.
​Portanto, podemos substituí-lo na equação.
Simplificamos o lado esquerdo da equação.
Colocamos o k em evidência e extraímos em dois fatores (k+1)
Um número multiplicado por ele mesmo é o mesmo que ele ao quadrado. Portanto transformamos o lado direito da equação em dois fatores.
Reduzimos a equação e mostramos que ambos os lados são equivalentes.

Pronto! A indução foi concluída e provamos que o teorema funciona para todos os infinitos números naturais positivos, ímpares e não nulos.

Agora é a sua vez!

Mostre que você aprendeu o processo de indução e prove o teorema abaixo:

David V. Santiago

David V. Santiago

Professor e Mestre em Sistemas e Computação.

Este artigo foi útil para você?

Então nos ajude a crescer e compartilhe-o com outras pessoas que se interessam por esse assunto!

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Nos siga em nossas redes sociais.

O primeiro livro didático de programação para jogos digitais

Este site usa cookies para garantir que você obtenha a melhor experiência.