Olá, gente, hoje iniciarei uma seção em que darei algumas dicas importantes para a resolução de diversos problemas. Essa Seção ficará aberta para sempre, para que eu possa acrescentar artigos com alguma frequência. Como plano inicial, espero que até o final de Julho esta secção esteja com alguns artigos sobre métodos de demonstrações matemáticas e outras dicas bem importantes. Hoje falarei sobre o Principio da Indução Finita ou Método de Indução Matemática e suas variações.
Antes de explicar esse tema muito amplo, citarei alguns exemplos.
* mostre que: ![1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1 [;1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1;]](http://thewe.net/tex/1+2+3+4+5+...+n=%20%5Cfrac%7B%28n+1%29.n%7D%7B2%7D%20%20%5Cforall%20n%20%5Cge%201)
* mostre que: ![1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1 [;1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1;]](http://thewe.net/tex/1%5E2+2%5E2+3%5E2+...+n%5E2=%20%5Cfrac%7Bn%20%5Ctimes%28n+1%29%20%5Ctimes%282n+1%29%7D%7B6%7D%20%20%20%20%5Cforall%20n%20%5Cge%201)
* mostre que: ![1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1 [;1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1;]](http://thewe.net/tex/1%5E3+2%5E3+3%5E3+...+n%5E3=%20%281+2+3+...+n%29%5E2%20%20%20%20%5Cforall%20n%20%5Cge%201)
(Após demonstradas essas propriedades, tentem gravá-las e refazer as demonstrações, pois são bem importantes!)
O MIM ou PIF consiste basicamente em uma maneira de provar uma propriedade
para todo
. Para isso você deve verificar
coisas:
i) (Base da Indução, passo base ou passo básico) Verificar se
é verdadeira e
ii) (Passo indutivo) Verificar que se
é valido para algum n natural,
, implica que
também é valido.
Em geral, há uma certa confusão pois pode parecer que é usar a hipótese para demonstrá-la, o que claramente não é valido, senão qualquer hipótese seria verdadeira. De forma mais didática, a demonstração pelo MIM equivale a demonstrar que, se vale para
e que se toda vez que vale para n, vale para seu SUCESSOR.
Por exemplo: imagine que eu subo uma escada, e que eu garanto que, se eu subir um degrau, então eu subirei mais um, com isso, eu subirei 2 degraus, e como eu subi 2, eu subirei 3 e assim por diante. Ao final, eu terei demonstrado que é possível subir uma escada de n degraus para todo n natural (a menos que eu fique cansado hahaha).
Vamos agora a mais alguns detalhes técnicos e exemplos.
No passo base, verificamos a validade dessa propriedade pra um valor inicial. A Hipótese de Indução (aqui no blog abreviarei para H.I.) é a propriedade aplicada a n, ou seja,
, e o passo indutivo consiste em mostrar que, se a Hipótese é Válida para um n, então ela valerá para um n+1, mas veremos como funciona na prática.
*Mostre que: ![1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1 [;1+2+3+4+5+...+n= \frac{(n+1).n}{2} \forall n \ge 1;]](http://thewe.net/tex/1+2+3+4+5+...+n=%20%5Cfrac%7B%28n+1%29.n%7D%7B2%7D%20%20%20%20%5Cforall%20n%20%5Cge%201)
Primeiro, temos a base da indução,![n=1 [; n=1;]](http://thewe.net/tex/%20n=1)
Logo, o passo base é verdadeiro.
Depois, supondo que
seja verdadeiro para algum n, então
, de fato,
![1+2+3+4+5+...+n+(n+1)= \underbrace{\frac{(n+1).n}{2}}_{1+2+3+4+5+...+n} + (n+1)= \frac{(n+1).n + 2(n+1)}{2} [;1+2+3+4+5+...+n+(n+1)= \underbrace{\frac{(n+1).n}{2}}_{1+2+3+4+5+...+n} + (n+1)= \frac{(n+1).n + 2(n+1)}{2};]](http://thewe.net/tex/1+2+3+4+5+...+n+%28n+1%29=%20%5Cunderbrace%7B%5Cfrac%7B%28n+1%29.n%7D%7B2%7D%7D_%7B1+2+3+4+5+...+n%7D%20+%20%28n+1%29=%20%5Cfrac%7B%28n+1%29.n%20+%202%28n+1%29%7D%7B2%7D)
botando
em evidência,
C.Q.D.
botando
C.Q.D.
Acho que com esse exemplo ficou claro como é feita a demonstração pelo MIM. Aqui vão mais dois exemplos para ajudar.
*Mostre que: ![1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1 [;1^2+2^2+3^2+...+n^2= \frac{n \times(n+1) \times(2n+1)}{6} \forall n \ge 1;]](http://thewe.net/tex/1%5E2+2%5E2+3%5E2+...+n%5E2=%20%5Cfrac%7Bn%20%5Ctimes%28n+1%29%20%5Ctimes%282n+1%29%7D%7B6%7D%20%20%5Cforall%20n%20%5Cge%201)
Inicialmente, vamos mostrar o passo básico.
Logo, o Passo básico é verdadeiro.
Nossa Hipotese de Indução é:
Vamos mostrar a veracidade do passo indutivo.
![1^2+2^2+3^2+...+n^2+(n+1)^2 = \underbrace{\frac{n \times(n+1) \times(2n+1)}{6}}_{ = 1^2+2^2+3^2+...+n^2 } + (n+1)^2 = [;1^2+2^2+3^2+...+n^2+(n+1)^2 = \underbrace{\frac{n \times(n+1) \times(2n+1)}{6}}_{ = 1^2+2^2+3^2+...+n^2 } + (n+1)^2 =;]](http://thewe.net/tex/1%5E2+2%5E2+3%5E2+...+n%5E2+%28n+1%29%5E2%20=%20%5Cunderbrace%7B%5Cfrac%7Bn%20%5Ctimes%28n+1%29%20%5Ctimes%282n+1%29%7D%7B6%7D%7D_%7B%20=%201%5E2+2%5E2+3%5E2+...+n%5E2%20%7D%20+%20%28n+1%29%5E2%20=)
Botando
em evidencia e fazendo algumas contas...
porém
, logo
![1^2+2^2+ \cdots + n^2 + (n+1)^2= [;1^2+2^2+ \cdots + n^2 + (n+1)^2=;]](http://thewe.net/tex/1%5E2+2%5E2+%20%5Ccdots%20+%20n%5E2%20+%20%28n+1%29%5E2=)
![\frac{(n+1) \times(n+2) \times (2n+3)}{6} [;\frac{(n+1) \times(n+2) \times (2n+3)}{6};]](http://thewe.net/tex/%5Cfrac%7B%28n+1%29%20%5Ctimes%28n+2%29%20%5Ctimes%20%282n+3%29%7D%7B6%7D)
que é exatamente nosso
C.Q.D.
C.Q.D.
Uma boa dica é escrever como deve ficar seu
para que isso indique um possivel caminho para a solução do exercicio. Tal ideia será muito util na resolução do exercício a seguir.
*Mostre que: ![1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1 [;1^3+2^3+3^3+...+n^3= (1+2+3+...+n)^2 \forall n \ge 1;]](http://thewe.net/tex/1%5E3+2%5E3+3%5E3+...+n%5E3=%20%281+2+3+...+n%29%5E2%20%5Cforall%20n%20%5Cge%201)
Passo Base.
Passo Indutivo.
Inicialmente, para facilitar, temos que tentar entender quanto aumenta em relação a
quando passamos para
, primeiro,
escreveremos
após isso, fica facil ver que:
![[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 = [;[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 =;]](http://thewe.net/tex/%5B1+2+3+4+...+n+%28n+1%29%5D%5E2%20-%20%281+2+3+4+...+n%29%5E2%20=)
(é só ver que cada termo de 1 até n multiplica (n+1) 1 vez, depois (n+1) multiplica cada termo (incluindo n+1) 1 vez).
Isso é o dobro da soma dos termos de uma P.A de razão
Esse processo informalmente demonstra o teorema, porém como isso pode parecer usar a hipótese para demonstrar a hipótese, quero terminar com calma a demonstração.
Passo Indutivo (formalizado)
por Hipotese de Indução
porém como mostramos acima,
![(n+1)^3= (n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1). [;(n+1)^3= (n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1).;]](http://thewe.net/tex/%28n+1%29%5E3=%20%28n+1%29+2%28n+1%29+3%28n+1%29+...+n%28n+1%29+%28n+1%29+2%28n+1%29+3%28n+1%29+...+n%28n+1%29+%28n+1%29%28n+1%29.)
Porém, como mostramos acima,
![(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1) [;(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)+2(n+1)+3(n+1)+...+n(n+1)+(n+1)(n+1);]](http://thewe.net/tex/%28n+1%29+2%28n+1%29+3%28n+1%29+...+n%28n+1%29+%28n+1%29+2%28n+1%29+3%28n+1%29+...+n%28n+1%29+%28n+1%29%28n+1%29)
é a diferença![[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2 [;[1+2+3+4+...+n+(n+1)]^2 - (1+2+3+4+...+n)^2;]](http://thewe.net/tex/%5B1+2+3+4+...+n+%28n+1%29%5D%5E2%20-%20%281+2+3+4+...+n%29%5E2)
Porém, como mostramos acima,
é a diferença
logo, ![(1+2+3+4+...+n)^2 + (n+1)^3 = [1+2+3+4+...+n+(n+1)]^2 [;(1+2+3+4+...+n)^2 + (n+1)^3 = [1+2+3+4+...+n+(n+1)]^2;]](http://thewe.net/tex/%281+2+3+4+...+n%29%5E2%20+%20%28n+1%29%5E3%20=%20%5B1+2+3+4+...+n+%28n+1%29%5D%5E2)
C.Q.D.
C.Q.D.
Antes de terminar esse post, para que não fique muito longo, pois o assunto é bem extenso, eu gostaria de mostrar um erro comum ao usar o PIF.
Por exemplo, demonstrar que a soma dos n primeiros números ímpares é ![n^2 + 1 [;n^2 + 1;]](http://thewe.net/tex/n%5E2%20+%201)
Definiremos um número ímpar como um número da forma
(note que o n-ésimo número ímpar vale
).
Nossa Hipotese de Indução é de que
![1+3+5+...+(2n-1) = n^2 + 1 [;1+3+5+...+(2n-1) = n^2 + 1;]](http://thewe.net/tex/1+3+5+...+%282n-1%29%20=%20n%5E2%20+%201)
então
![1+3+5+...+(2n-1)+(2n+1)= n^2 + 1 + 2n + 1 = (n+1)^2 + 1 [;1+3+5+...+(2n-1)+(2n+1)= n^2 + 1 + 2n + 1 = (n+1)^2 + 1;]](http://thewe.net/tex/1+3+5+...+%282n-1%29+%282n+1%29=%20n%5E2%20+%201%20+%202n%20+%201%20=%20%28n+1%29%5E2%20+%201)
então
CLARAMENTE ISSO ESTÁ ERRADO!
O erro é simples, o passo base não é valido, em geral, algumas pessoas não verificam o passo base por acharem muito trivial, mas não é e ele é tão importante quanto o passo indutivo.
O erro é simples, o passo base não é valido, em geral, algumas pessoas não verificam o passo base por acharem muito trivial, mas não é e ele é tão importante quanto o passo indutivo.
Só por curiosidade, a soma dos n primeiros números ímpares é
Até mais!
*** Lembre-se: Para melhorar a qualidade do nosso blog, avalie esse post.
*** Lembre-se: Para melhorar a qualidade do nosso blog, avalie esse post.
Boa noite! Estou pesquisando alguns posts em Teoria dos Números e percebi que em vários deles as expressões não estão aparecendo. Há um motivo? Obrigado!
ResponderExcluirOi, Diogo!
ExcluirInfelizmente, é um problema recorrente em postagens antigas.
Em breve vamos consertar tudo isso.
Abraço,
A Equipe do Blog.