Exemplos de diferente dificuldade do método de indução matemática

Neste blogue  já descrevi e utilizei o método de indução  matemática em certas demonstrações. Nesta entrada apresento dois novos exemplos, ilustrativos de que nem todas as provas por indução têm o mesmo grau de dificuldade. Enquanto a do 1º.  é  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.

Veja aqui um exercício sobre este método.

About these ads

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 com as etiquetas , . ligação permanente.

5 respostas a Exemplos de diferente dificuldade do método de indução matemática

  1. There is a very instructive lesson on induction that one may learn from the first example you gave. Instead of asking a student to prove the statement in Example 1, if she is asked to prove the statement \displaystyle \sum_{k=1}^{n} \frac1{2^k} < 1 using induction then she quickly runs into trouble. (You may try it yourself!) This is because the statement P(n) is not strong enough to prove the statement P(n+1) when we do the inductive step. Here, P(n) stands for \displaystyle \sum_{k=1}^{n} \frac1{2^k} < 1. Therefore, one must look to prove a stronger statement instead of a weaker one. And, a stronger statement would precisely be the one you gave in Example 1!

    • You are right. In my words, assuming

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

      I can only show that

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

      But, since

      1+\dfrac{1}{2^{n+1}}> 1,

      indeed I am in trouble to prove the inequality

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

      However

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

      proves right away that

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

      In this regard example 1 is important! Thanks for your lesson!

      In this post I was concentrated on the difficulty of the inductive step rather than the result itself. As I wrote in the 1st paragraph, proving by induction example 2 was not easy for me, although I knew the result long time ago, as an application of the Ruffini’s rule.

  2. yodato diz:

    Valeu pelo tutorial. Adorei bastante.
    Se for possivel,gostaria que postasses tambem um tutorial em como demonstrar o Teorema Polinomial em Combinatorica…Eh um pouco complicado pra mim,fazer demonstraçao do Teorema polinomial.

    Abraçoes e mais uma vez,agradeço por este tutorial.

    Yodato Maiato

    • Caro yodato

      Obrigado.

      O teorema trinomial traduz-se no desenvolvimento

      (x+y+z)^{n}=\displaystyle\sum\dbinom{n}{i,j,k}x^{i}y^{i}z^{k}

      em que os índices do somatório verificam 0\leq i\leq n,0\leq j\leq n,0\leq k\leq n e ainda i+j+k=n e o coeficiente trinomial é dado por

      \dbinom{n}{i,j,k}=\dfrac{n!}{i!j!k!}.

      Pode ver o caso multinomial na Wikipédia ou na Wikipedia

      Outro abraço para si.

      Américo

  3. Edosn Rodrigues diz:

    obrigada pela grande ajuda

Deixar uma resposta

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

WordPress.com Logo

Está a comentar usando a sua conta WordPress.com Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook Log Out / Modificar )

Google+ photo

Está a comentar usando a sua conta Google+ Log Out / Modificar )

Connecting to %s