Módulo 02: Indução matemática
* Esta obra é uma adptação do autor desse blog da disciplina de Fundamento de Algoritmo para Computação do curso de Tecnologia em Sistemas de Computacão/Cederj UFF das aulas originais cujo as autoras são: Sulamita Klein e Susana Scheimberg de Makler.
Revisão em 28/fev/2008 19:29
Conteúdo:
1. Introdução
2. Princípio da indução matemática (PIM)
3. Princípio da indução matemática generalizada
4. Questões de AP´s e AD´s do Cederj
5. Bibliografia
1. Introdução
Idéia intuitiva:
Exemplo:
- Consideremos uma sequência de dominós alinhados tal que: Se um cair ele vai derrubar o seguinte.
Formalização:
- Seja P(n) uma afirmação, para cada n
. - Se:
- (i) P(1) verdadeira e
- (ii) P(k) verdadeira
P (k + 1) verdadeira 
k . - Então P(n) verdadeira para todo n
(1) Base da indução: Mostrar que P(n) verdadeira para n = 1
(2) Hipótese de indução: Assumir que P(k) verdadeira para k
1(3) Passo indutivo:
Mostrar que P (k + 1) verdadeira, assumindo (2).
Exemplo:
- Mostre que 1 + 2 + 3 + ... + n =
k
- Seja P(n) : 1 + 2 + 3 + ... + n =
- P ( 1 ): 1 =
= 1 verdadeira
1:- 1 + 2 + .... + k =
- P (k) verdadeira P (k + 1) verdadeira
3. Princípio da indução matemática generalizada
- Lembremos a formulas do PIM:
Se:
(i) P (1) verdadeira e
(ii) P (k) verdadeira
P (k + 1) verdade 
k 
.Então P (n) verdadeira para todo n
.Para aplicarmos o PIM generalizado precisamos executar os três passos a seguir:
(1) Base da indução:
- Mostrar que P (n) verdadeira para n = n0
- Assumir que P (k) verdadeira para k
n0
- Mostrar que P (k + 1) verdadeira, assumindo a hipótese de indução (2)
- Mostre que
> 3n n k .
- Seja
4. Questões de AP´s e AD´s do Cederj
1) Cederj 2005/1 AD01 - Mostre usando indução matemática:
2 + 5 + 8 + ... + (3n - 1 ) =
n 
Resposta:
Por indução:
para n = 1, 3*1 - 1 = 2 =
= 2 é verdadeirasuponha verdadeira para n = k isto é, 2 + 5 + ... + ( 3k - 1 ) =
(Vamos mostrar que se é verdadeira para k
verdadeira para k + 1)Desenvolvendo para n = k + 1
Logo a expressão é verdadeira
n 2) Cederj 2005/2 AD01 - Mostre usando indução matemática:
Resposta:
Prova:
Por indução:
Base da indução:
Hipótese indução:
Suponha verdadeiro para n = k, isto é , P ( k ) é verdadeira:
Vamos mostrar que se P ( k ) é verdadeiro então é P ( k + 1 ) é verdadeiro, isto é:
Temos que provar que:
Desenvolvendo para n = k + 1 e usando a hipótese de indução, temos que:
Logo a expressão é verdadeira
n 3) Cederj 2006/1 AD01 - Mostre usando indução matemática:
Resposta:
Logo, pelo princípio da indução, a expressão é verdadeira
n 4) Cederj 2006/2 AD01 - Use o Princípio da Indução matemática para provar que:
Resposta:
Resposta:
Base da indução:
Hipótese de Indução:
Suponha verdadeira para n = k, isto é, P ( k ) é verdadeira:
Passo da indução:
Vamos mostrar que se P ( k ) é verdadeiro então P ( k + 1 ) é verdade, isto é,
temos que provar que: P ( k + 1 ) =
éverdadeira. De fato,
Logo, pelo princípio da indução, a expressão é verdadeira
n 5) Cederj 2007/2 AP01 - Mostre por Indução Matemática que:
n ( n + 1 ) > 4 n para todo natural n
4.Resposta:
Seja P ( n ) : n ( n + 1 ) > 4n, n
, n 4a) Base da indução:
Para n = 4, 4 ( 4 + 1 ) = 20 > 16 = 4 . 4 , logo P ( 4 ) é verdadeira.
b) Hipótese de Indução:
Suponha verdadeira para k
4, isto é, P ( k ) é verdadeira, para k 4:P ( k ) : k ( k + 1 ) > 4 k
Passo da Indução:
Vamos mostrar que se P ( k ) é verdadeiro então P ( k + 1 ) é verdadeiro, isto é, temos que provar que:
P ( k + 1 ) : k + 1 ( ( k + 1 ) + 1 ) = ( k + 1 ) ( k + 2 ) = k ( k + 1 ) + 2 ( k + 1 ) ......
5. Bibliografia
http://pt.wikipedia.org/wiki/Indu%C3%A7%C3%A3o_matem%C3%A1tica
http://www.cepa.if.usp.br/e-calculo/ferramentas/pif/pif.htm
http://www.e-escola.pt/site/topico.asp?topico=5&ordem=3&canal=4
Nenhum comentário:
Postar um comentário