Indução matemática

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}$

$\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

Demonstração de que uma dada proposição é válida para n=1. (Caso Base).
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)$

$\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}$

$\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

Anúncios

12 respostas a Indução matemática

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
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
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
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$ .
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
Antonia diz:

27 de Março de 2012 às 23:53

Poderia enviar -me esse material?

Responder
- Américo Tavares diz:
  
  28 de Março de 2012 às 11:36
  
  Inseri agora no blogue estas notas em formato pdf. inducaomatematicablogpt
antonia diz:

28 de Março de 2012 às 22:12

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

Responder
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
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
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 Cancelar resposta

Insira aqui o seu comentário...

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

E-mail (obrigatório) (O endereço nunca será tornado público)

Nome (obrigatório)

Site da Web

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

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

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

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.

	Leandro Tezoto em LaTeX – matrizes…
	Vinicius Brasilio Ca… em LaTeX – matrizes…
	Lucas Santos em A Matemática é uma Ciência? ::…
	jhonathan em Resolução da equação do 3.º gr…
	Hélder Machava em B. Demidovitch — Problem…
	Antonio Ferrão Neto em A Matemática é uma Ciência? ::…
	Antonio Ferrão Neto em A Matemática é uma Ciência? ::…
	Serafim Carlos Dias… em Uma aplicação interessante do…