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

	Lidia em Transformação de um radical du…
	Kauan em Livro de Terence Tao Como Reso…
	Américo Tavares em Projecção ortogonal de um pont…
	Américo Tavares em La Recherche Spécial Mathémati…
	beni22sof em Republicação de problema (e re…
	beni22sof em Republicação de problema (e re…
	Américo Tavares em Algoritmo de O’Beirne, e…
	Américo Tavares em Algoritmo de O’Beirne, e…