Indução matemática

Publicado em Setembro 15, 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}$

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

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer

Ver todos os artigos de Américo Tavares →

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 Exercícios, Matemática. ligação permanente.

12 respostas a Indução matemática

Alson José diz:

Março 26, 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:

Abril 12, 2011 às 02:46

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

Responder
miranda dos santos diz:

Outubro 22, 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:

Novembro 27, 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:
  
  Novembro 27, 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:

Janeiro 27, 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:

Março 27, 2012 às 23:53

Poderia enviar -me esse material?

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

Março 28, 2012 às 22:12

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

Responder
GILBERTO RIBEIRO DOS SANTOS FILHO diz:

Outubro 22, 2012 às 01:12

Posso passar algumas questões para tirar para tirar duvidas

Responder
GILBERTO RIBEIRO DOS SANTOS FILHO diz:

Novembro 23, 2012 às 11:18

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

Responder
Américo Tavares diz:

Novembro 30, 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

Deixar uma resposta Cancelar resposta

Escreva o seu comentário aqui...

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

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

Nome (obrigatório)

Website

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

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

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

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

Cancelar

Connecting to %s

	edilene em 1 bilião é igual a 1000 000 00…
	Bazinga em Aplicação da transformada de F…
	Américo Tavares em Equação diferencial de uma cur…
	Rosenildo Santos em Mathematics Stack Exchange…
	Américo Tavares em Aplicação da transformada de F…
	Américo Tavares em Aplicação da transformada de F…
	Bazinga em Aplicação da transformada de F…
	Beatriz Alves em Mathematics Stack Exchange…