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,

é 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

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

, pois como [;nx^2=0;]

então

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;]

logo, para o passo base é valido

Supondo que [;n^3+(n+1)^3+(n+2)^3;]

é um múltiplo de [;9;]

, então,

será também múltiplo de [;9;]

for também.

Ou seja,

deve ser múltiplo de [;9;]

Como n é natural, fazendo [;n^2+3n+3=L;]

é natural também. Logo,

[;n^3+(n+1)^3+(n+2)^3 + 9L = (n+1)^3+(n+2)^3+(n+3)^3;]

como

é 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_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+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,

é 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