Princípio de Indução

§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

\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

\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: 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).

 

Edição de 19-12-2007: Acrescentei § 1 (proveniente de entrada anterior que suprimi em 24-5-2009).

Edição de 31-3-2009: repetida na última fórmula uma igualdade verificada para y=0 (ver 1º. comentário e resposta).

Edição de 24-5-2009: Acrescentei § 3 e § 4 (provenientes de entradas posteriores)

Sobre Américo Tavares

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

3 respostas a Princípio de Indução

  1. This comment is somewhat late, but didn’t you mean to write (x+y)^n on the right hand side of the last equation (final formula), above?!

    • In the first line I prove the case y\neq 0 and in the remaining part the particular case y=0 for which we have x^n=\left( x+y\right) ^n, the binomial formula in the “corolário” (corollary) being still valid.
      Anyhow I have now written this equality once more in the last formula.

  2. Carlos da Costa Lourenço diz:

    Ok

Deixe uma Resposta

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

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 )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s