Indução Matemática

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!

Comentários

Anônimo8 de janeiro de 2013 às 18:34
Brigadão Kara, salvou minha reputação!
ResponderExcluir
Respostas
Anônimo24 de abril de 2013 às 19:45
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

Adicionar comentário

Postar um comentário

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.

A Matemática Pura

Pesquisar este blog

Indução Matemática - Parte II

Comentários

Postar um comentário