Indução matemática - Parte III -

Olá, gente! Estou trazendo a terceira postagem sobre o MIM ou PIF.

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