Indução matemática

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:

$[;m!=;]$ $[;\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;]$
$[;2^0=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, $[;d=n-2^k;]$ é 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;]$
$[;2^5>5^2;]$
Logo, o $[;P_(n);]$ é válido para $[;n=5;]$
Se $[;2^n>n^2;]$ 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!

Comentários

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 III -

Comentários

Postar um comentário