sábado, 7 de julho de 2012

Indução Matemática - Parte II

Olá, hoje darei continuidade ao post sobre o Método de Indução Matemática, (clique aqui para ver o post anterior

Para organizar melhor os assuntos, hoje escreverei sobre o uso de indução em demonstrações de desigualdades, divisibilidade e em situações do mundo real. Inicialmente, temos alguns exemplos:

** (A desigualdade de Bernoulli). [;(1+x)^n \ge 1 + nx, \forall n \in \mathbb{N}, x > -1, x \in \mathbb{R};]. E a igualdade ocorre para [;n > 1;] se e somente se [;x=0;]

** Mostre que: [;2^n \le;] [;n;]! [;\forall n\ge 4;], [; n\in \mathbb{N};]

**(formula do binômio de Newton) [;(x+y)^n;]= [;n \choose 0;][;\times;][;x^n;][;+;][;n \choose 1;][;\times;][;x^{n-1}y;][;+\cdots +;][;n \choose n;][;\times;][;y^n;]

**Mostre que: Para qualquer [;n;] natural, [;n^3+(n+1)^3+(n+2)^3;] é divisível por [;9;].

**Mostre que: [;5^n-1;] é múltiplo de [;24;] para todo número natural [;n;] par.

**Mostre que, se [;F_n;] é o n-ésimo termo da sequencia de Fibonacci, então,
[;F_{n+1} \times;] [;F_{n-1} - (F_n)^2 = (-1)^n \forall n \ge 1;], [;n \in \mathbb{N};] [;\mathbb{N};]

**(A torre de Hanói) Há 3 Hastes e n discos de diâmetros diferentes, todos os discos estão empilhados de forma que um de maior diâmetro não fique em cima de um de menor diâmetro, o jogo consiste em mover toda a pilha para uma outra haste sem que um disco de diâmetro maior fique em cima de um com diâmetro menor.
*** O jogo tem solução para cada [;n \in \mathbb{N};]?
*** Em caso afirmativo, qual é o número mínimo [;j_n;] de movimentos para resolver o problema com n discos?

**(A Pizza de Steiner)- Retirado de [1] - Jacob Steiner foi um grande geômetra alemão, ele propôs e resolveu o problema em 1826. “ Qual é o maior número de partes em que se pode dividir o plano com n cortes retos?" - (se imaginar o plano como uma pizza, temos uma justificativa para o nome do problema.)

Esses são exemplos de problemas clássicos (Torre de Hanói e a Pizza de Steiner), fórmulas conhecidas (como o binômio de Newton) e desigualdades importantes. Tente demonstra-las você mesmo, de preferência por indução. É um ótimo exercício!

Comecemos pelas Desigualdades. 

Em geral, usar o PIF na resolução de desigualdades é:

*Verificar o passo base.

*Verificar que se vale para n, o passo indutivo para n+1 em um dos lados é menor ou maior que o passo indutivo do outro lado da desigualdade.

Aos que acharam pouco claro, aqui vai um exemplo.

**Mostre que: [;2^n \le n;]! para todo [;n \ge 4;], [;n \in \mathbb{N};].

Passo básico: [;2^4\le 4;]!, de fato [;16\le 24;].

Supondo que [;2^n\le n!;], se multiplicar por [; n+1;] ambos lados, então [;2^n \cdot (n+1) \le (n+1);]! porém, [;2^n \cdot (n+1);] é maior que [;2^{n+1};] para todo n natural maior que 2. Como pelo enunciado [;n\ge 4;], então [;2^{n+1}< 2^n\cdot (n+1) \le (n+1);]!

logo, [;2^{n+1}\le (n+1);]! C.Q.D

Outro exemplo é:

**Mostre que: [;(1+x)^n \ge 1 + nx, \forall n \in \mathbb{N}, x > -1, x \in \mathbb{R};]. E a igualdade ocorre para [;n > 1;] se e somente se [;x=0;].

Inicialmente, verifique que [;(1+x)>0;] pois [;x>-1;].

Passo base: [;n=1;] ocorre a igualdade [;1+x=1+x;].

Supondo pela H.I que [;(1+x)^n \ge 1+nx;], então:

[;(1+x)(1+x)^n \ge (1+x)(1+nx) = 1 + nx+ x + nx^2 = 1 + (n+1)x +nx^2;],

de onde concluímos que:

A igualdade ocorre quando [;n=1;] ou quando [;n>1;] e [;x=0;], pois como [;nx^2=0;] então 

[;(1+0)(1+0)=1+(n+1)0;].

E que fora o caso em que ocorre a igualdade,

[;(1+x)(1+x)^n \ge 1;] [;+ (n+1)x +nx^2 \ge 1+(n+1)x;] logo[;(1+x)^{n+1} \ge 1+(n+1)x;]

C.Q.D.
Para ler mais sobre a desigualdade de Bernoulli, CLIQUE AQUI

(brevemente sairá também no blog um post com esse assunto)

Vou deixar a formula do Binômio de Newton como "dever de casa", e no próximo post vou resolvê-la.

Agora falaremos sobre indução na resolução de problemas de divisibilidade para certo número J. Em geral, consiste em encontrar [;P(n+1)-P(n)=k;] e mostrar que k é divisível por J.

Seguem dois exemplos.
**Mostre que: Para qualquer n natural, [;n^3+(n+1)^3+(n+2)^3;]é divisível por [;9;]

Verificando a base [;n=0;]

[;0^3+(0+1)^3+(0+2)^3=1+8=9;] 

logo, para o passo base é valido

Supondo que [;n^3+(n+1)^3+(n+2)^3;] é um múltiplo de [;9;], então, [;(n+1)^3+(n+2)^3+(n+3)^3;] será também múltiplo de [;9;] se [;(n+1)^3+(n+2)^3+(n+3)^3;][;-n^3-(n+1)^3-(n+2)^3;]for também.

Ou seja, [;(n+3)^3 - n^3;] deve ser múltiplo de [;9;].

[;(n+3)^3 - n^3 = n^3+9n^2+27n+27 - n^3 = 9n^2+27n+27 = 9(n^2+3n+3);][;9(n^2+3n+3);]

Como n é natural, fazendo [;n^2+3n+3=L;], [;L;] é natural também. Logo, 

[;n^3+(n+1)^3+(n+2)^3 + 9L = (n+1)^3+(n+2)^3+(n+3)^3;]como [;n^3+(n+1)^3+(n+2)^3;] é por hipótese múltiplo de 9, [;(n+1)^3+(n+2)^3+(n+3)^3;] também será.

C.Q.D.

O.B.S.: A principio é natural pensar "Nossa! pra que tanto trabalho?! Eu facilmente posso verificar usando ARITMÉTICA MODULAR ".

De fato, mas para verificar a divisibilidade para números grandes é melhor usar indução. Olhe o exemplo abaixo.

**Mostre que: [;5^n-1;] é múltiplo de [;24;] para todo número natural n par.

Para o passo base, [;5^0-1=1-1=0;] é de fato múltiplo de [;24;].

Como n é par, [;n=2k;]. Supondo que [;5^{2k}-1;] é múltiplo de [;24;], temos que saber como passar de [;5^{2k}-1;] para [;5^{2k+2}-1;].

Se [;5^{2k}-1 = M;], então [;5^2\cdot M - 24;][;+24;] [;= 5^{2k+2}-1;], logo, como [;M;] é por Hipótese múltiplo de [;24;], então [;5^2\times M + 24;]é múltiplo de [;24;]. Porém [;5^2 \cdot M + 24 = 5^{2k+2}-1;]. Logo, toda vez que [;5^{2k}-1;] é múltiplo de [;24;], [;5^{2k+2}-1;] também será.

C.Q.D.

Agora temos alguns exemplos para mostrar o uso do PIF em situações próximas a realidade:

**Mostre que, se [;F_n;] é o n-ésimo termo da sequencia de Fibonacci, então,
[;F_{n+1}.F_{n-1} - (F_n)^2 = (-1)^n \forall n \ge 1, n \in \mathbb{N};][;\mathbb{N};]

A sequencia de Fibonacci é definida pela recorrência:

[;F_0 = 0;]
[;F_1;][;= 1;]
[;F_n = F_{n-1} + F_{n-2};][;F_{n-1};][;+;][;F_{n-2};]

Há várias propriedades interessantes, por isso pretendemos falar sobre ela aqui no blog em breve. Se quiser saber mais sobre essa sequencia clique aqui.

Inicialmente testamos o passo base: [;n=1;]

[;F_2 \times F_0;][; - (F_1)^2 = 1 \times 0 - 1 = -1;] . Logo, a hipótese é valida para [;n=1;]

[;F_{n+2}.F_{n} - (F_{n+1})^2 =;]

Por [;F_{n+2}=F_{n+1}+F_n;] e [;F_{n+1}=F_{n}+F_{n-1};]temos

[;(F_{n+1};][;+F_n);] [;\cdot;] [;(F_n);] [;- [(F_{n}+F_{n-1}) \cdot F_{n+1}] =;]
= [;(F_n)^2-F_{n+1} \cdot F_{n-1};]

Pela H.I, [;F_{n+1}.F_{n-1} - (F_n)^2 = (-1)^n;] 

multiplicando os dois lados por [;(-1);]

[;(F_n)^2;][;-F_{n+1};] [;\cdot F_{n-1} = F_{n+2}.F_{n};] [;- (F_{n+1})^2 = (-1)^{n+1};]

C.Q.D.

**(A torre de Hanói) Há 3 Hastes e n discos de diâmetros diferentes, todos os discos estão empilhados de forma que um de maior diâmetro não fique em cima de um de diâmetro menor, o jogo consiste em mover toda a pilha para uma outra haste, sem que um disco de diâmetro maior fique em cima de um com diâmetro menor.
*** O jogo tem solução para cada [;n \in \mathbb{N};]?
*** Em caso afirmativo, qual é o número mínimo [;j_n;] de movimentos para resolver o problema com n discos?

Sim, para resolver, com 1 disco precisamos de 1 jogada. Para resolver com n+1 discos precisamos resolver como se tivesse apenas n discos, depois passar o disco de maior diâmetro para uma haste livre e resolver novamente como se tivesse n discos.

Já demonstramos acima que é possível resolver o jogo com n discos para qualquer n natural. Seja então [;P(n);] o número mínimo de movimentos que devem ser realizados para resolver um jogo com n discos. 

Logo, [;P(n+1)= P(n)+P(n)+1 = 2P(n) +1;]

[;P(1);] é 1, que é [;2^1-1;]

Suponha então que [;P(n)=2^n-1;]. Então, [;P(n+1)=2^{n+1}-2+1=2^{n+1}-1;]

Logo, o número mínimo de jogadas a se fazer com n discos é [;2^n-1;].(clique aqui para ler mais sobre este jogo!)

**(A Pizza de Steiner) - Jacob Steiner foi um grande geômetra alemão, ele propôs e resolveu o problema em 1826. " Qual é o maior número de partes em que se pode dividir o plano com n cortes retos?" - (se imaginar o plano como uma pizza, temos uma justificativa para o nome do problema).
Observe que usando n cortes, o número máximo de regiões em que podemos dividir o plano será alcançado se:
*Não houver 2 retas paralelas.
*Não houver 1 ponto que pertença a 3 ou mais retas.
(Essas condições são geralmente chamadas de retas em posição geral. Há também pontos em posição geral, e enunciados com essas nomenclaturas não são incomuns!)
O primeiro corte divide o plano em 2 partes. Após fazer alguns casos, observa-se que [;P_n=\frac{n(n+1)}{2} + 1;] onde [;P_n;] é o número máximo de regiões que podemos obter com n cortes. Observe que seguindo as regras acima, o (n+1)-ésimo corte cruzará n retas e [;n+1;] regiões, dividindo cada região em duas partes, ou seja, o número máximo de cortes que obtemos com n+1 cortes é:

[;\frac{n(n+1)}{2} + 1 + n+1= \frac{(n+1)(n+2)}{2} + 1 = P_{n+1};]

Mostrando a veracidade de [;P_n;].

Observe que a dificuldade em resolver problemas de indução no mundo material é que eles exigem conhecimento em outras áreas. Por exemplo, o problema abaixo, que eu tive que quebrar muito a cabeça para resolver, pois exige muita visão espacial.

**(O queijo de Steiner)- Retirado de [1]- "Para fazer a sua pizza, Steiner teve que cortar, primeiro, o queijo. Imaginando que o espaço é um enorme queijo, você seria capaz de achar uma fórmula para o número máximos de pedaços que poderíamos obter ao cortá-lo por n planos?"

Bem, por hoje é só. Para ver mais, fiquem ligados, pois devo postar em breve a terceira parte desta série.

Se você gostou do blog, curta nossa página no Facebook e siga-nos por e-mail e no blog para receber nossas atualizações. Seus comentários são muito bem vindos, desde que respeitem as regras abaixo explicitadas. 

Até mais!

Bibliografia

1. Apostila 4- (distribuída no programa de iniciação cientifica da Obmep) - CAP: 2. Você pode baixa-la de graça aqui.

***LEMBRE-SE: Para melhorar a qualidade de nossas postagens, avalie este post. É rapidinho!

4 comentários:

  1. Brigadão Kara, salvou minha reputação!

    ResponderExcluir
    Respostas
    1. Obrigado pelo comentário. É muito bom saber que estamos ajudando alguém.

      Excluir
  2. Não sei se estou enganada, mas me parece que houve uma pequena inversão quando na Pizza de Steiner escreveu: "Observe que seguindo as regras acima, o n-ésimo corte cruzará n retas e n+1 regiões" Ao meu ver acho que ficaria assim: "Observe que seguindo as regras acima, o n-ésimo corte cruzará n-1 retas e obteremos n regiões". Se eu estiver enganada gostaria de ser esclarecida, se possível.

    ResponderExcluir
    Respostas
    1. Verdade, houve um erro de digitação, no lugar de "o n-ésimo corte cruzará n retas e..." coloquei : "o (n+1)-ésimo corte cruzará n retas e...". Como foi apenas um erro de digitação alterei apenas isso.

      Obrigado por notar esse erro, está ajudando a deixar o blog mais completo e preciso.

      Até mais!

      Excluir

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...