Matemática

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)

Mostre que:
$[;(x+y)^n= \displaystyle\sum_{k=0}^{n} {n \choose k} x^{n-k} \cdot y^k;]$ $[;\forall n \in \mathbb{N};]$

2- Mostre que:

$[;\frac{m!}{0!}+;]$ $[;\frac{(m + 1) !}{1 !} + \cdots + \frac{(m + n) !}{n !} = ;]$ $[;\frac{(m + n + 1) !}{n ! (m+1)};]$

$[;\forall;]$ [;m,n;]

$[;\in;]$ $[;\mathbb{N};]$

3- Prove que todo número natural pode ser escrito como a soma de diversas potências distintas de 2.

4- Mostre que: $[;2^n > n^2 \forall n \in \mathbb{N}, n\ge 5;]$

O primeiro problema eu "fiquei devendo" na ultima postagem, por isso, aqui vai a resolução.

1-Mostre que:

$[;(x+y)^n= \displaystyle\sum_{k=0}^{n} {n \choose k} x^{n-k} \cdot y^k;]$ $[;\forall n\in \mathbb{N};]$

Vamos primeiro verificar a base.

[;n=0;]

$[;(x+y)^0={0\choose 0} \cdot x^0 \cdot y^0 =1 ;]$

Logo, o passo base é verdadeiro.
Vamos supor que: $[;(x+y)^n=\displaystyle\sum_{k=0}^{n} {n\choose k} \cdot x^{n-k} \cdot y^k;]$
Expandindo o somatório para ajudar a vizualizar...
[;(x+y)^n;]

$[;={n \choose 0} x^n+;]$ $[; {n\choose 1} x^{n-1} \cdot y +;]$ $[;\cdots {n\choose n-1} x y^{n-1} + {n \choose n} y^n;]$

Então:

$[;(x+y)^n \cdot (x+y)=;]$

$[;{n \choose 0} x^{n+1};]$ $[; + {n\choose 1} x^n \cdot y + \cdots + {n \choose n-1} x^2 \cdot y^{n-1} +;]$ $[; {n \choose n} x \cdot y^n + ;]$

$[; {n \choose 0} x^n \cdot y + ;]$ $[; {n\choose 1} x^{n-1} \cdot y^2 +;]$ $[;\cdots + {n \choose n-1} x \cdot y^{n} + {n \choose n} y^{n+1};]$

Juntando os termos de expoente correspondente...
$[;(x+y)^n \cdot (x+y)=;]$ $[;{n \choose 0} x^{n+1} + \left({n\choose 1} + {n \choose 0}\right) x^n \cdot y +;]$ $[; \left( {n \choose 2} + {n \choose 1} \right) x^{n-1}y^2 +;]$ $[;\cdots + \left({n \choose n-1} + {n \choose n-2} \right) x^2 \cdot y^{n-1};]$
$[; + \left( {n \choose n} + {n \choose n-1} \right) x y^{n} +;]$ $[; {n \choose n} y^{n+1};]$

LEMBRANDO QUE:

$[;{n\choose k-1} + {n \choose k} = {n+1 \choose k};]$

e

$[;{n\choose 0} = {n+1 \choose 0};]$
$[;{n \choose n} = {n+1 \choose n+1};]$

Então:
$[;(x+y)^{n+1}=;]$ $[; {n+1 \choose 0} x^{n+1} + {n+1 \choose 1} x^n \cdot y + \cdots + { n+1 \choose n} x \cdot y^n + {n+1 \choose n+1} y^{n+1};]$
C.Q.D.
2- Mostre que:

$[;\frac{m!}{0!}+;]$ $[;\frac{(m + 1) !}{1 !} + \cdots + \frac{(m + n) !}{n !} = ;]$ $[;\frac{(m + n + 1) !}{n ! (m+1)};]$

$[;\forall;]$ [;m,n;]

$[;\in;]$ $[;\mathbb{N};]$

Observe que como m e n são números naturais, isso dá a possibilidade de escolher sobre qual variavel queremos aplicar indução. Isso é muito comum e você deve escolher- de preferência - a variavel que "der menos trabalho". Não há uma regra para saber qual a variavel vai dar menos trabalho. É nescessario ter uma boa intuição.

Vamos usar indução em n. Se quiser, use indução em m e compare os resultados.

Para a base [;n=0;]

$[;\frac{m !}{0 !} = m !;]$

Multiplicando por $[;\frac{m+1}{m+1};]$ temos:

$[;\frac{(m+1) !}{m+1};]$

logo, o passo base é verdadeiro.

Se $[;\frac{m !}{0 !} + \frac{(m + 1) !}{1 !} + \cdots + \frac{(m + n) !}{n !};]$ $[;= \frac{(m + n + 1) !}{n ! (m+1)};]$ então:

$[;\frac{m !}{0 !} + \frac{(m+1) !}{1 !} + \cdots + \frac{(m+n) !}{n !} +;]$ $[;\frac{(m+n+1) !}{(n+1) !};]$ $[;= \frac{(m+n+1) !}{n ! (m+1)} + \frac{(m+n+1) !}{(n+1) !};]$

igualando denominadores temos:

$[;\frac{(m+n+1) ! (n+1) + (m+n+1) ! (m+2)}{(n+1) ! (m+1)};]$ $[;=\frac{(m+n+2) !}{(n+1) ! (m+1)};]$

C.Q.D.

Para demonstrar pelo PIF, deduzimos $[;P_{n+1};]$ da proposição anterior [;P_n;]

. Porém, as vezes é nescessário adimitir que mais do que uma, as vezes todas, as proposições anteriores são verdadeiras. Esse tipo de indução é chamado de indução forte. Podemos enuncia-la assim:
Para verificar uma proposição para todo n natural usando indução forte você deve:
I) Verificar para a base
II) Mostrar que, a veracidade de todas as proposições [;P_1, P_2, ... P_n;]

implica na
veracidade de $[;P_{n+1};]$ .

3- Prove que todo número natural pode ser escrito como a soma de diversas potências distintas de 2.
Se [;n=1;]

Logo, a base é verdadeira.

Seja n um número natural qualquer. Seja então [;2^k;]

a maior potência de 2 menor ou igual a n.
Se [;2^k=n;]

então o problema acaba. Mas se [;2^k<n;]

então,

é menor que [;2^k;]

e menor que n.
Pela nossa Hipótese, qualquer número natural menor que n pode ser escrito como soma de
diversas potências distintas de 2. Com isso, d pode ser escrito como soma de diversas potências
distintas de 2, todas diferentes de [;2^k;]

com isso, n pode ser escrito como a soma de diversas
potências distintas de 2.

C.Q.D.

Observe que as vezes, para utilizar indução forte precisamos verificar mais do que $[;P_{n_0};]$ . Como na demonstração da fórmula de Binet feita nesta postagem AQUI.

O último problema é uma outra forma de utilizar indução, eu já usei numa postagem antiga pois é bem intuitivo.

Para demonstrar uma propriedade [;P_(n);]

$[;\forall n \in \mathbb{N}, n\ge a;]$ você deve:
I) Verificar se [;P_(a);]

é válido.

II) Verificar que a veracidade de [;P_(n);]

para todo natural, [;n > a;]

implica na veracidade de $[;P_{(n+1)};]$ .

Exemplo: 4- Mostre que: $[;2^n > n^2 \forall n \in \mathbb{N}, n\ge 5;]$
Verificando para a base, [;n=5;]

Logo, o

é válido para [;n=5;]

podemos somar [;2^n;]

a ambos os lados. Assim:
$[;2^{n+1}>n^2+2^n;]$ só que: [;2^n>2n+1;]

para todo $[;n \ge 3;]$ e consequêntemente, para $[;n \ge 5;]$ .
Logo, $[;2^{n+1}>n^2 + 2^n > n^2 + 2n + 1 = (n+1)^2;]$
C.Q.D.
Bem, por hoje é só! Na próxima postagem sobre esse tema, que provavelmente será a última
desta série, eu falarei sobre mais alguns últimos tópicos. Se você gostou do blog, recomende aos seus amigos no Facebook, Twitter ou G+ e inscreva-se por e-mail e no blog para receber nossas atualizações. Se gostou da postagem, avalie-a abaixo da postagem. É RAPIDINHO!
Até mais!

- Matemática Através De Problemas - Vi
Oi, pessoal! Dada a falta de tempo dos administradores do blog, não estamos conseguindo postar muito conteúdo. Para compensar a falta de material novo, apresentamos aqui mais uma leva de problemas interessantes: 1 - Ache todas as funções contínuas...

- Dois Problemas Interessantes Sobre Jogos
Hoje vou apresentar a vocês dois problemas de jogos interessantes que um amigo meu me propôs. Na verdade, um deles é apenas um erro de interpretação (e aquecimento) para o outro, porém eu gostei bastante das duas versões, logo, apresentarei as...

- "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 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...

- A Demonstração Por Indução
Esta postagem é a segunda da série sobre os números naturais. Na primeira enunciamos os chamados Axiomas de Peano e nesta vamos volver nossa atenção para o quinto deles, chamado o Princípio da Indução: Se X ? ? é tal que 1 ? X e, para todo...

Matemática