Mostrando postagens com marcador Provas por Indução Matemática. Mostrar todas as postagens
Mostrando postagens com marcador Provas por Indução Matemática. Mostrar todas as postagens

quinta-feira, 19 de setembro de 2013

Prova indutiva: n! > $2^n$ para n $\geq$ 4

Provaremos agora a desigualdade n! > $2^n$ para n $\geq$ 4. Mostraremos que a função fatorial cresce mais rápido que a função exponencial.

A prova é por indução em n:

  • Caso Base: Para n = 4, temos que $4! > 2^4$.
  • Hipótese de Indução: Vamos supor que $(n-1)! > 2^{n-1}$.
  • Caso Geral: Agora basta utilizar o resultado obtido na hipótese de indução e estender a solução para o caso geral, assim temos que
                               $2*(n-1)! > 2*2^{n-1}$
                       $2*(n-1)! > 2^n$  
         {como 2*(n-1)! é menor que n!, para n = 4, podemos substituí-lo por n! e mantemos a desigualdade}
                   $n! > 2^n$   C.Q.D.

sábado, 7 de setembro de 2013

Prova Indutiva: $2^n$ > $n^2$, para n $\geq$ 5

Continuando nossa série de posts sobre provas por indução, vamos mostrar que: $2^n$ > $n^2$, para n $\geq$ 5.

Prova por indução em n:

  • Caso Base: Para n = 5, $2^5 > 5^2$.
  • Hipótese de Indução: Vamos assumir que a inequação é valida para n-1, ou seja, $2^{n-1} > (n-1)^2$.
  • Caso Geral: Agora vamos utilizar a hipótese de indução e estender a solução, esta etapa também é conhecida como "passo indutivo".
                                                  $2 * 2^{n-1} > 2*(n-1)^2$     {multiplicando ambos os lados por 2}
                                                  $2^n > 2(n^2 - 2n + 1)$
                                                  $2^n > n^2 + n^2 - 4n + 2$    {como $-4n > -n^2$, vamos subtituí-lo por $n^2$}
                                                  $2^n > n^2 + n^2 - n^2 + 2$     {substituindo $n^2 + n^2 - n^2 + 2$ por $n^2 + n^2 - n^2$}
                                                  $2^n > n^2 + n^2 - n^2$
                                                  $2^n > n^2$                               C.Q.D.

Neste post, apresentamos a prova por indução de uma inequação. É interessante observar que a prova de inequações é um pouco diferente da prova de equações, pois ao trabalharmos com desigualdades podemos realizar algumas substituições que não seriam permitidas em equações com operador de igualdade.

quarta-feira, 4 de setembro de 2013

Prova Indutiva: Soma de uma série geométrica

Neste post, apresentaremos a prova por indução da fórmula que calcula a soma dos termos de uma progressão geométrica. 

                                                $\sum\limits_{i=0}^n r^i = \frac{r^{n + 1} - 1}{r - 1}$

A prova é por indução em n:

  • Caso Base: Para n = 0 temos, $\sum\limits_{i=0}^0 r^i = \frac{r ^ {0 + 1} - 1}{r - 1} = 1$.
  • Hipótese de Indução: Vamos assumir que a fórmula é válida para n-1. Logo, temos $\sum\limits_{i=0}^{n-1}r^i = \frac{r ^ {n -1 + 1} - 1}{r - 1}= \frac{r ^{n} - 1}{r - 1}$.
  • Caso Geral: Para compor o caso geral, vamos somar o elemento r^n a soma dos n-1 elementos da P.G. encontrada na hipótese de indução, temos
                                                                  $\sum\limits_{i=0}^n r^i=( \sum\limits_{i=0}^{n-1} r^i ) + r^n$

                                                                            $=\frac{r ^{n} - 1}{r - 1} + r^n$

                                                                            $=\frac{r ^{n} - 1 + (r-1)r^n}{r - 1}$

                                                                            $=\frac{r ^{n} - 1 + r^{n+1} - r^n}{r - 1}$
                                                                 
                                                                            $=\frac{r ^{n+1} - 1}{r - 1}$             C.Q.D.

segunda-feira, 2 de setembro de 2013

Prova Indutiva: 2 + 5 + 8 + ... + 3n-1 = $\frac{n(3n + 1)}{2}$

Neste post, apresentaremos a prova indutiva de que a soma 2 + 5 + 8 + ... + 3n-1 vale $\frac{n(3n + 1)}{2}$.

                                   $S{\tiny n} = 2 + 5 + 8 + ... + 3n-1 = \frac{n(3n + 1)}{2}$

A prova é por indução em n:

  • Caso Base: Para n = 1, temos que $\frac{1(3\times1 + 1)}{2} = 2$.
  • Hipótese de Indução: Vamos assumir que a fórmula vale para n-1, ou seja,
                                     $S{\tiny n-1} =\frac{(n-1)(3(n-1) + 1)}{2} = \frac{3n^2 - 5n + 2}{2}$.
  • Caso Geral: Vamos estender a solução adicionando o elemento (3n-1) a soma dos n-1 primeiros elementos que assumimos ser verdadeira na hipótese de indução, logo
                                                              $S{\tiny n} = S{\tiny n-1} + (3n-1)$

                                                              $S{\tiny n} = \frac{3n^2 - 5n + 2}{2}+ (3n-1)$

                                                              $S{\tiny n} = \frac{3n^2 - 5n + 2 + 6n - 2}{2}$

                                                              $S{\tiny n} = \frac{3n^2 + n}{2}$

                                                              {Colocando n em evidência}
                                                              $S{\tiny n} = \frac{n(3n + 1)}{2}$   C.Q.D.

@inductioncode

domingo, 18 de agosto de 2013

Mostre que a soma dos primeiros N números naturais ímpares é $N^2$

Neste post, vamos usar a indução matemática para mostrar que a soma S(n) = 1 + 3 + 5 + ... + (2n - 1) é igual a $n^2$. Como sabemos, uma prova por indução é dividida em três partes:

  • Caso Base
  • Hipótese de Indução
  • Caso Geral

Então, para o problema em questão temos que:
  • Caso Base: para n = 1 temos que $S(1) = 1^2 = 1$.
  • Hipótese de Indução: vamos assumir que a fórmula vale para n-1 elementos, ou seja, $S(n-1) = (n-1)^2$.
  • Caso Geral: Agora basta estender a solução. Para isso, vamos utilizar o resultado encontrado na hipótese de indução. Fazemos, S(n) = S(n-1) + (2n - 1) = $n^2$. C.Q.D.

Em breve teremos mais provas por indução, aguardem!!!
Siga o @inductioncode no Twitter e no Facebook