Indução Matemática - Parte II
Matemática

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!




- Quebra-cabeça: Torre De Hanói
Entre os diversos puzzles (quebra-cabeças) disponíveis nas lojas de brinquedos encontramos aquele que se conhece geralmente por ?Torre de Hanói?. A ?Torre de Hanói? é constituída de uma base horizontal com três hastes verticais, como aquele visto...

- Indução Matemática - Parte Iii -
Olá, gente! Estou trazendo a terceira postagem sobre o MIM ou PIF. Clique aqui para ler a primeira e a segunda parte desta série Antes de começarmos, gostaria que tentasse resolver os problemas abaixo. 1- (A fórmula do Binômio de Newton) ...

- "demonstração Por Absurdo"
Olá, gente! Hoje falarei sobre o método de demonstração por redução ao absurdo. A teoria é muito curta e intuitiva, porém a pratica pode ser muito complicada. De forma didática, para demonstrar alguma proposição por absurdo você deve assumir...

- Indução Matematica - Parte I
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...

- Torre De Hanói E Relações De Recorrência
Neste post iremos tratar de um quebra-cabeças bastante interessante: A Torre de Hanói, esse jogo foi criado por Edouard Lucas inspirado em uma lenda, você pode saber um pouco mais da parte histórica clicando aqui. Aqui trataremos de uma forma para...



Matemática








.