Indução matemática

Publicado em 15 de Setembro de 2009 por Américo Tavares

Reuno aqui, para comodidade de leitura, algumas entradas já publicadas sobre o princípio da indução matemática.

§1. Por este princípio, a demonstração da veracidade de uma determinada proposição matemática p\left( n\right) para todos os inteiros n\geq n_{0}, comporta dois passos:

(1) Verifica-se a sua validade para um dado valor inteiro n_{0} (normalmente, 0 ou 1) da variável de indução n.

(2) Assume-se que é válida para o inteiro n e demonstra-se que é também válida para n+1, isto é, que p\left( n\right)\implies p\left( n+1\right) .

\bigskip

Vamos demonstrar de seguida o Teorema Binomial por este princípio.

Teorema: Para todo o valor de n natural, tem-se

\boxed{\left( 1+x\right) ^{n}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}}

qualquer que seja o valor real de x.

\bigskip

Demonstração:

O teorema verifica-se para n=0: \displaystyle\sum_{k=0}^{0}\dbinom{0}{k}x^{k}=\dbinom{0}{0}x^{0}=1 e \left( 1+x\right) ^{0}=1, logo \left( 1+x\right) ^{0}=\displaystyle\sum_{k=0}^{0}\dbinom{0}{k}x^{k}. Admitimos agora que o teorema é válido para n, isto é, que \left( 1+x\right)^{n}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k} e demonstremos que o é igualmente para n+1. Como \left( 1+x\right) ^{n+1}=\left( 1+x\right) \left(1+x\right) ^{n}, vem

\left( 1+x\right) ^{n+1}=\left( 1+x\right) \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}+\dbinom{n}{k}x^{k+1}.

Manipulamos o segundo membro (lado direito) até obter \displaystyle\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^{k}. De facto,

\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}+\dbinom{n}{k}x^{k+1}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}+\displaystyle\sum_{k=1}^{n+1}\dbinom{n}{k-1}x^{k}=\dbinom{n}{0}x^{0}+\left( \displaystyle\sum_{k=1}^{n}\dbinom{n}{k}x^{k}+\dbinom{n}{k-1}x^{k}\right) +\dbinom{n}{n}x^{n+1}=\dbinom{n+1}{0}x^{0}+\left( \displaystyle\sum_{k=1}^{n}\dbinom{n+1}{k}x^{k}\right) +\dbinom{n+1}{n+1}x^{n+1}

pela identidade de Pascal e porque

\dbinom{n+1}{0}=\dbinom{n}{0}=\dbinom{n+1}{n+1}=\dbinom{n}{n}=1.

Mas, como

\dbinom{n+1}{0}x^{0}+\left( \displaystyle\sum_{k=1}^{n}\dbinom{n+1}{k}x^{k}\right) +\dbinom{n+1}{n+1}x^{n+1}=\displaystyle\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^{k}

provámos, como pretendíamos, que \left( 1+x\right)^{n+1}=\displaystyle\sum_{k=0}^{n+1}\dbinom{n+1}{k}x^{k}, e assim acabámos a demonstração. \qquad \blacksquare

\bigskip

A partir do desenvolvimento de \left( 1+x\right) ^{n} deduz-se imediatamente o de \left( x+y\right) ^{n}.

\bigskip

Corolário: Quaisquer que sejam os reais x e y e o natural n é válida a fórmula

\boxed{\left( x+y\right) ^{n}=\displaystyle \sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}}.

\bigskip
Demonstração: Admitamos que y\neq 0:

\left( x+y\right) ^{n}=y^{n}\left( 1+\frac{x}{y}\right)^{n}=y^{n}\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}\left( \frac{x}{y}\right)^{k}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}.

Como

\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}=\displaystyle\sum_{k=0}^{n-1}\dbinom{n}{k}x^{k}y^{n-k}+\dbinom{n}{n}x^{n}y^{0},

para y=0, tem-se

\left( x+y\right)^{n}=x^{n}

e

\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}=x^n=\left( x+y\right) ^{n}

ou seja a fórmula ainda é válida \qquad \blacksquare .

 

§2. O Princípio de indução matemática é o seguinte axioma de Peano:

Se o conjunto A, contido em N, for tal que 1 pertence a A e n+1 pertence igualmente a A sempre que n seja elemento de A, então A = N. [N aqui é o conjunto dos naturais 1, 2, 3, … ].

Uma propriedade P diz-se hereditária quando, sendo verdadeira para o inteiro n, é também verdadeira para o sucessor de n (n+1).

Assim, o Princípio de Indução equivale a afirmar que uma dada proposição, verdadeira para n=1 e hereditária, implica que seja verdadeira para todos os naturais 1, 2, 3, … .

Por isso, a aplicação deste método comporta as duas etapas (ou passos) conhecidos

  1. Demonstração de que uma dada proposição é válida para n=1. (Caso Base).

  2. Demonstração de que a proposição é hereditária. (Etapa de Indução).

Este princípio nada ou quase nada tem a ver com o método de indução próprio das ciências naturais, que se caracteriza por se estabelecer uma lei geral observando a repetição do mesmo fenómeno em inúmeros casos particulares.

§3. Nem todas as provas por indução têm o mesmo grau de dificuldade. Enquanto a do 1º. exemplo é extremamente simples e natural, a do 2º. obtive-a após tentativas, recorrendo a uma identidade algébrica auxiliar — a ser usada no passo de indução — cuja demonstração me pareceu mais simples do que a identidade inicialmente apresentada, que pode ser deduzida a partir da regra de Ruffini de divisão de um polinómio em x, de grau n, por x-\alpha .

Exemplo 1: prove por indução matemática

\displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n}}

Para n=1 a igualdade verifica-se:

\dfrac{1}{2}=1-\dfrac{1}{2}

Admite-se que se verifica para n

\displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n}}

e prova-se que nesse caso também se verifica para n+1, ou seja, devemos chegar a

\displaystyle\sum_{k=1}^{n+1}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n+1}}

Vejamos: se

\displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}=1-\dfrac{1}{2^{n}}

então, somando \dfrac{1}{2^{n+1}} a ambos os membros da igualdade e simplificando o segundo membro, deduzimos sucessivamente

\left( \displaystyle\sum_{k=1}^{n}\dfrac{1}{2^{k}}\right) +\dfrac{1}{2^{n+1}} =1-\dfrac{1}{2^{n}}+\dfrac{1}{2^{n+1}}=1-\left( \dfrac{1}{2^{n}}-\dfrac{1}{2^{n+1}}\right) =1-\dfrac{1}{2^{n+1}}

Ora, como

\displaystyle\sum_{k=1}^{n+1}\dfrac{1}{2^{k}}=\left( \sum_{k=1}^{n}\dfrac{1}{2^{k}}\right) +\dfrac{1}{2^{n+1}}

provámos deste modo que a igualdade se verifica para qualquer inteiro n\geq 1.

Exemplo 2: se n for um inteiro positivo, prove

a^{n}-b^{n}=\left( a-b\right) \displaystyle\sum_{k=0}^{n-1}a^{k}b^{n-1-k}

Para n=1, temos a^{1}-b^{1}=\left( a-b\right) \displaystyle\sum_{k=0}^{1-1}a^{k}b^{1-1-k}=a-b.

Antes de aplicar a hipótese de indução, a ideia fundamental consiste em mostrar a validade da identidade auxiliar

\left( a^{n}-b^{n}\right) P(n+1)=\left( a^{n+1}-b^{n+1}\right) P(n)\qquad (\ast )

em que

P(n)=\displaystyle\sum_{k=0}^{n-1}a^{k}b^{n-1-k}.

De facto

\left( a^{n}-b^{n}\right) P(n+1)=\left( a^{n}-b^{n}\right) \displaystyle\sum_{k=0}^{n}a^{k}b^{n-k}

=\left( \displaystyle\sum_{k=0}^{n}a^{n+k}b^{n-k}\right) -\left( \displaystyle\sum_{k=0}^{n}a^{k}b^{2n-k}\right)

e

\left( a^{n+1}-b^{n+1}\right) P(n)=\left( a^{n+1}-b^{n+1}\right) \displaystyle\sum_{k=0}^{n-1}a^{k}b^{n-1-k}

=\left( \displaystyle\sum_{k=0}^{n-1}a^{n+k+1}b^{n-1-k}\right) -\left( \displaystyle\sum_{k=0}^{n-1}a^{k}b^{2n-k}\right)

Mas

\displaystyle\sum_{k=0}^{n}a^{n+k}b^{n-k}=a^{n}b^{n}+\displaystyle\sum_{k=0}^{n-1}a^{n+k+1}b^{n-1-k}

e

\displaystyle\sum_{k=0}^{n}a^{k}b^{2n-k}=a^{n}b^{n}+\displaystyle\sum_{k=0}^{n-1}a^{k}b^{2n-k}

Subtraindo membro a membro, vem

\left( \displaystyle\sum_{k=0}^{n}a^{n+k}b^{n-k}\right) -\left( \displaystyle\sum_{k=0}^{n}a^{k}b^{2n-k}\right)

=\left( \displaystyle\sum_{k=0}^{n-1}a^{n+k+1}b^{n-1-k}\right) -\left( \displaystyle\sum_{k=0}^{n-1}a^{k}b^{2n-k}\right)

pelo que fica provada a identidade (\ast ) da qual se tira

a^{n+1}-b^{n+1}=\dfrac{a^{n}-b^{n}}{P(n)}P(n+1)

Assim, admitindo que

a^{n}-b^{n}=\left( a-b\right) P(n)

resulta que

a^{n+1}-b^{n+1}=\dfrac{\left( a-b\right) P(n)}{P(n)}P(n+1)

=\left( a-b\right) P(n+1)

=\left( a-b\right) \displaystyle\sum_{k=0}^{n}a^{k}b^{n-k}

como se queria mostrar.

§ 4. Exercício 1: prove que existe apenas um número natural que verifica a relação

^{n\!}C_{n-2}=2^{n-2}-1

Sugestão: utilize o princípio de indução para provar que a relação não é satisfeita por nenhum natural superior a seis.

Esta ideia é devida a Vishal Lama (neste comentário em inglês).

§ 5. Exercício 2: podemos demonstrar que

\Gamma \left( n+\dfrac{1}{2}\right) =\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }\qquad n=1,2,3,\ldots .

De facto substituindo em

\Gamma \left( n+\dfrac{1}{2}\right) =\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }

n por 1, ficamos com

\Gamma \left(1+\dfrac{1}{2}\right)=\Gamma \left( \dfrac{3}{2}\right) =\dfrac{1}{2^{1}}\sqrt{\pi }=\dfrac{1}{2}\sqrt{\pi },

que vemos ser verdadeiro, visto que da equação funcional da função gama

\Gamma \left( x+1\right) =x\Gamma \left( x\right)

se obtém, para x=\dfrac{1}{2}

\Gamma \left( 1+\dfrac{1}{2}\right) =\dfrac{1}{2}\Gamma \left( \dfrac{1}{2}\right) =\dfrac{1}{2}\sqrt{\pi }.

Admitimos agora que

\Gamma \left( n+\dfrac{1}{2}\right) =\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }

e fazemos, na equação funcional, x=n+\dfrac{1}{2}. Como vem sucessivamente

\Gamma \left( n+1+\dfrac{1}{2}\right) =\left( n+\dfrac{1}{2}\right) \Gamma\left( n+\dfrac{1}{2}\right) =\left( n+\dfrac{1}{2}\right) \dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }

=\dfrac{2n+1}{2}\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) }{2^{n}}\sqrt{\pi }=\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) \left( 2n+1\right) }{2^{n+1}}\sqrt{\pi }

=\dfrac{1\cdot 3\cdot 5\cdots \left( 2n-1\right) \left[ 2\left( n+1\right) -1\right] }{2^{n+1}}\sqrt{\pi }

demonstra-se desta forma o passo de indução. \blacktriangleleft

Ficheiro pdf. inducaomatematicablogpt

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Exercícios Matemáticos, Indução matemática, Matemática, Matemáticas Gerais, Teoria dos Números com as etiquetas , . ligação permanente.

12 respostas a Indução matemática

  1. Alson José diz:
    26 de Março de 2010 às 06:46

    a materia esta excelente, tanto q me interessou. sera que posso obtê la por email? alsonjose@yaoo.com

    [Enviei-lhe um email, mas recebi uma mensagem a informar-me que não foi entregue; de seguida reenviei para yahoo em vez de yaoo, mas sem sucesso.

    A Tavares]

    Responder
  2. Juliana Raisa diz:
    12 de Abril de 2011 às 02:46

    Foi muito bem fetia a demonstração, só acho que poderia haver mais comentários.

    Responder
  3. miranda dos santos diz:
    22 de Outubro de 2011 às 20:57

    é um método de prova matemática usado para demostrar a verdade de um número infinito de proposições

    Responder
  4. a diz:
    27 de Novembro de 2011 às 13:58

    Só não entendo como é que no final sabemos que também é válido para n+1 se não da igual nos dois lados

    Responder
    • Américo Tavares diz:
      27 de Novembro de 2011 às 22:56

      “não da igual nos dois lados”

      Não sei se percebo a sua dúvida. Verifiquei todos os exemplos que apresentei e não detectei nenhum erro. No final não obtemos uma igualdade do tipo A(n+1)=A(n+1), mas do tipo A(n+1)=B(n+1).

      O que fiz foi provar que admitindo a validade de uma igualdade do tipo A(n)=B(n) daí decorria a igualdade A(n+1)=B(n+1), além de ter verificado o caso base A(n_0)=B(n_0), em que, por exemplo, no teorema binomial é n_0=0.

  5. Aloisio Teixeira diz:
    27 de Janeiro de 2012 às 12:36

    O princípio da indução é um dos básicos na matemática. Veja como apliquei-a em elementosdeteixeira.blogspot.com no artigo funções aritméticas multiplicativas. Parabéns pelo execelente artigo.

    Responder
  6. Antonia diz:
    27 de Março de 2012 às 23:53

    Poderia enviar -me esse material?

    Responder
  7. antonia diz:
    28 de Março de 2012 às 22:12

    Valeu,
    O material é ótimo, me ajudou muito.

    Responder
  8. GILBERTO RIBEIRO DOS SANTOS FILHO diz:
    22 de Outubro de 2012 às 01:12

    Posso passar algumas questões para tirar para tirar duvidas

    Responder
  9. GILBERTO RIBEIRO DOS SANTOS FILHO diz:
    23 de Novembro de 2012 às 11:18

    Excelente conseguir tirar todas as minha dúvidas muito obrigado.

    Responder
  10. Américo Tavares diz:
    30 de Novembro de 2012 às 22:38

    Este meu blogue, como já referi por mais do que uma vez, não se destina por princípio a responder a questões. Sugiro que as coloque por exemplo no Mathematics Stack Exchange, site de perguntas e respostas de matemática de nível geral, em inglês.

    Responder

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Gravatar
Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com ( Terminar Sessão /  Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter ( Terminar Sessão /  Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook ( Terminar Sessão /  Alterar )

Cancelar

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.