Embed Size (px)
Citation preview
VAMOS FALAR DE MATEMÁTICAProf. Marcelo Gama�
Princípio de indução �nita( Parte 2 - Doze problemas para entender indução )
�facebook.com/vamosfalardematematica
1/60
Sumário
1. Roteiro para provas por indução
2. Igualdades
3. Desigualdades
4. Divisibilidade
5. Recursividade
2/60
Prof. Marcelo Gama
Parte 1: Roteiro de uma prova porindução
1. Roteiro para provas por indução 3/60
Prof. Marcelo Gama
Os três passos
◦ Passo 1: Provar a validade da a�rmação para o valorinicial n0
◦ Passo 2: Supor que a a�rmação é válida para umcerto valor n = k
◦ Passo 3: Usar a informação do Passo 2 para provarque a a�rmação também é válida para n = k +1
1. Roteiro para provas por indução 4/60
Prof. Marcelo Gama
Os três passos
◦ Passo 1: Provar a validade da a�rmação para o valorinicial n0
◦ Passo 2: Supor que a a�rmação é válida para umcerto valor n = k
◦ Passo 3: Usar a informação do Passo 2 para provarque a a�rmação também é válida para n = k +1
1. Roteiro para provas por indução 4/60
Prof. Marcelo Gama
Os três passos
◦ Passo 1: Provar a validade da a�rmação para o valorinicial n0
◦ Passo 2: Supor que a a�rmação é válida para umcerto valor n = k
◦ Passo 3: Usar a informação do Passo 2 para provarque a a�rmação também é válida para n = k +1
1. Roteiro para provas por indução 4/60
Prof. Marcelo Gama
Os três passos
◦ Passo 1: Provar a validade da a�rmação para o valorinicial n0
◦ Passo 2: Supor que a a�rmação é válida para umcerto valor n = k
◦ Passo 3: Usar a informação do Passo 2 para provarque a a�rmação também é válida para n = k +1
1. Roteiro para provas por indução 4/60
Prof. Marcelo Gama
Parte 2: Igualdades
2. Igualdades 5/60
Prof. Marcelo Gama
Problema 1
1+3+·· ·+ (2n −1) = n2, para n ≥ 1
2. Igualdades 6/60
Problema 1 Prof. Marcelo Gama
1+3+·· ·+ (2n −1) = n2, para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 = 12 ( V )
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
1+3+·· ·+ (2k −1) = k2, para k ≥ 1
2. Igualdades 7/60
Problema 1 Prof. Marcelo Gama
1+3+·· ·+ (2n −1) = n2, para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 = 12 ( V )
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
1+3+·· ·+ (2k −1) = k2, para k ≥ 1
2. Igualdades 7/60
Problema 1 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1+3+·· ·+ (2n −1) = n2
◦ Queremos provar que
1+3+·· ·+ (2k −1)+ [2(k +1)−1] = (k +1)2
2. Igualdades 8/60
Problema 1 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1+3+·· ·+ (2n −1) = n2
◦ Queremos provar que
1+3+·· ·+ (2k −1)+ [2(k +1)−1] = (k +1)2
2. Igualdades 8/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] =
k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] = k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] = k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] = k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] = k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] = k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Problema 1 Prof. Marcelo Gama
◦ Prova:
1+3+·· ·+ (2k −1)︸ ︷︷ ︸passo 2
+ [2(k +1)−1] = k2 + [2(k +1)−1]
= k2 + [2k +2−1]
= k2 +2k +1
= (k +1)2
Portanto, a a�rmação está provada.
2. Igualdades 9/60
Prof. Marcelo Gama
Problema 2
1 ·1!+2 ·2!+·· ·+n ·n! = (n +1)!−1, para n ≥ 1
2. Igualdades 10/60
Problema 2 Prof. Marcelo Gama
1 ·1!+2 ·2!+·· ·+n ·n! = (n +1)!−1, para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 ·1! = (1+1)!−1 ou 1 = 1 (V)
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1 ·1!+2 ·2!+·· ·+k ·k ! = (k +1)!−1, para k ≥ 1
2. Igualdades 11/60
Problema 2 Prof. Marcelo Gama
1 ·1!+2 ·2!+·· ·+n ·n! = (n +1)!−1, para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 ·1! = (1+1)!−1 ou 1 = 1 (V)
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1 ·1!+2 ·2!+·· ·+k ·k ! = (k +1)!−1, para k ≥ 1
2. Igualdades 11/60
Problema 2 Prof. Marcelo Gama
1 ·1!+2 ·2!+·· ·+n ·n! = (n +1)!−1, para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 ·1! = (1+1)!−1 ou 1 = 1 (V)
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1 ·1!+2 ·2!+·· ·+k ·k ! = (k +1)!−1, para k ≥ 1
2. Igualdades 11/60
Problema 2 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1 ·1!+2 ·2!+·+n ·n! = (n +1)!−1
◦ Queremos provar que
1 ·1!+2 ·2!+·· ·+k ·k !+ (k +1) · (k +1)! = (k +2)!−1
2. Igualdades 12/60
Problema 2 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1 ·1!+2 ·2!+·+n ·n! = (n +1)!−1
◦ Queremos provar que
1 ·1!+2 ·2!+·· ·+k ·k !+ (k +1) · (k +1)! = (k +2)!−1
2. Igualdades 12/60
Problema 2 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1 ·1!+2 ·2!+·+n ·n! = (n +1)!−1
◦ Queremos provar que
1 ·1!+2 ·2!+·· ·+k ·k !+ (k +1) · (k +1)! = (k +2)!−1
2. Igualdades 12/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Problema 2 Prof. Marcelo Gama
◦ Prova:
1 ·1!+2 ·2!+·· ·+k ·k !︸ ︷︷ ︸passo 2
+(k +1) · (k +1)!
= [(k +1)!−1]+ (k +1) · (k +1)!
= (k +1)!+ (k +1) · (k +1)!−1
= (k +1)! · [1+ (k +1)]−1
= (k +1)! · [k +2]−1
= (k +2)!−1
Portanto, a a�rmação está provada.
2. Igualdades 13/60
Prof. Marcelo Gama
Problema 3
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n·(n+1)·(n+2)·(n+3)4
2. Igualdades 14/60
Problema 3 Prof. Marcelo Gama
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n·(n+1)·(n+2)·(n+3)4
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 ·2 ·3 = 1·(1+1)·(1+2)·(1+3)4 = 1·2·3·�4
�4ou
1 ·2 ·3 = 1 ·2 ·3
Portanto, a a�rmação é verdadeira para n = 1
◦ Passo 2: Supor que a a�rmação vale para n = k
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2) = k · (k +1) · (k +2) · (k +3)
4
2. Igualdades 15/60
Problema 3 Prof. Marcelo Gama
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n·(n+1)·(n+2)·(n+3)4
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 ·2 ·3 = 1·(1+1)·(1+2)·(1+3)4 = 1·2·3·�4
�4ou
1 ·2 ·3 = 1 ·2 ·3
Portanto, a a�rmação é verdadeira para n = 1
◦ Passo 2: Supor que a a�rmação vale para n = k
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2) = k · (k +1) · (k +2) · (k +3)
4
2. Igualdades 15/60
Problema 3 Prof. Marcelo Gama
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n·(n+1)·(n+2)·(n+3)4
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
1 ·2 ·3 = 1·(1+1)·(1+2)·(1+3)4 = 1·2·3·�4
�4ou
1 ·2 ·3 = 1 ·2 ·3
Portanto, a a�rmação é verdadeira para n = 1
◦ Passo 2: Supor que a a�rmação vale para n = k
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2) = k · (k +1) · (k +2) · (k +3)
4
2. Igualdades 15/60
Problema 3 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n · (n +1) · (n +2) · (n +3)
4
◦ Queremos provar que
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)+ (k +1) · (k +2) · (k +3)
= (k +1) · (k +2) · (k +3) · (k +4)
4
2. Igualdades 16/60
Problema 3 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n · (n +1) · (n +2) · (n +3)
4
◦ Queremos provar que
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)+ (k +1) · (k +2) · (k +3)
= (k +1) · (k +2) · (k +3) · (k +4)
4
2. Igualdades 16/60
Problema 3 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1 ·2 ·3+2 ·3 ·4+·· ·+n · (n +1) · (n +2) = n · (n +1) · (n +2) · (n +3)
4
◦ Queremos provar que
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)+ (k +1) · (k +2) · (k +3)
= (k +1) · (k +2) · (k +3) · (k +4)
4
2. Igualdades 16/60
Problema 3 Prof. Marcelo Gama
◦ Prova:
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)︸ ︷︷ ︸passo 2
+(k +1) · (k +2) · (k +3)
= k · (k +1) · (k +2) · (k +3)
4+ 4 · (k +1) · (k +2) · (k +3)
4
= (k +1) · (k +2) · (k +3)
4· (k +4)
= (k +1) · (k +2) · (k +3) · (k +4)
4
Portanto, a a�rmação está provada.
2. Igualdades 17/60
Problema 3 Prof. Marcelo Gama
◦ Prova:
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)︸ ︷︷ ︸passo 2
+(k +1) · (k +2) · (k +3)
= k · (k +1) · (k +2) · (k +3)
4+ 4 · (k +1) · (k +2) · (k +3)
4
= (k +1) · (k +2) · (k +3)
4· (k +4)
= (k +1) · (k +2) · (k +3) · (k +4)
4
Portanto, a a�rmação está provada.
2. Igualdades 17/60
Problema 3 Prof. Marcelo Gama
◦ Prova:
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)︸ ︷︷ ︸passo 2
+(k +1) · (k +2) · (k +3)
= k · (k +1) · (k +2) · (k +3)
4+ 4 · (k +1) · (k +2) · (k +3)
4
= (k +1) · (k +2) · (k +3)
4· (k +4)
= (k +1) · (k +2) · (k +3) · (k +4)
4
Portanto, a a�rmação está provada.
2. Igualdades 17/60
Problema 3 Prof. Marcelo Gama
◦ Prova:
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)︸ ︷︷ ︸passo 2
+(k +1) · (k +2) · (k +3)
= k · (k +1) · (k +2) · (k +3)
4+ 4 · (k +1) · (k +2) · (k +3)
4
= (k +1) · (k +2) · (k +3)
4· (k +4)
= (k +1) · (k +2) · (k +3) · (k +4)
4
Portanto, a a�rmação está provada.
2. Igualdades 17/60
Problema 3 Prof. Marcelo Gama
◦ Prova:
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)︸ ︷︷ ︸passo 2
+(k +1) · (k +2) · (k +3)
= k · (k +1) · (k +2) · (k +3)
4+ 4 · (k +1) · (k +2) · (k +3)
4
= (k +1) · (k +2) · (k +3)
4· (k +4)
= (k +1) · (k +2) · (k +3) · (k +4)
4
Portanto, a a�rmação está provada.
2. Igualdades 17/60
Problema 3 Prof. Marcelo Gama
◦ Prova:
1 ·2 ·3+2 ·3 ·4+·· ·+k · (k +1) · (k +2)︸ ︷︷ ︸passo 2
+(k +1) · (k +2) · (k +3)
= k · (k +1) · (k +2) · (k +3)
4+ 4 · (k +1) · (k +2) · (k +3)
4
= (k +1) · (k +2) · (k +3)
4· (k +4)
= (k +1) · (k +2) · (k +3) · (k +4)
4
Portanto, a a�rmação está provada.
2. Igualdades 17/60
Prof. Marcelo Gama
Problema 4
Encontrar uma fórmula para a soma
11×2 + 1
2×3 +·· ·+ 1n×(n+1)
e provar sua validade por indução.
2. Igualdades 18/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dada
Ï Para n = 1: 11×2 = 1
2
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dadaÏ Para n = 1: 1
1×2 = 12
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dadaÏ Para n = 1: 1
1×2 = 12
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dadaÏ Para n = 1: 1
1×2 = 12
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dadaÏ Para n = 1: 1
1×2 = 12
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dadaÏ Para n = 1: 1
1×2 = 12
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
◦ Passo 0: Encontrar uma fórmula para a soma dadaÏ Para n = 1: 1
1×2 = 12
Ï Para n = 2: 11×2 + 1
2×3 = 12 + 1
6 = 36 + 1
6 = 46 = 2
3
Ï Para n = 3: 11×2 + 1
2×3 +1
3×4 = 23 + 1
12 = 812 + 1
12 = 912 = 3
4
Ï Para n = 4: 11×2 + 1
2×3 + 13×4 + 1
4×5 = 34 + 1
20 = 1520 + 1
20 = 1620 = 4
5
Ï Para n:1
1×2 + 12×3 +·· ·+ 1
n×(n+1) = nn+1
◦ Esta é a fórmula que precisamos veri�car1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1, para n ≥ 1
2. Igualdades 19/60
Problema 4 Prof. Marcelo Gama
11×2 + 1
2×3 +·· ·+ 1n×(n+1) = n
n+1 , para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
11×2 = 1
1+1 ou 12 = 1
2
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)= k
k +1, para n ≥ 1
2. Igualdades 20/60
Problema 4 Prof. Marcelo Gama
11×2 + 1
2×3 +·· ·+ 1n×(n+1) = n
n+1 , para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
11×2 = 1
1+1 ou 12 = 1
2
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)= k
k +1, para n ≥ 1
2. Igualdades 20/60
Problema 4 Prof. Marcelo Gama
11×2 + 1
2×3 +·· ·+ 1n×(n+1) = n
n+1 , para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
11×2 = 1
1+1 ou 12 = 1
2
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)= k
k +1, para n ≥ 1
2. Igualdades 20/60
Problema 4 Prof. Marcelo Gama
11×2 + 1
2×3 +·· ·+ 1n×(n+1) = n
n+1 , para n ≥ 1
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
11×2 = 1
1+1 ou 12 = 1
2
Portanto, a a�rmação é verdadeira para n = 1.
◦ Passo 2: Supor que a a�rmação vale para n = k
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)= k
k +1, para n ≥ 1
2. Igualdades 20/60
Problema 4 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1
◦ Queremos provar que
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)+ 1
(k +1)× (k +2)= k +1
k +2
2. Igualdades 21/60
Problema 4 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1
◦ Queremos provar que
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)+ 1
(k +1)× (k +2)= k +1
k +2
2. Igualdades 21/60
Problema 4 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
1
1×2+ 1
2×3+·· ·+ 1
n × (n +1)= n
n +1
◦ Queremos provar que
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)+ 1
(k +1)× (k +2)= k +1
k +2
2. Igualdades 21/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.
2. Igualdades 22/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.
2. Igualdades 22/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.
2. Igualdades 22/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.
2. Igualdades 22/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.
2. Igualdades 22/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.
2. Igualdades 22/60
Problema 4 Prof. Marcelo Gama
◦ Prova:
1
1×2+ 1
2×3+·· ·+ 1
k × (k +1)︸ ︷︷ ︸passo 2
+ 1
(k +1)× (k +2)
= k
k +1+ 1
(k +1)× (k +2)
= k × (k +2)
(k +1)× (k +2)+ 1
(k +1)× (k +2)
= k2 +2k +1
(k +1)× (k +2)= (k +1)2
(k +1)× (k +2)=����(k +1)× (k +1)
����(k +1)× (k +2)
= k +1
k +2
Portanto, a a�rmação está provada.2. Igualdades 22/60
Prof. Marcelo Gama
Parte 2: Desigualdades
3. Desigualdades 23/60
Prof. Marcelo Gama
Problema 5
3n > 50n +1, para n ≥ 6
3. Desigualdades 24/60
Problema 5 Prof. Marcelo Gama
3n > 50n +1, para n ≥ 6
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 6
36 = 729 e 50×6+1 = 301, ou seja, 36 > 50×6+1
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
3k > 50k +1, para k ≥ 6
3. Desigualdades 25/60
Problema 5 Prof. Marcelo Gama
3n > 50n +1, para n ≥ 6
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 6
36 = 729 e 50×6+1 = 301, ou seja, 36 > 50×6+1
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
3k > 50k +1, para k ≥ 6
3. Desigualdades 25/60
Problema 5 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
3n > 50n +1
◦ Queremos provar que
3k+1 > 50(k +1)+1
3. Desigualdades 26/60
Problema 5 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
3n > 50n +1
◦ Queremos provar que
3k+1 > 50(k +1)+1
3. Desigualdades 26/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Problema 5 Prof. Marcelo Gama
◦ Prova:
3k+1 = 3 · 3k︸︷︷︸passo 2
> 3 · (50k +1)
≥ 150k +3
≥ 50k + (100k +3)︸ ︷︷ ︸k ≥ 6
≥ 50k + (100×6+3)
≥ 50k +603
> 50k +50+1
≥ 50(k +1)+1
Portanto, a a�rmação está provada.
3. Desigualdades 27/60
Prof. Marcelo Gama
Problema 6
n! > 3n, para n ≥ 7
3. Desigualdades 28/60
Problema 6 Prof. Marcelo Gama
n! > 3n, para n ≥ 7
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 7
7! = 5040 e 37 = 2187, ou seja, 7! > 37
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
k ! > 3k , para k ≥ 7
3. Desigualdades 29/60
Problema 6 Prof. Marcelo Gama
n! > 3n, para n ≥ 7
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 7
7! = 5040 e 37 = 2187, ou seja, 7! > 37
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
k ! > 3k , para k ≥ 7
3. Desigualdades 29/60
Problema 6 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
n! > 3n
◦ Queremos provar que
(k +1)! > 3k+1
3. Desigualdades 30/60
Problema 6 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
n! > 3n
◦ Queremos provar que
(k +1)! > 3k+1
3. Desigualdades 30/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Problema 6 Prof. Marcelo Gama
◦ Prova:
(k +1)! = (k +1) · k !︸︷︷︸passo 2
> (k +1)︸ ︷︷ ︸k ≥ 7
·3k
≥ 8 ·3k
> 3 ·3k
≥ 3k+1
Portanto, a a�rmação está provada.
3. Desigualdades 31/60
Prof. Marcelo Gama
Problema 7
(1+x)n ≥ 1+nx, para n ≥ 1 e x ≥ 0
3. Desigualdades 32/60
Problema 7 Prof. Marcelo Gama
(1+x)n ≥ 1+nx, para n ≥ 1 e x ≥ 0
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
(1+x)1 = 1+x e 1+1x = 1+x
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
(1+x)k ≥ 1+kx, para k ≥ 1 e x ≥ 0
3. Desigualdades 33/60
Problema 7 Prof. Marcelo Gama
(1+x)n ≥ 1+nx, para n ≥ 1 e x ≥ 0
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 1
(1+x)1 = 1+x e 1+1x = 1+x
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
(1+x)k ≥ 1+kx, para k ≥ 1 e x ≥ 0
3. Desigualdades 33/60
Problema 7 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
(1+x)n ≥ 1+nx, para n ≥ 1 e x ≥ 0
◦ Queremos provar que
(1+x)k+1 ≥ 1+ (k +1)x
3. Desigualdades 34/60
Problema 7 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
(1+x)n ≥ 1+nx, para n ≥ 1 e x ≥ 0
◦ Queremos provar que
(1+x)k+1 ≥ 1+ (k +1)x
3. Desigualdades 34/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Problema 7 Prof. Marcelo Gama
◦ Prova:
(1+x)k+1 = (1+x)k︸ ︷︷ ︸passo 2
(1+x)
≥ (1+kx)(1+x)
≥ 1+kx +x︸ ︷︷ ︸+kx2
≥ 1+x(k +1)+ kx2︸︷︷︸≥0
≥ 1+ (k +1)x
Portanto, a a�rmação está provada.
3. Desigualdades 35/60
Prof. Marcelo Gama
Parte 3: Divisibilidade
4. Divisibilidade 36/60
Prof. Marcelo Gama
Problema 8
23n −1 é divisível por 7 se n ≥ 0
4. Divisibilidade 37/60
Problema 8 Prof. Marcelo Gama
23n −1 é divisível por 7 se n ≥ 0
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 0 (vamos provar também para n = 1)
23·0 −1 = 20 −1 = 1−1 = 0 é divisível por 723·1 −1 = 23 −1 = 8−1 = 7 é divisível por 7
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
23k −1 é divisível por 7 se k ≥ 0ou 23k −1 = 7a, com a ∈Z
4. Divisibilidade 38/60
Problema 8 Prof. Marcelo Gama
23n −1 é divisível por 7 se n ≥ 0
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 0 (vamos provar também para n = 1)
23·0 −1 = 20 −1 = 1−1 = 0 é divisível por 7
23·1 −1 = 23 −1 = 8−1 = 7 é divisível por 7
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
23k −1 é divisível por 7 se k ≥ 0ou 23k −1 = 7a, com a ∈Z
4. Divisibilidade 38/60
Problema 8 Prof. Marcelo Gama
23n −1 é divisível por 7 se n ≥ 0
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 0 (vamos provar também para n = 1)
23·0 −1 = 20 −1 = 1−1 = 0 é divisível por 723·1 −1 = 23 −1 = 8−1 = 7 é divisível por 7
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
23k −1 é divisível por 7 se k ≥ 0ou 23k −1 = 7a, com a ∈Z
4. Divisibilidade 38/60
Problema 8 Prof. Marcelo Gama
23n −1 é divisível por 7 se n ≥ 0
◦ Passo 1: Provar que a a�rmação é verdadeira paran = 0 (vamos provar também para n = 1)
23·0 −1 = 20 −1 = 1−1 = 0 é divisível por 723·1 −1 = 23 −1 = 8−1 = 7 é divisível por 7
◦ Passo 2: Supor que a a�rmação é verdadeira paran = k
23k −1 é divisível por 7 se k ≥ 0ou 23k −1 = 7a, com a ∈Z
4. Divisibilidade 38/60
Problema 8 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
23n −1 é divisível por 7
◦ Queremos provar que
23(k+1) −1 é divisível por 7
ou 23(k+1) −1 = 7b, para algum b ∈Z
4. Divisibilidade 39/60
Problema 8 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
23n −1 é divisível por 7
◦ Queremos provar que
23(k+1) −1 é divisível por 7
ou 23(k+1) −1 = 7b, para algum b ∈Z
4. Divisibilidade 39/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Problema 8 Prof. Marcelo Gama
◦ Prova:
23(k+1) −1 = 23k+3 −1
= 23k︸︷︷︸23k −1 = 7a
·23 −1
= (7a +1) ·8−1
= 56a +8−1
= 56a +7
= 7× (8a +1)
Portanto, a a�rmação está provada.
4. Divisibilidade 40/60
Prof. Marcelo Gama
Problema 9
32n +3 ·5n é divisível por 4, para n ≥ 0
4. Divisibilidade 41/60
Problema 9 Prof. Marcelo Gama
32n +3 ·5n é divisível por 4, para n ≥ 0
◦ Passo 1: Provar que a a�rmação é válida para n = 0
32·0 +3 ·50 = 30 +3 ·50 = 1+3 ·1 = 4 é divisível por 4
◦ Passo 2: Supor que a a�rmação é válida para n = k
32k +3 ·5k é divisível por 4 se n ≥ 0ou 32k +3 ·5k = 4a, com a ∈Z
4. Divisibilidade 42/60
Problema 9 Prof. Marcelo Gama
32n +3 ·5n é divisível por 4, para n ≥ 0
◦ Passo 1: Provar que a a�rmação é válida para n = 0
32·0 +3 ·50 = 30 +3 ·50 = 1+3 ·1 = 4 é divisível por 4
◦ Passo 2: Supor que a a�rmação é válida para n = k
32k +3 ·5k é divisível por 4 se n ≥ 0ou 32k +3 ·5k = 4a, com a ∈Z
4. Divisibilidade 42/60
Problema 9 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
32n +3 ·5n é divisível por 4
◦ Queremos provar que
32(k+1) +3 ·5k+1 é divisível por 4
ou 32(k+1) +3 ·5k+1 = 4b, para algum b ∈Z
4. Divisibilidade 43/60
Problema 9 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
32n +3 ·5n é divisível por 4
◦ Queremos provar que
32(k+1) +3 ·5k+1 é divisível por 4
ou 32(k+1) +3 ·5k+1 = 4b, para algum b ∈Z
4. Divisibilidade 43/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Problema 9 Prof. Marcelo Gama
◦ Prova:
32(k+1) +3 ·5k+1 = 32k+2 +3 ·5k+1
= 32k︸︷︷︸32k +3 ·5k = 4a
·32 +3 ·5k ·51
= (4a −3 ·5k) ·9+15 ·5k
= 36a −27 ·5k +15 ·5k
= 36a −12 ·5k
= 4× (9a −3 ·5k)
Portanto, a a�rmação está provada.
4. Divisibilidade 44/60
Prof. Marcelo Gama
Parte 4: Recursividade
5. Recursividade 45/60
Prof. Marcelo Gama
Problema 10
◦ R$ 1500,00 foi depositado em um banco
◦ A cada mês é adicionado 2% de juros
a1 = 1500, an+1 = 1,02 ·an
◦ Qual o valor acumulado em n meses?
5. Recursividade 46/60
Problema 10 Prof. Marcelo Gama
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1500
◦ a2 = 1,02 ·a1 = 1,02 ·1500
◦ a3 = 1,02 ·a2 = 1,02 · (1,02 ·1500) = (1,02)2 ·1500
◦ a4 = 1,02 ·a3 = 1,02 · [(1,02)2 ·1500] = (1,02)3 ·1500
Parece que temos uma canditata a fórmula
◦ an = (1,02)n−1 ·1500, com n ≥ 1
5. Recursividade 47/60
Problema 10 Prof. Marcelo Gama
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1500
◦ a2 = 1,02 ·a1 = 1,02 ·1500
◦ a3 = 1,02 ·a2 = 1,02 · (1,02 ·1500) = (1,02)2 ·1500
◦ a4 = 1,02 ·a3 = 1,02 · [(1,02)2 ·1500] = (1,02)3 ·1500
Parece que temos uma canditata a fórmula
◦ an = (1,02)n−1 ·1500, com n ≥ 1
5. Recursividade 47/60
Problema 10 Prof. Marcelo Gama
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1500
◦ a2 = 1,02 ·a1 = 1,02 ·1500
◦ a3 = 1,02 ·a2 = 1,02 · (1,02 ·1500) = (1,02)2 ·1500
◦ a4 = 1,02 ·a3 = 1,02 · [(1,02)2 ·1500] = (1,02)3 ·1500
Parece que temos uma canditata a fórmula
◦ an = (1,02)n−1 ·1500, com n ≥ 1
5. Recursividade 47/60
Problema 10 Prof. Marcelo Gama
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1500
◦ a2 = 1,02 ·a1 = 1,02 ·1500
◦ a3 = 1,02 ·a2 = 1,02 · (1,02 ·1500) = (1,02)2 ·1500
◦ a4 = 1,02 ·a3 = 1,02 · [(1,02)2 ·1500] = (1,02)3 ·1500
Parece que temos uma canditata a fórmula
◦ an = (1,02)n−1 ·1500, com n ≥ 1
5. Recursividade 47/60
Problema 10 Prof. Marcelo Gama
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1500
◦ a2 = 1,02 ·a1 = 1,02 ·1500
◦ a3 = 1,02 ·a2 = 1,02 · (1,02 ·1500) = (1,02)2 ·1500
◦ a4 = 1,02 ·a3 = 1,02 · [(1,02)2 ·1500] = (1,02)3 ·1500
Parece que temos uma canditata a fórmula
◦ an = (1,02)n−1 ·1500, com n ≥ 1
5. Recursividade 47/60
Problema 10 Prof. Marcelo Gama
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1500
◦ a2 = 1,02 ·a1 = 1,02 ·1500
◦ a3 = 1,02 ·a2 = 1,02 · (1,02 ·1500) = (1,02)2 ·1500
◦ a4 = 1,02 ·a3 = 1,02 · [(1,02)2 ·1500] = (1,02)3 ·1500
Parece que temos uma canditata a fórmula
◦ an = (1,02)n−1 ·1500, com n ≥ 1
5. Recursividade 47/60
Problema 10 Prof. Marcelo Gama
an = (1,02)n−1 ·1500, com n ≥ 1
◦ Passo 1: Provar que a a�rmação é válida para n = 1
a1 = (1,02)1−1 ·1500 = (1,02)0 ·1500 = 1500
◦ Passo 2: Supor que a a�rmação é válida para n = k
ak = (1,02)k−1 ·1500, com k ≥ 1
5. Recursividade 48/60
Problema 10 Prof. Marcelo Gama
an = (1,02)n−1 ·1500, com n ≥ 1
◦ Passo 1: Provar que a a�rmação é válida para n = 1
a1 = (1,02)1−1 ·1500 = (1,02)0 ·1500 = 1500
◦ Passo 2: Supor que a a�rmação é válida para n = k
ak = (1,02)k−1 ·1500, com k ≥ 1
5. Recursividade 48/60
Problema 10 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
an = (1,02)n−1 ·1500
◦ Queremos provar que
ak+1 = (1,02)k ·1500
5. Recursividade 49/60
Problema 10 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
an = (1,02)n−1 ·1500
◦ Queremos provar que
ak+1 = (1,02)k ·1500
5. Recursividade 49/60
Problema 10 Prof. Marcelo Gama
◦ Prova:
ak+1 = 1,02 · ak︸︷︷︸passo 2
= 1,02 · [(1,02)k−1 ·1500]
= (1,02)k ·1500
Portanto, a a�rmação está provada.
A título de curiosidade, em um ano teríamos R$ 1865,06
5. Recursividade 50/60
Problema 10 Prof. Marcelo Gama
◦ Prova:
ak+1 = 1,02 · ak︸︷︷︸passo 2
= 1,02 · [(1,02)k−1 ·1500]
= (1,02)k ·1500
Portanto, a a�rmação está provada.
A título de curiosidade, em um ano teríamos R$ 1865,06
5. Recursividade 50/60
Problema 10 Prof. Marcelo Gama
◦ Prova:
ak+1 = 1,02 · ak︸︷︷︸passo 2
= 1,02 · [(1,02)k−1 ·1500]
= (1,02)k ·1500
Portanto, a a�rmação está provada.
A título de curiosidade, em um ano teríamos R$ 1865,06
5. Recursividade 50/60
Problema 10 Prof. Marcelo Gama
◦ Prova:
ak+1 = 1,02 · ak︸︷︷︸passo 2
= 1,02 · [(1,02)k−1 ·1500]
= (1,02)k ·1500
Portanto, a a�rmação está provada.
A título de curiosidade, em um ano teríamos R$ 1865,06
5. Recursividade 50/60
Problema 10 Prof. Marcelo Gama
◦ Prova:
ak+1 = 1,02 · ak︸︷︷︸passo 2
= 1,02 · [(1,02)k−1 ·1500]
= (1,02)k ·1500
Portanto, a a�rmação está provada.
A título de curiosidade, em um ano teríamos R$ 1865,06
5. Recursividade 50/60
Problema 10 Prof. Marcelo Gama
◦ Prova:
ak+1 = 1,02 · ak︸︷︷︸passo 2
= 1,02 · [(1,02)k−1 ·1500]
= (1,02)k ·1500
Portanto, a a�rmação está provada.
A título de curiosidade, em um ano teríamos R$ 1865,06
5. Recursividade 50/60
Prof. Marcelo Gama
Problema 11
Encontre uma fórmula fechada para a sequência
◦ a1 = 1
◦ an+1 =√
n+1n ·an, para n ≥ 1
Em seguida, prove sua validade por indução.
5. Recursividade 51/60
Problema 11 Prof. Marcelo Gama
an+1 =√
n+1n ·an , para n ≥ 1
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1
◦ a2 =√
21 ·a1 =
√21 ·1 =p
2
◦ a3 =√
32 ·a2 =
√32 ·
p2 =
p3
��p
2·���p
2 =p3
◦ a4 =√
43 ·a3 =
√43 ·
p3 =
p4
��p
3·���p
3 =p4
Parece que temos uma canditata a fórmula
◦ an =pn, com n ≥ 1
5. Recursividade 52/60
Problema 11 Prof. Marcelo Gama
an+1 =√
n+1n ·an , para n ≥ 1
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1
◦ a2 =√
21 ·a1 =
√21 ·1 =p
2
◦ a3 =√
32 ·a2 =
√32 ·
p2 =
p3
��p
2·���p
2 =p3
◦ a4 =√
43 ·a3 =
√43 ·
p3 =
p4
��p
3·���p
3 =p4
Parece que temos uma canditata a fórmula
◦ an =pn, com n ≥ 1
5. Recursividade 52/60
Problema 11 Prof. Marcelo Gama
an+1 =√
n+1n ·an , para n ≥ 1
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1
◦ a2 =√
21 ·a1 =
√21 ·1 =p
2
◦ a3 =√
32 ·a2 =
√32 ·
p2 =
p3
��p
2·���p
2 =p3
◦ a4 =√
43 ·a3 =
√43 ·
p3 =
p4
��p
3·���p
3 =p4
Parece que temos uma canditata a fórmula
◦ an =pn, com n ≥ 1
5. Recursividade 52/60
Problema 11 Prof. Marcelo Gama
an+1 =√
n+1n ·an , para n ≥ 1
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1
◦ a2 =√
21 ·a1 =
√21 ·1 =p
2
◦ a3 =√
32 ·a2 =
√32 ·
p2 =
p3
��p
2·���p
2 =p3
◦ a4 =√
43 ·a3 =
√43 ·
p3 =
p4
��p
3·���p
3 =p4
Parece que temos uma canditata a fórmula
◦ an =pn, com n ≥ 1
5. Recursividade 52/60
Problema 11 Prof. Marcelo Gama
an+1 =√
n+1n ·an , para n ≥ 1
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1
◦ a2 =√
21 ·a1 =
√21 ·1 =p
2
◦ a3 =√
32 ·a2 =
√32 ·
p2 =
p3
��p
2·���p
2 =p3
◦ a4 =√
43 ·a3 =
√43 ·
p3 =
p4
��p
3·���p
3 =p4
Parece que temos uma canditata a fórmula
◦ an =pn, com n ≥ 1
5. Recursividade 52/60
Problema 11 Prof. Marcelo Gama
an+1 =√
n+1n ·an , para n ≥ 1
Precisamos de uma fórmula para o cálculo direto de an
◦ a1 = 1
◦ a2 =√
21 ·a1 =
√21 ·1 =p
2
◦ a3 =√
32 ·a2 =
√32 ·
p2 =
p3
��p
2·���p
2 =p3
◦ a4 =√
43 ·a3 =
√43 ·
p3 =
p4
��p
3·���p
3 =p4
Parece que temos uma canditata a fórmula
◦ an =pn, com n ≥ 1
5. Recursividade 52/60
Problema 11 Prof. Marcelo Gama
an =pn, com n ≥ 1
◦ Passo 1: Provar que a a�rmação é válida para n = 1
a1 = 1 (é o valor dado pela recorrência)
a1 =p
1 = 1 (é o valor dado pela fórmula)
como são iguais, a fórmula está correta.
◦ Passo 2: Supor que a a�rmação é válida para n = k
ak =p
k, com k ≥ 1
5. Recursividade 53/60
Problema 11 Prof. Marcelo Gama
an =pn, com n ≥ 1
◦ Passo 1: Provar que a a�rmação é válida para n = 1
a1 = 1 (é o valor dado pela recorrência)
a1 =p
1 = 1 (é o valor dado pela fórmula)
como são iguais, a fórmula está correta.
◦ Passo 2: Supor que a a�rmação é válida para n = k
ak =p
k, com k ≥ 1
5. Recursividade 53/60
Problema 11 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
an =pn
◦ Queremos provar que
ak+1 =p
k +1
5. Recursividade 54/60
Problema 11 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
an =pn
◦ Queremos provar que
ak+1 =p
k +1
5. Recursividade 54/60
Problema 11 Prof. Marcelo Gama
◦ Prova:
ak+1 =√
k +1
k· ak︸︷︷︸
passo 2
=p
k +1
���
pk
·���p
k
=p
k +1
Portanto, a a�rmação está provada.
5. Recursividade 55/60
Problema 11 Prof. Marcelo Gama
◦ Prova:
ak+1 =√
k +1
k· ak︸︷︷︸
passo 2
=p
k +1
���
pk
·���p
k
=p
k +1
Portanto, a a�rmação está provada.
5. Recursividade 55/60
Problema 11 Prof. Marcelo Gama
◦ Prova:
ak+1 =√
k +1
k· ak︸︷︷︸
passo 2
=p
k +1
���
pk
·���p
k
=p
k +1
Portanto, a a�rmação está provada.
5. Recursividade 55/60
Problema 11 Prof. Marcelo Gama
◦ Prova:
ak+1 =√
k +1
k· ak︸︷︷︸
passo 2
=p
k +1
���
pk
·���p
k
=p
k +1
Portanto, a a�rmação está provada.
5. Recursividade 55/60
Problema 11 Prof. Marcelo Gama
◦ Prova:
ak+1 =√
k +1
k· ak︸︷︷︸
passo 2
=p
k +1
���
pk
·���p
k
=p
k +1
Portanto, a a�rmação está provada.
5. Recursividade 55/60
Prof. Marcelo Gama
Problema 12
Um problema envolvendo derivadas
◦ f0(x) = 1x
◦ fn+1(x) = f ′n(x), para n ≥ 1
Prove, por indução, que
fn(x) = (−1)n ·n! ·x−(n+1), para n ≥ 0
5. Recursividade 56/60
Problema 12 Prof. Marcelo Gama
fn(x) = (−1)n ·n! · x−(n+1), para n ≥ 0
◦ Passo 1: Provar que a a�rmação é válida para n = 0
f0(x) = (−1)0 ·0! ·x−(0+1) = 1 ·1 ·x−1 = 1
x
◦ Passo 2: Supor que a a�rmação é válida para n = k
fk(x) = (−1)k ·k ! · x−(k+1), para k ≥ 0
5. Recursividade 57/60
Problema 12 Prof. Marcelo Gama
fn(x) = (−1)n ·n! · x−(n+1), para n ≥ 0
◦ Passo 1: Provar que a a�rmação é válida para n = 0
f0(x) = (−1)0 ·0! ·x−(0+1) = 1 ·1 ·x−1 = 1
x
◦ Passo 2: Supor que a a�rmação é válida para n = k
fk(x) = (−1)k ·k ! · x−(k+1), para k ≥ 0
5. Recursividade 57/60
Problema 12 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
fn(x) = (−1)n ·n! · x−(n+1)
◦ Queremos provar que
fk+1(x) = (−1)k+1 · (k +1)! · x−(k+2)
5. Recursividade 58/60
Problema 12 Prof. Marcelo Gama
◦ Passo 3: O que queremos provar ?
Para saber, faça n = k +1 na expressão original
fn(x) = (−1)n ·n! · x−(n+1)
◦ Queremos provar que
fk+1(x) = (−1)k+1 · (k +1)! · x−(k+2)
5. Recursividade 58/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]
= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]
= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
Problema 12 Prof. Marcelo Gama
◦ Prova:
fk+1(x) = f ′k(x)︸ ︷︷ ︸
passo 2
= [(−1)k ·k ! · x−(k+1)]′
= (−1)k ·k ! · [−(k +1)x−(k+1)−1]= (−1)k ·k ! · [(−1)(k +1)x−(k+1)−1]= (−1)k · (−1) ·k ! · (k +1) · x−(k+1)−1
= (−1)k+1 · (k +1)! · x−(k+2)
Portanto, a a�rmação está provada.
5. Recursividade 59/60
OBRIGADO PELA ATENÇÃO
Professor Marcelo Gama
Para receber mais dicas como essa acompanhemeu trabalho através das redes sociais
◦ Curta minha página no FacebookVamos falar de Matemática
◦ Inscreva-se no meu canal canal do YouTubeVamos falar de Matemática
◦ Siga meu per�l no SlideshareMarcelo Gama 26
5. Recursividade 60/60
