Slides - Matemática Discreta - Prof Júlio Silveira

Prévia do material em texto

Matemática Discreta 
Prof. Júlio Silveira 
Apresentação 
• Objetivos 
– Introduzir conceitos matemáticos relativos a problemas que 
envolvam conjuntos discretos, utilizando definições, demonstrações 
e aplicações. 
• Competências 
– Resolver problemas, implementar soluções, e demonstrar afirmações 
decorrentes de Conjuntos Discretos, Análise Combinatória e Funções 
Recorrentes. 
Apresentação 
• Ementa 
– Conjuntos; Conjuntos Discretos e Contínuos; Relações e operações 
envolvendo conjuntos. 
– Contagem (combinatória) 
• Princípios fundamentais da Contagem; Permutações, Arranjos, Combinações; 
Princípio das Casas de Pombo 
– Recorrências 
• Definições recorrentes: Sequências e Conjuntos; Algoritmos recursivos. 
– Indução matemática (indução finita) 
Bibliografia 
• Básica 
• GERSTING, J. L. Fundamentos matemáticos para a ciência da computação. 4. 
ed. Rio de Janeiro: LTC, 2001. 
• SCHEINERMAN, Edward R. Matemática Discreta – Uma Introdução. São 
Paulo: Pioneira Thomson Learning, 2003. 
• SANTOS, José Plínio O.; MELLO, Margarida P.; MURARI, Idani T.C. Introdução à 
análise combinatória. 2. ed. Campinas, SP: UNICAMP, 1998. 
Bibliografia 
• Complementar 
• DOMINGUES, Hygino H. e Iezzi, Gelson. Álgebra Moderna. Rio de Janeiro: Atual, 2003. 
• LIPSCHUTZ, S.; LIPSON, M. Teoria e problemas de matemática discreta. 2. ed. Porto 
Alegre, RS: Bookman, 2004. 
• MELLO, M. P.; SANTOS, J. P.; MURARI, I. T. C. Introdução à Análise Combinatória. 1. Ed. 
Rio de Janeiro: Ciência Moderna, 2008. 
• MENEZES, Paulo B. Matemática Discreta para Computação e Informática. Série Livros 
Didáticos, número 16, Instituto de Informática da UFRGS, Porto Alegre, RS: Sagra 
Luzzatto, 2004. 
• SCHEINERMAN, Eduard R.. Matemática Discreta: uma introdução. SP, São Paulo: 
Thomson Learning, 2006. 
Aula 1 
• Conjuntos 
– Conceitos; definições; formas de representação 
– Propriedades; terminogia 
– Conjuntos Discretos e Contínuos 
– Relações: Pertinência e Inclusão 
Conjuntos 
• Objeto atômico 
• letra, número, animal, pessoa, palavra (?) 
• Conjunto: coleção não-ordenada de objetos distintos 
– Todo conjunto é caracterizado pela totalidade de seus elementos 
DOIS CONJUNTOS SÃO IGUAIS SE E SOMENTE SE 
TÊM EXATAMENTE OS MESMOS ELEMENTOS 
– Notação: 
• Elementos atômicos: letras minúsculas 
• Conjuntos: LETRAS MAIÚSCULAS 
 
Conjuntos 
• Formas de representação 
1. Enumeração 
• A = { mamão, kiwi, melão } = { kiwi, melão, mamão } 
• B = { a, e, i, o, u } = { o, a, i, u, e } 
• C = { 1, 2, 3,  , 10 } = { 10, 9, 8,  , 1 } = { 2, 10, 1, 5, 3, 9, 6, 4, 8, 7 } 
• IN = { 0, 1, 2, 3, 4,  } 
Conjuntos 
• Formas de representação 
1. Enumeração 
• A = { mamão, kiwi, melão } = { kiwi, melão, mamão } 
 
2. Diagrama de Venn 
mamão
melão
kiwi
A
Conjuntos 
• Formas de representação 
1. Enumeração 
• B = { a, e, i, o, u } = { o, a, i, u, e } 
• C = { 1, 2, 3,  , 10 } = { 10, 9, 8,  , 1 } = { 2, 10, 1, 5, 3, 9, 6, 4, 8, 7 } 
 
3. Por compreensão (propriedade ou condição) 
• B = { x | x é uma vogal minúscula do alfabeto brasileiro } 
• C = { x ∊ IN | 1 ≤ x ≤ 10 } 
 
Conjuntos 
• Exercício 
 ENUMERAÇÃO 
 { } 
 { 0, 2, 4, 6, 8, 10, 12,  } 
 { 1, 4, 9, 16, 25,  } 
 { 1, 4, 9, 16, 25, 36, 64, 72, 81, 100 } 
 { } 
 { } 
 { } 
 { 1, 2, 4, 8, 16, 32, 64, 128,  } 
 
 PROPRIEDADE 
= { x ∊ IN | 1 ≤ x ≤ 10 } 
= { } 
= { } 
= { } 
= { x | x = 2n; n ∊ IN } 
= { x | ∃ n ∊ IN e x = 3n } 
= { x | x = 2n+1; n  IN } 
= { } 
 
Conjuntos 
• Cardinalidade 
Notação |X| ou n(X) 
• Exemplos 
A = { mamão, kiwi, melão } ⇒ n(A) = 3 
| { 1, 2, 3,  , 10 } | = 10 
| { 123 } | = 1 
| IN | = ∞ 
 
 
Conjuntos 
• Conjunto vazio 
{ } ou ∅ ⇒ | { } | = 0 
 
• Conjunto unitário 
M = { x ∊ IN | 1 < x < 3 } = { 2 } ⇒ | M | = 1 
 
• Atenção! 
{ ∅ } NÃO É vazio! ⇒ | { ∅ } | = 1 
 
Conjuntos Numéricos 
• Conjuntos discretos 
Números naturais ℕ = { 0, 1, 2, 3, ... } 
Naturais positivos ℕ∗ = { 1, 2, 3, ... } 
Números inteiros ℤ = { ..., -3, -2, -1, 0, 1, 2, 3, ... } 
Inteiros não-negativos ℤ+ = { 0, 1, 2, 3, ... } 
Inteiros não-positivos ℤ− = { ..., -3, -2, -1, 0 } 
Inteiros positivos ℤ
∗
+
 = { 1, 2, 3, ... } 
Inteiros negativos ℤ
∗
−
 = { -1, -2, -3, ... } 
 
Conjuntos - Relações 
• Pertinência 
 
A = { a, b, c } 
 
 a  A 
 b  A 
 c  A 
 d  A 
 12  A 
 
b
a
c
A
Conjuntos - Relações 
• Inclusão (relação entre dois conjuntos) 
 
X ⊂ Y  X está contido em Y 
 ou 
 X é subconjunto de Y 
 
 X ⊂ Y se e somente se ∀x: x ∊ X  x ∊ Y 
 
Desta forma 
 
 X ⊄ Y se e somente se ∃x: x ∊ X e x  Y 
Conjuntos - Relações 
• Inclusão 
 
X = { a, b, c } 
Y = { a, b, c, d } 
 a ∊ X 
 b ∊ X 
 c ∊ X 
X ⊂ Y 
 a ∊ Y 
 b ∊ Y 
 c ∊ Y 
b
a
d
c
Y
X
Conjuntos - Relações 
• Inclusão 
 
X = { a, b, c, d } 
Y = { a, b, c } 
 a ∊ X 
 b ∊ X 
 c ∊ X 
 d ∊ X 
X ⊄ Y 
 a ∊ Y 
 b ∊ Y 
 c ∊ Y 
 d  Y 
b
a dc
Y
X
Conjuntos - Relações 
• Inclusão 
 
∅ ⊂ { a, b, c } ? 
 x ∊ { } e x  { a, b, c } ? 
S I M! 
b
a
c

 Não existe x que atenda esta condição! 
Conjuntos - Relações 
• Inclusão 
 
Qualquer que seja o conjunto X 
 
 ∅ ⊂ X 
 X ⊂ X 
 
• Atenção 
 a ⊄ { a, b, c } ⇒ a NÃO É SUBCONJUNTO de { a, b, c } 
Conjuntos - Relações 
• Notas de Aula 
Verifique: 
Conjuntos - Relações 
• Notas de Aula 
Exercício 
Obrigado! 
 
 
Aula 2 
• Conjuntos 
– Conjuntos das Partes 
– Operações com conjuntos 
– Cardinalidade da diferença 
– Princípio da Inclusão e Exclusão 
Conjunto das partes 
• Para todo conjunto X 
(X): Conjunto das partes (subconjuntos) de X 
 
 S  X  S  (X) 
 
Conjunto das partes 
• (X): Conjunto das partes (subconjuntos) de X 
Exemplos 
 
• A = { } (A) = { { } } ou (A) = { ∅ } 
• B = { a } (B) = { ∅, { a } } 
• C = { a, b } (C) = { ∅, { a } , { b } , { a, b } } 
 
• ( {a,b,c} ) = { ∅, { a } , { b } , { c } , { a, b } , { a, c } , { b, c } , { a, b, c } } 
Conjunto das partes 
• (X): Conjunto das partes (subconjuntos) de X 
Exemplos 
 
• A = { } |A| = 0 |(A)| = 1 
• B = { a } |B| = 1 |(B)| = 2 
• C = { a, b } |C| = 2 |(C)| = 4 
 
• |{a,b,c}| = 3 |( {a,b,c} )| = 8 
 
 |X| = n |(X)| = 2n 
Conjunto das partes 
• (X): Conjunto das partes (subconjuntos) de X 
– Exemplos 
 
• A = { } (A) = { { } } ou (A) = { ∅ } 
• B = { a } (B) = { ∅, { a } } 
• C = { a, b } (C) = { ∅, { a } , { b } , { a, b } } 
 
• ( {a,b,c} ) = { ∅, { a } , { b } , { c } , { a, b } , { a, c } , { b, c } , { a, b, c } } 
Operações com conjuntos 
• União: X  Y = { x | x  X OU x  Y } 
X Y
Operações com conjuntos 
• Interseção: X  Y = { x | x  X E x  Y } 
 
IMPORTANTE 
Quando X  Y =  
 X e Y são ditos 
 DISJUNTOS 
 
 
 
X Y
Operações com conjuntos 
• Diferença: X – Y = { x | x  X E x  Y } 
• Se Y  X, temos C YX : complemento de Y em relação a X 
X
Y
X Y
Operações com conjuntos 
• Complemento: XC = X’ = U – X = { x | x  U E x  X } 
 
X
U
Operações com conjuntos 
• Exemplo 
A = { 1, 3, 5, 7, 9 } 
B = { 3, 5, 6, 10, 11 } 
 
 
 
A  B = { 1, 3, 5, 6, 7, 9, 10, 11 } 
A  B = { 3, 5 } 
A – B = { 1, 7, 9 } 
 
 
5
7
1 6
10
A
3
9
B
11
Operações com conjuntos 
• Exemplo 
A = { 1, 3, 5, 7, 9 } | A | = 5 
B = { 3, 5, 6, 10, 11 } | B | = 5 
 
 
 
A  B = { 1, 3, 5, 6, 7, 9, 10, 11 } | A  B | = 8 
A  B = { 3, 5 } | A  B | = 2 
A – B = { 1, 7, 9 } | A – B | = 3 
 
 
5
7
1 6
10
A
3
9
B
11
Operações com conjuntos 
• Propriedades 
 
 
Comutatividade A  B = B  A A  B = B  A 
Associatividade (A  B)  C = A  (B  C) (A  B)  C = A  (B  C) 
Distributividade A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) 
Elemento NeutroA   =   A = A A  U = U  A = A 
Complemento A  A’ = U A  A’ =  
Operações com conjuntos 
• Cardinalidade da diferença 
 
| A | = 5 | A – B | = 3 
 
| B | = 5 | A  B | = 2 
 
 
 
 | A – B | = | A | – | B | ? 
 
 
 
 | A | – | B | = 0 
 
 
5
7
1 6
10
A
3
9
B
11
Não (nem sempre)! 
Operações com conjuntos 
• Cardinalidade da diferença 
 
| A | = 5 | A – B | = 3 
 
| B | = 5 | A  B | = 2 
 
 
 
 | A – B | = | A | – | A  B | 
 
 
 
 | A | – | A  B | = 5 – 2 = 3 
 
 
5
7
1 6
10
A
3
9
B
11
Operações com conjuntos 
• Princípio da Inclusão e Exclusão 
 
| A | = 5 | A  B | = 8 
 
| B | = 5 | A  B | = 2 
 
 
 
 | A  B | = | A | + | B | ? 
 
 
 
 | A | + | B | = 10 
 
 
5
7
1 6
10
A
3
9
B
11
Não (nem sempre)! 
Apenas se A e B 
são disjuntos. 
Operações com conjuntos 
• Princípio da Inclusão e Exclusão 
 
| A | = 5 | A  B | = 8 
 
| B | = 5 | A  B | = 2 
 
 
 
 | A  B | = | A | + | B | – | A  B | 
 
 
 
 | A | + | B | – | A  B | = 5 + 5 – 2 = 8 
 
5
7
1 6
10
A
3
9
B
11
Operações com conjuntos 
• Exercícios 
Notas de Aula 1.13, do 1) ao 9) 
 
 
Operações com conjuntos 
• Princípio da Inclusão e Exclusão para três conjuntos 
 
 
| A  B  C | = | A  ( B  C ) | = 
= | A | + | B  C | – | A  ( B  C ) | = 
= | A | + | B | + | C | – | B  C | – | A  ( B  C ) | 
= | A | + | B | + | C | – | B  C | – | (A  B)  (B  C) | 
= | A | + | B | + | C | – | B  C | – ( | A  B | + | B  C | – | A  B  C | ) 
= | A | + | B | + | C | – | A  B | – | A  C | – | B  C | + | A  B  C | 
Operações com conjuntos 
• Princípio da Inclusão e Exclusão para três conjuntos 
d
c
a
f
g
A
e
j
B
k
n
C
h i
l m
b
| A  B  C ) | = 14 
+ | A | = 8 a b c d e h i j 
+ | B | = 8 d e f g h i k n 
+ | C | = 7 h i j k l m n 
– | A  B | = – 4 d e h i 
– | A  C | = – 3 h i j 
– | B  C | = – 4 h i k n 
+ | A  B  C | = – 2 h i 
Operações com conjuntos 
• Exercícios - AVA 
– Na seção MATERIAL DIDÁTICO 
• Notas de Aula - Conjuntos, Pág 10 – EXERCÍCIOS 1.13 
– Na seção ATIVIDADES 
• Exercícios MatDisc - Conjuntos 
– Na seção MIDIATECA 
• Conjuntos Discretos: Teoria e Exercícios 
Obrigado! 
 
 
Aula 3 
• Contagem (Combinatória) 
– Princípio da Multiplicação 
– Princípio da Adição 
– Princípio da Inclusão e Exclusão 
 
Contagem 
• Princípio da Multiplicação 
– Exemplo: Batalha Naval 
• L = { a, b, c, d, e } 
C = { 1, 2, 3, 4, 5, 6, 7, 8 } 
 
Quantas opções de tiro? 
 1 2 3 4 5 6 7 8 
a 
b  
c 
d 
e 
5 x 8 = 40 
Contagem 
• Princípio da Multiplicação 
– Exemplo: Batalha Naval 
• L = { a, b, c, d, e } 
C = { 1, 2, 3, 4, 5, 6, 7, 8 } 
• Tiros: pares ordenados 
– T = L  C = { (l, c) | l  L e c  C } 
 1 2 3 4 5 6 7 8 
a 
b  
c 
d 
e 
(b,4)  T 
Contagem 
• Princípio da Multiplicação 
– Exemplo: Batalha Naval 
• L = { a, b, c, d, e } 
C = { 1, 2, 3, 4, 5, 6, 7, 8 } 
• Quantos tiros? 
 
| T | = | L  C | = | L |  | C | 
 
Assim: |T| = 5  8 = 40 
 1 2 3 4 5 6 7 8 
a 
b  
c 
d 
e 
Contagem 
• Princípio da Multiplicação 
– Para dois conjuntos X e Y 
 
 | X  Y | = |X|  |Y| 
 
 
Se temos n1 diferentes resultados para um evento E1 , e 
 n2 diferentes resultados para um 2º evento E2 , temos então 
 
 n1  n2 resultados distintos para a sequência dos dois eventos. 
Princípio da Multiplicação 
• Exemplo 
1) Gisele deseja formar um conjunto de calça-blusa para vestir-se. Se ela 
dispõe de 6 calças e 10 blusas para escolher, de quantos modos ela pode 
formar o conjunto? 
 
Resp. (c,b)  C  B |C| = 6 
 |B| = 10 
 
 | C  B | = 6  10 = 60 conjuntos 
 
 
Princípio da Multiplicação 
• Vale para mais conjuntos: | X  Y  Z | = |X||Y||Z| 
• Exemplo 
2) Gisele deseja formar um conjunto de calça-blusa-sapato para vestir-se. Se 
ela dispõe de 6 calças, 10 blusas e 8 sapatos para escolher, de quantos 
modos ela pode formar o conjunto? 
 
Resp. (c,b,s)  C  B  S |C| = 6 |B| = 10 |B| = 8 
 
 | C  B  S | = 6  10  8 = 480 conjuntos 
 
 
Princípio da Multiplicação 
• Exemplos 
3) Quantas placas de automóveis distintas podem existir no Brasil? 
 
Resp. L L L – D D D D 
26  26  26  10  10  10  10 = 263  104 placas distintas 
263  10  9  8  7 
4) Quantas placas de automóveis possuem todos os dígitos distintos? 
 
Resp. L L L – D D D D 
Princípio da Multiplicação 
• Exemplos 
5) Quantas placas de automóveis possuem letras e dígitos distintos? 
 
Resp. L L L – D D D D 
26  25  24  10  9  8  7 
26  1  1  10  10  10  10 = 26  104 
 
ou 260000 placas possíveis. 
6) Quantas placas de automóveis possuem todas as letras iguais? 
 
Resp. L L L – D D D D 
Princípio da Multiplicação 
• Exemplos 
7) Quantas placas de automóveis possuem todas as letras iguais e todos os 
dígitos distintos? 
 
Resp. L L L – D D D D 
26  1  1  10  9  8  7 = 26  10  9  8  7 
Contagem 
• Princípio da Adição 
– Para dois conjuntos disjuntos X e Y (X  Y = ) 
 
 | X  Y | = |X| + |Y| 
 
• 
 
Sejam dois eventos E1 e E2 disjuntos, com respectivamente 
 n1 e n2 resultados distintos. 
 
Então temos n1 + n2 resultados distintos para o evento “E1 ou E2”. 
Princípio da Adição 
• Exemplo 
8) Gisele mudou de ideia e resolveu usar um vestido. Como opções, ela tem 5 
vestidos curtos e 8 vestidos longos. Quantas opções de vestido ela possui? 
 
Resp. curto ou longo |C| = 5 
 | L | = 8 
 
| C  B | = | C | + | L | = 5 + 8 = 13 opções 
Como C  L =  
Princípio da Adição 
• Exemplos 
9) Quantas placas de veículos começam com a letra A ou com a letra B? 
 
Resp. L L L – D D D D 
Conjunto A = placas que começam com A: A L L – D D D D = 262  104 placas 
Conjunto B = placas que começam com B: B L L – D D D D = 262  104 placas 
Como A e B são disjuntos, pelo Princípio da Adição: 
 
262  104 + 262  104 = 2 x 262  104 
Princípio da Adição 
• Exemplos 
9) Quantas placas de veículos começam com a letra A ou com a letra B? 
 
Resp. L L L – D D D D 
 
Outra solução: usamos direto o Princípio da Multiplicação 
P L L – D D D D onde P = { A, B } 
2 x 262  104 
Princípio da Adição 
• Exemplos 
10) Quantas placas de veículos começam com vogal? 
 
Resp. A = placas que começam com A: ALL – DDDD = 262  104 placas 
E = placas que começam com E: ELL – DDDD = 262  104 placas 
I = placas que começam com I: ILL – DDDD = 262  104 placas 
O = placas que começam com O: OLL – DDDD = 262  104 placas 
U = placas que começam com U: ULL – DDDD = 262  104 placas 
Ou então: VLL – DDDD onde V = { A, E , I , O , U } 
5 x 262  104 
Princípio da Adição 
• Exemplos 
11) Quantos diferentes sufixos de telefone são formados apenas com dígitos 
distintos? 
 
Resp. 
 D1
 D2
 D3
 D4
 
10 x 9 x 8 x 7 
Princípio da Adição 
• Exemplos 
12) Sufixos de telefone D1
 D2
 D3
 D4
 
com todos os dígitos distintos, 
D1 é par E D2  5?
 
 {0,2,4,6,8} {5,6,7,8,9} 8 7 
 D1
 D2
 D3
 D4 
 5 ? 
 Solução: Princípio da Adição 
 {0,2,4} {5,6,7,8,9} 8 7 
 D1
 D2
 D3
 D4 
OU {6,8} {5,6,7,8,9} 8 7 
 D1
 D2
 D3
 D4 
Resp.: 3  5  8  7 + 2  4  8  7. 
Contagem 
• Princípio da Inclusão e Exclusão 
– Para dois conjuntos não disjuntos X e Y 
 
 | X  Y | = |X| + |Y| + | X  Y | 
 
Princípio da Inclusão e Exclusão 
• Exemplos 
13) Gisele foi escolher o vestido.Cores dos vestidos curtos: rosa, verde, preto, 
branco, azul; Cores dos vestidos longos: marfim, preto, branco, verde, lilás, 
grafite, turquesa, ocre. Quantas opções de cores ela tem para escolher? 
 
Resp. 
C = { r, v, p, b, a } | C | = 5 
L = { m, p, b, v, l , g, t, o } | L | = 8 
| C | + | L| + | C  L | = 
5 + 8 – 3 = 10 opções distintas de cor. 
|C|+|I| = 
C: começam com par: 263  5  103 
• Exemplos 
14) Placas que começam com dígito par 
OU terminam com dígito ímpar? 
 
Resp. 
 - |C ∩ I| 
Princípio da Inclusão e Exclusão 
263  104 
I : terminam com ímpar: 263  5  103 
ABC – 2233 
ABC – 2222 
ABC – 3333 
 – 263  52  102 
• Exercícios 
15) Sufixos de telefone em que a soma dos dois dígitos iniciais é igual a 8? 
 
 
Resp. 
Contagem 
 9  1  102 = 900 
 
 D1
 D2
 D3
 D4
 
 D1
 + D2 = 8 
• Exercícios 
16) Sufixos de telefone com dígitos distintos, a soma dos dois dígitos iniciais é 
igual a 8? 
 
 
Resp. 
Contagem 
 8  1  8  7 
 
 D1
 D2
 D3
 D4
 
 D1
 + D2 = 8 
• Exercícios 
17) Gisele possui 2 calças claras e 4 escuras. Quanto às blusas, são 3 claras e 
7 escuras. Gisele quer variar as cores, misturando as tonalidades claras com 
as escuras. De quantos modos ela pode formar o conjunto? 
 
 
Resp. 
Contagem 
 2  7 + 4  3 = 14 + 12 = 26 
Contagem 
• Exercícios - AVA 
– MATERIAL DIDÁTICO 
• Notas de Aula MatDisc – Contagem; 1.13 
– ATIVIDADES 
• Exercícios MatDisc - Contagem; 22) a 28) 
– MIDIATECA 
• Exercícios de Arranjos, Combinações e Permutações; 1) a 8) 
Obrigado! 
 
 
Aula 4 
• Contagem (Combinatória) 
– Permutações simples 
• Fatorial 
– Permutações com repetições 
– Arranjos Simples 
 
 
• Exemplo 
17) Quantos são os anagramas da palavra CONTAGEM? 
 
Resp. ___ ___ ___ ___ ___ ___ ___ ___ 
 
Permutações simples 
 8  7  6  5  4  3  2  1 
Anagramas: Permutações das 8 letras (distintas) 
Notação: P8 = 8! 
• Permutações simples 
– n objetos distintos 
– Arranjos ordenados 
• Os mesmos objetos dispostos em outra ordem = outra permutação 
– Notação 
• Pn ou P(n,n): número de permutações dos n objetos 
Permutações simples 
Pn = n  (n–1)  (n–2)  ...  3  2  1 Pn = n! ou 
• Fatorial de n (n ∊ IN): n! 
• Definição 1 
 
 
Permutações simples 
n! = 1  2  3  ...  n 
 
 ou 
 
n! = n  (n–1)  (n–2)  ...  3  2  1 
2! = 1  2 = 2 
1! = 1 
3! = 1  2  3 = 6 
0! = ? 
4! = 1  2  3  4 = 24 
0! = 1 
• Fatorial de n (n ∊ IN): n! 
• Definição 2 
 
 
Permutações simples 
n! = n  (n–1)  (n–2)  ...  3  2  1 
0! = 1 
1! = 
3! = 3  2! = 
4! = 4  3! = n! = n  (n–1)! 
2! = 2  1! = 
= 1  0! = 1  1 = 1 
2  1 = 2 
3  2 = 6 
4  6 = 24 
• Fatorial de n (n ∊ IN): n! 
• Definição 2 
 
 
Permutações simples 
n! = n  (n–1)!  𝑛 − 1 ! = 
𝑛!
𝑛
 
Exemplo: 3! = 
4!
4
 = 
4×3×2×1
4
 
Então 0! = 
1!
1
= 
1
1
= 1 
• Fatorial de n (n ∊ IN): n! 
• Definição 2 
– Definição por recorrência: 
 
 
Permutações simples 
n! = n  (n–1)! 
 
0! = 1 
• Exemplo 
18) Quantos anagramas da palavra CONTAGEM começam com vogal? 
 
Resp. { A,E,O } ___ ___ ___ ___ ___ ___ ___ 
Permutações simples 
 3 
3  P7 = 3  7! 
  7  6  5  4  3  2  1 
• Exemplo 
19) Quantos anagramas da palavra CONTAGEM começam com as três vogais? 
 
Resp. ___ ___ ___ ___ ___ ___ ___ ___ 
Permutações simples 
P3  P5 = 3!  5! 
3  2  1  5  4  3  2  1 
• Exemplo 
20) Um grupo de 11 homens e 8 mulheres deve formar uma fila. 
De quantas formas isso é possível? 
 
Resp. 
Permutações simples 
P19 = 19! 
• Exemplo 
21) O mesmo grupo com 11 homens e 8 mulheres deve forma uma fila. Quantas 
filas distintas podem ser formadas, estando os homens todos juntos, e as 
mulheres também? 
 
Resp. 
Permutações simples 
Homens depois mulheres: P11  P8 = 11!  8! 
 ou 
Mulheres depois homens: P8  P11 = 11!  8! 
2  P8  P11 = 2  11!  8! 
• Exemplo 
22) Uma bibliotecária recebeu 5 livros de Algoritmos, 4 de Lógica, e 7 de 
Programação, todos distintos entre si. Ela tem que organizá-los em uma 
prateleira, mantendo todos os livros de um mesmo assunto agrupados. De 
quantas formas ela pode organizar os livros? 
 
Resp. 
Permutações simples 
|A1A2...|L1L2...|P1P2... | 
Mas... podemos trocar a ordem dos assuntos. 
Permutando os assuntos: ALP, APL, LAP, LPA, PAL, PLA 
3!  5!  4!  7! = 5!  4!  7! 
• Exemplo 
– Quantos anagramas da palavra CASO? R.: 4! = 24 
– Quantos anagramas da palavra CASA? 
 
Permutações com repetições 
CA1SA2 
A1A2CS 
A1A2SC 
A1CA2S 
A1CSA2 
A1SA2C 
A1SCA2 
A2A1CS 
A2A1SC 
A2CA1S 
A2CSA1 
A2SA1C 
A2SCA1 
CA2SA1 CA1SA2 
Resp: 
P4
2
 = 
4!
2
 = 12 
• Exemplo 
– Quantos anagramas da palavra ARARA? 
 
Permutações com repetições 
A1R1A2R2A3 
A1R1A2R2A3 
A1R1A3R2A2 
A2R1A1R2A3 
A2R1A3R2A1 
A3R1A1R2A2 
A3R1A2R2A1 
Resp: 
P5
P2×P3
 = 
5!
2! ∙ 3!
 = 
5×4×3!
2 ∙ 3! 
 
A1R2A2R1A3 
A1R2A3R1A2 
A2R2A1R1A3 
A2R2A3R1A1 
A3R2A1R1A2 
A3R2A2R1A1 
= 10 
• Caso geral 
n objetos 
n1 ocorrências do mesmo objeto o1 
n2 ocorrências no mesmo objeto o2 
... 
nk ocorrências do mesmo objeto ok. 
 
Permutações dos n objetos = 
P𝑛
P𝑛
1
×P𝑛
2
× ⋯ ×P𝑛
𝑘
=
𝑛!
𝑛
1
!×𝑛
2
!×⋯×𝑛
𝑘
!
 
Permutações com repetições 
• Exemplo 
23) Existem quantos anagramas da palavra PROPORCIONAL? 
 
Resp. 
Permutações com repetições 
12 Letras: 2 P, 2 R, 3 O 
12!
3! 2! 2!
 
• Exemplo 
24) Quantos anagramas da palavra PROPORCIONAL começam com vogal? 
 
Resp.: usar o Princípio Aditivo 
Permutações com repetições 
A_____ = 11 Letras: 2 P, 2 R, 3 O 
11!
2! 2! 2!
 + 2 ∙
11!
2! 2! 3!
 
I______ = 11 Letras: 2 P, 2 R, 3 O 
O_____ = 11 Letras: 2 P, 2 R, 2 O 
• Desafios! 
– Quantos anagramas da palavra PROPORCIONAL começam com todas 
as vogais na frente das consoantes? 
– Quantos anagramas da palavra PROPORCIONAL contêm todas as 
vogais agrupadas, e também todas as consoantes agrupadas? 
– Quantos anagramas da palavra PROPORCIONAL contêm todas as 
vogais agrupadas? 
 
 
Permutações com repetições 
• Exemplo 
– Quantos diferentes sufixos (de números) de telefone com todos os 
dígitos distintos existem? 
 
Resp. ___ ___ ___ ___ 
Arranjos (ou Arranjos simples) 
 10  9  8  7 
Outra forma de resposta = 
10×9×8×7×𝟔×𝟓×𝟒×𝟑×𝟐×𝟏
𝟔×𝟓×𝟒×𝟑×𝟐×𝟏
 = 
𝟏𝟎! 
𝟔!
 
• Arranjos – ou Arranjos Simples 
– n objetos distintos 
– Seleção de r objetos 
• Sem reposição 
– A ordem da seleção influi 
• Variação na ordem = arranjos distintos. Ex.: 1289  1298 
 
– Dizemos arranjos de n tomados r : 𝑨
𝒓
𝒏
 ou 𝐏
𝒓
𝒏
 ou 𝐏(𝒏, 𝒓) 
 
Arranjos 
• Arranjos – ou Arranjos Simples – de n objetos tomados r 
– Notação 
 𝐴
𝑟
𝑛
 ou P
𝑟
𝑛
 ou P 𝑛, 𝑟 
 
• n objetos distintos entre si 
• Seleção de r objetos 
• Seleção sem reposição 
• A ordem da seleção influi. 
Ex.: 1289  1298 
 
Arranjos 
𝐴
𝑟
𝑛
= 
𝑛!
(𝑛 − 𝑟)!
 
• Voltando ao exemplo anterior 
– Quantos diferentes sufixos (de números) de telefone com todos os 
dígitos distintos existem? 
 
Resp. 
• n = 10 
• r = 4 
• Sem repetição 
• A ordem influi 
 
 
Arranjos 
𝐴
4
10
= 
10!
10 − 4 !
=
10!
6!
=
10 ∙ 9 ∙ 8 ∙ 7 ∙ 𝟔!
𝟔!
= 10 × 9 × 8 × 7 
• Exemplo 
25) Quantas placas de automóveis possuem letras e dígitos distintos? 
 
Resp.: usar o Princípio Multiplicativo com dois eventos 
 Escolher as letras e depois escolher os dígitos. 
Arranjos 
P 26,3 × P 10,4 =
26 × 25 × 24 × 23!
23! 
 × 10 × 9 × 8 × 7 
• Exemplo 
26) Quantos números de 3 algarismos distintos podem ser escritos com os 
dígitos 1, 3, 4, 5, 6, 8, e 9? 
 
Resp.: 
Arranjos 
210567
!4
!4567
)!37(
!7
)3,7(37
3
7 



 PPA
Arranjos com n = 7 er = 3 
• Exemplo 
27) Temos uma prova olímpica individual com 10 competidores. De quantas 
formas distintas as medalhas de ouro, prata e bronze podem ser 
distribuídas? 
Arranjos 
Resposta nas Notas de Aula 
Obrigado! 
 
 
Aula 5 
• Contagem (Combinatória) 
– Combinações simples 
– Exercícios 
 
 
• Exemplo 
– Conjunto com 5 estudantes { Ana, Bruno, Carlos, Diana, Edna } 
 
A. Montar chapa (Presidente, Vice-presidente, Secretário) para o grêmio 
• Seleção sem repetição 
• A ordem influi: ABC é uma chapa; BAC é outra chapa 
 
• Solução: arranjos de 5 tomados 3 
 
 
Combinações Simples 
Resp.: 𝐴
3
5
= 5 × 4 × 3 = 𝟔𝟎 chapas distintas 
• Exemplo 
– Conjunto com 5 estudantes { Ana, Bruno, Carlos, Diana, Edna } 
 
B. Selecionar 3 alunos para representar a faculdade em uma gincana de 
Matemática Discreta. Quantas equipes podem ser formadas? 
• Seleção sem repetição 
• A ordem NÃO influi: ABC e BAC são a mesma equipe. 
 
• Solução: combinações de 5 tomados 3 
 
 
Combinações Simples 
n! = 1  2  3  ...  n 
 
 ou 
 
n! = n  (n–1)  (n–2)  ...  3  2  1 
Notação: 𝐂
𝟑
𝟓
 ou 𝐂 𝟓, 𝟑 
• Exemplo 
– E = { A, B, C, D, E }. Selecionar uma equipe com 3 alunos. 
Vamos enumerar os 60 arranjos: 
 
 
 
Combinações Simples 
Com ABC: Com ABD: Com ABE: 
 ABE 
 AEB 
 BAE 
 BEA 
 EAB 
 EBA 
3! arranjos 
Com ACD: 
ABC 
ACB 
BAC 
BCA 
CAB 
CBA 
6 arranjos 
ABD 
ADB 
BAD 
BDA 
DAB 
DBA 
6 arranjos 
Com ACE: 
Com BCD: 
Com BCE: 
Com BDE: 
Com CDE: 
Com ADE: 
Cada combinação “está relacionada” 
a um grupo de 3! arranjos contendo 
os mesmos alunos. 
 
Número de combinações (grupos): 
 60 / 3! 
• Exemplo 
– E = { A, B, C, D, E }. Selecionar uma equipe com 3 alunos. 
 
Vamos dividir os 60 arranjos em grupos de 3! arranjos (grupos com 
os mesmos alunos). Quantos grupos (combinações) existem? 
 
Resp.: 
 
 
 
Combinações Simples 
C
3
5
 = 
𝐴
3
5
3!
 = 
60
6
 = 10 combinações 
• Exemplo 
– E = { A, B, C, D, E }. Selecionar uma equipe com 3 alunos. 
 
Vamos calcular de outra forma? 
 
Resp.: 
 
 
 
Combinações Simples 
C
3
5
 = 
𝐴
3
5
3!
 = 
5!
2! 
⋅
1
3! 
 = 
5×4× 3! 
2 ⋅ 3! 
 = 
20
2
 = 10 combinações 
• Caso geral 
– n objetos distintos 
– Selecionar r objetos, sem repetição 
– A ordem NÃO influi 
– Combinações de n tomados r 
Combinações Simples 
C
𝑟
𝑛
 = 
𝐴
𝑟
𝑛
𝑟!
 = 
𝒏!
(𝒏−𝒓)! ⋅ 𝒓!
 
• Exemplo 
28) De um grupo de 5 pessoas, quantas equipes com 3 componentes podem ser 
formadas? 
 
Resp.: já utilizamos a fórmula 
Combinações Simples 
C
3
5
 = 
𝐴
3
5
3!
 = 
5!
2! ⋅ 3!
 = 
5×4× 3! 
2 ⋅ 3! 
 = 
20
2
 = 10 combinações 
• Exemplo 
29) De um grupo de 11 homens e 8 mulheres, queremos formar um júri com 4 
membros. De quantas formas distintas o júri pode ser formado? 
 
Resp.: 
Combinações Simples 
C
4
19
 = 
19!
15! ⋅4!
 = 
19×18×17×16× 15! 
4 ⋅ 3 ⋅ 2 ⋅ 15! 
 
= 19 × 6 × 17 × 2 combinações 
Obs.: nas Notas de Aula as simplificações foram diferentes 
• Exemplo 
30) Grupo de 11 homens e 8 mulheres, júri com 4 membros. De quantas formas 
distintas o júri pode ser formado somente com membros do mesmo sexo? 
 
Resp.: 
Combinações Simples 
C
4
11
 = 
11!
7! ⋅4!
 + 
8!
4! ⋅4!
 
= 
11×10×9×8× 7! 
4 ⋅ 3 ⋅ 2 ⋅ 7! 
+
8×7×6×5× 4! 
4 ⋅ 3 ⋅ 2 ⋅ 4! 
 
= 11 × 10 × 3 
C
4
8
 + 
+ 7 × 2 × 5 combinações 
• Exemplo 
31) Grupo de 11 homens e 8 mulheres, júri com 4 membros. De quantas formas 
distintas o júri pode ser formado contendo metade de cada sexo? 
 
Resp.: 
Combinações Simples 
C
2
11
 = 
11!
9! ⋅ 2!
×
8!
6! ⋅ 2!
 
= 
11×10× 9! 
2 ⋅ 9! 
×
8×7× 6! 
2 ⋅ 6! 
 
= 11 × 5 
C
2
8
 × 
 × 4 × 7 combinações 
• Exemplo 
32) Grupo de 11 homens e 8 mulheres, júri com 4 membros. De quantas formas 
distintas o júri pode ser formado contendo mais homens do que mulheres? 
 
Resp.: 
Combinações Simples 
C
3
11
 = 
11!
8! ⋅3!
 × 
8!
7! ⋅1!
 = 
11×10×9× 8! 
3 ⋅ 2 ⋅ 8! 
×
8× 7! 
1 ⋅ 7! 
 C
1
8
 × 
= 11 × 5 × 3 × 8 + 11 × 10 × 3 combinações 
C
4
11
 = 
11!
7! ⋅ 4!
 = 11 × 10 × 3 C
0
8
 × 
ou 
• Vamos trabalhar? 
33) Gisele tem 12 amigos, mas ela só pode convidar 6 deles para a sua festa. De 
quantas formas distintas ele pode formar a lista de convidados? 
34) Imagine que, dentre os 12 amigos de Gisele, 2 não se falam, e ela não pode 
convidar ambos. De quantas formas distintas ele pode formar a lista de 
convidados sem que ambos estejam presentes? 
35) Imagine que exista um casal entre os 12 amigos de Gisele, e ela não pode 
convidar um deles apenas. De quantas formas distintas ele pode formar a 
lista de convidados com esta restrição? 
 
Combinações Simples 
Contagem 
• Exercícios - AVA 
– MATERIAL DIDÁTICO 
• Notas de Aula MatDisc – Exercícios 33) a 35) 
– ATIVIDADES 
• Exercícios MatDisc - Contagem; 29) a 47) 
– MIDIATECA 
• Exercícios de Arranjos, Combinações e Permutações; 9) a 33) 
Obrigado! 
 
 
Aula 6 
• Contagem (Combinatória) 
– Princípio das Casas de Pombo 
 
 
 
• Se existem n pombos para ocupar k casas, e n > k, então 
pelo menos uma casa será ocupada por mais de 1 pombo. 
 
De outra forma 
 
• Se mais de n itens são colocados em k caixas, e n > k, então 
pelo menos uma caixa conterá mais de um item. 
Princípio das Casas de Pombo 
• Exemplo 43 (livro-texto, pág. 165) 
– Quantas pessoas precisam estar presentes em uma sala para garantir 
que duas delas tenham nomes começando com a mesma letra. 
• Resposta: no mínimo 27 pessoas 
• Justificativa As casas (ou caixas) são as letras do alfabeto = 26. 
 Os pombos (ou itens) são as pessoas = 27. 
 Associamos cada pessoa à letra inicial do seu prenome 
Com 26 pessoas, é possível que uma pessoa tenha nome iniciado por A, outra por B, e 
assim por diante. Ou seja, uma pessoa associada a cada uma das 26 letras 
do alfabeto. A chegada de uma 27ª pessoa impõe que pelo menos 
2 delas tenham nomes iniciados com mesma letra. 
Princípio das Casas de Pombo 
• PROBLEMA PRÁTICO 29 (livro-texto, pág. 165) 
– Quantas vezes é preciso jogar um dado de modo a garantir que um 
mesmo valor apareça duas vezes. 
• Casas: 
Pombos: 
• Resposta: 
 
 
Princípio das Casas de Pombo 
no mínimo 7 tentativas 
número de faces de um dado = 
número de tentativas. 
6 
Com apenas 6 tentativas, podemos ter cada uma dela associada a um dos seis possíveis 
valores, e diferente dos outros cinco. Ou seja, cada valor ocorrerá exatamente uma vez. 
Uma 7ª tentativa impõe que seu valor, sendo um dos 6 possíveis, já tenha 
sido obtido antes. Assim, teremos necessariamente um valor repetido. 
• Exemplo 44 (livro-texto, pág. 165) 
– Estude; e depois... 
 
 Explique como resolver! 
 
Princípio das Casas de Pombo 
• Exemplo (material do prof. Ricardo Mesquita) 
Princípio das Casas de Pombo 
• Exemplo (material do prof. Ricardo Mesquita) 
Princípio das Casas de Pombo 
• Outro exemplo (material do prof. Ricardo Mesquita) 
Princípio das Casas de Pombo 
• Princípio das Casas de Pombo – versão geral 
– Se 𝑛 objetos devem ser colocados em 𝑘 caixas, então existirá 
pelo menos uma caixa contendo, no mínimo, 𝑛/𝑘 objetos. 
 
 𝑛/𝑘 ⇒ função “teto”. 
 
 2 = 2 2.0 = 2 2.0001 = 3 2.999 = 3 
 
Princípio das Casas de Pombo 
• Outro exemplo (material do prof. Ricardo Mesquita) 
 
 
 
 
Resposta: 
 Sendo 5 o número de casas (cada conceito permitido). 
Com 25 estudantes (pombos) poderemos ter cada conceito associado a 𝟐𝟓/𝟓 = 𝟓. 𝟎 = 5. 
Ou seja 5 estudantes em cada conceito. Com 26 estudantes, podemos garantir que pelo 
menos um dos conceitos foi obtido por 26/5 = 𝟓. 𝟐 = 6 alunos. 
Princípio das Casas de Pombo 
Contagem 
• Exercícios - AVA 
– MIDIATECA 
• Material do prof. Ricardo Mesquita. 
• Princípio das Casas de Pombos I 
 Livro-texto: pág. 167, exercícios 13 a 21. 
• Princípio das Casas de Pombos II 
Obrigado! 
 
 
Aula 7 
•Indução Matemática 
 ou Indução Finita 
 
Indução Matemática 
• Exemplo 1 
– Considere a seguinte igualdade 
 
 𝑖
𝑛
𝑖=1
 = 
 𝑖
𝑛
𝑖=1
 = 
𝑛 𝑛 + 1
2
 , ∀𝑛 ∈ ℕ
∗
 
= 
𝑛 𝑛 + 1
2
 1 + 2 + 3 + ⋯+ 𝑛 
ou seja 
Indução Matemática 
• Vamos conferir a igualdade para alguns valores? 𝒊
𝒏
𝒊=𝟏
 = 
𝒏 𝒏 + 𝟏
𝟐
 
• n = 1 ⇒ 
• n = 2 ⇒ 
• n = 3 ⇒ 
 𝑖
𝟐
𝑖=1
 = 1 + 𝟐 = 𝟑 
 𝑖
𝟏
𝑖=1
 = 𝟏 
 𝑖
𝟑
𝑖=1
 = 1 + 2 + 𝟑 = 𝟔 
𝟑 ⋅ 3 + 1
2
=
𝟑 ∙
2
= 𝟑 ∙ 2 = 𝟔 
𝟐 ⋅ 2 + 1
2
=
𝟐 ∙ 3
2
= 𝟑 
𝟏 ⋅ 1 + 1
2
=
𝟏 ∙ 2
2
= 𝟏 
Indução Matemática 
• Vamos conferir a igualdade para alguns valores? 𝒊
𝒏
𝒊=𝟏
 = 
𝒏 𝒏 + 𝟏
𝟐
 
 𝑖
𝟐𝟎
𝑖=1
 = 1 + 2 + 3 + ⋯𝟐𝟎 = 
 
 𝑖
𝟏𝟎
𝑖=1
 = 1 + 2 + 3 + ⋯𝟏𝟎 = 
𝟓 ⋅ 5 + 1
2
=
5 ∙ 6
2
= 5 ∙ 3 = 𝟏𝟓 𝑖
𝟓
𝑖=1
 = 1 + 2 + 3 + 4 + 𝟓 = • n = 5 ⇒ 
• n = 10 ⇒ 
• n = 20 ⇒ 
Confira! 
Calcule! 
𝟏𝟎 ⋅ 11
2
= 5 ∙ 11 = 𝟓𝟓 
Indução Matemática 
• Como provar? 
 
 
 
Primeiro Princípio de Indução 
 𝑖
𝑛
𝑖=1
 = 
𝑛 𝑛 + 1
2
, ∀𝑛 ∈ ℕ
∗
 
Prof. Ricardo Mesquita 
Indução Matemática 
– Imagine que você esteja subindo uma escada infinitamente alta. Como você será 
capaz de saber se será capaz de chegar a um degrau arbitrariamente alto? 
03/20 
Primeiro Princípio da Indução – Prof. Ricardo Mesquita 
– Você pode inicialmente fazer as seguintes hipóteses sobre a sua capacidade de subir: 
1. Você consegue alcançar o primeiro degrau. 
2. Uma vez chegado a um degrau, você sempre será capaz de chegar ao próximo. 
– Se a proposição 1 e a condicional 2 são verdadeiras, então, pela proposição 1, você 
consegue chegar no primeiro degrau e, portanto, pela 2, consegue chegar no segundo. 
Novamente pela 2, consegue chegar no terceiro. Mais uma vez, pela 2, chega no 
quarto degrau e assim por diante. 
– Assim, podemos concluir que 
 você poderá subir tão alto quanto quiser. 
05/20 
Primeiro Princípio da Indução – Prof. Ricardo Mesquita 
– Note que, no exemplo, ambas as hipóteses são necessárias. 
• Se apenas a primeira fosse verdadeira, não teríamos a garantia de passar do 
primeiro degrau. 
• Por outro lado, se apenas a segunda fosse verdadeira, poderíamos não ser 
capazes de começar nunca!... 
– Numerando os degraus... 
• Vamos considerar uma propriedade 
que cada degrau identificado possa ter... 
 
06/20 
Primeiro Princípio da Indução – Prof. Ricardo Mesquita 
– Vamos usar a notação P(n) para dizer que o inteiro positivo n tem a 
propriedade P. 
– Por analogia, vamos usar a mesma “técnica” usada para subir a escada, para 
provar que, qualquer que seja o inteiro positivo n, temos P(n). 
– Precisamos provar as proposições: 
1. P(1) [ Ou seja, 1 tem a propriedade P. ] 
2. Para qualquer inteiro positivo k, P(k)  P(k+1) [ Se qualquer número tem a propriedade P, 
 o próximo também tem. ] 
– Se pudermos provar ambas as proposições, 1 e 2, então 
P(n) e válida para qualquer inteiro positivo n. 
 
 07/20 
Primeiro Princípio da Indução – Prof. Ricardo Mesquita 
– O primeiro princípio de indução matemática é uma condicional, com 
uma conclusão na forma “P(n) e verdade para todo inteiro positivo n”. 
• A técnica da indução se mostra mais apropriada para provarmos que alguma 
coisa é verdade para todo inteiro positivo n (conjunto dos números naturais). 
• Estrutura: 
1. P(1) 
2. k ( P(k) é verdade  P(k + 1) também é verdade ) 
 
provar 
provar supor 
08/20 
Primeiro Princípio da Indução – Prof. Ricardo Mesquita 
Indução Matemática 
• Provar por indução 
 
– Base: 
 
 
– Passo: 
n = 1  𝑖
𝟏
𝑖=1
 = 𝟏 1 ⋅ 1 + 1
2
=
1 ∙ 2
2
= 𝟏 
∀𝑘 𝑖
𝑘
𝑖=1
 = 
𝑘 𝑘 + 1
2
 ⟹ 𝑖
𝑘+1
𝑖=1
 = 
𝑘 + 1 𝑘 + 2
2
 
 𝑖
𝑛
𝑖=1
 = 
𝑛 𝑛 + 1
2
 , ∀𝑛 ∈ ℕ
∗
 
 
? 
– Passo: hipótese de indução 
1 + 2 + 3 + ⋯+ 𝑘 + 𝒌 + 𝟏 = 1 + 2 + 3 + ⋯+ 𝑘 𝑖
𝑘+1
𝑖=1
 = 
Indução Matemática 
 𝑖
𝑘
𝑖=1
 = 
𝑘 𝑘 + 1
2
 
 𝑖
𝑘+1
𝑖=1
 = 
 𝑖
𝑘+1
𝑖=1
= 
𝒌 𝑘 + 1 + 𝟐 𝑘 + 2
2
= 
 
𝑘 𝑘 + 1
2
+ 𝑘 + 1 = Pela hipótese de indução ⇒ 
Com (k+1) em evidência ⇒ 
 𝑖
𝑘
𝑖=1
 + 𝑘 + 1 
𝑘 𝑘 + 1 + 2 𝑘 + 1
2
 
1 + 2 + 3 + ⋯+ 𝑘 + 𝒌 + 𝟏 
 𝑘 + 1 𝑘 + 2 
2
 
Indução Matemática 
• Exemplo 2: 
 
 𝑖 ⋅ 𝑖! 
𝑛
𝑖=1
 = 𝑛 + 1 ! − 1, ∀𝑛 ∈ ℕ
∗
 
4 + 1 ! − 1 = 5! − 1 𝑖 ⋅ 𝑖!
𝟒
𝑖=1
 = 1 ⋅ 1! + 2 ⋅ 2! + 3 ⋅ 3! + 4 ⋅ 4! 
• n = 4 
= 1 + 2 ⋅ 2 + 3 ⋅ 6 + 4 ⋅ 24 
= 1 + 4 + 18 + 96 = 𝟏𝟏𝟗 
120−1 = 𝟏𝟏𝟗 
Indução Matemática 
• Provar por indução 
 
– Base: 
 
 
– Passo: 
n = 1  𝑖 ⋅ 𝑖!
𝟏
𝑖=1
 = 1 ⋅ 1! = 𝟏 1 + 1 ! − 1 = 2! − 1 = 𝟏 
∀𝑘 𝑖 ⋅ 𝑖!
𝑘
𝑖=1
 = 𝑘 + 1 ! − 1 ⟹ 𝑖 ⋅ 𝑖!
𝑘+1
𝑖=1
 = 𝑘 + 2 ! − 1 
 
? 
 𝑖 ⋅ 𝑖! 
𝑛
𝑖=1
 = 𝑛 + 1 ! − 1, ∀𝑛 ∈ ℕ
∗
 
– Passo: hipótese de indução 𝑖 ⋅ 𝑖! 
𝑘
𝑖=1
 = 𝑘 + 1 ! − 1 
1 ⋅ 1! + 2 ⋅ 2! + 3 ⋅ 3! + ⋯+ 𝑘 ⋅ 𝑘! + 𝒌 + 𝟏 ⋅ 𝒌 + 𝟏 ! = 𝑖 ⋅ 𝑖!
𝑘+1
𝑖=1
 = 
Indução Matemática 
 𝑖 ⋅ 𝑖!
𝑘+1
𝑖=1
 = 
 𝑖 ⋅ 𝑖!
𝑘+1
𝑖=1
= 𝒌 + 𝟏 + 𝟏 𝑘 + 1 ! + 1 = 
𝒌 + 𝟏 ! − 𝟏 + 𝑘 + 1 𝑘 + 1 ! = Pela hipótese de indução ⇒ 
Com (k+1)! em evidência ⇒ 
 𝑖 ⋅ 𝑖!
𝑘
𝑖=1
 + 𝒌 + 𝟏 𝒌 + 𝟏 ! 
𝒌 + 𝟏 𝑘 + 1 ! + 𝑘 + 1 ! − 1 
 𝑘 + 2 𝑘 + 1 ! -1 
 𝑖 ⋅ 𝑖!
𝑘+1
𝑖=1
= 𝒌 + 𝟐 ! − 1 
1 ⋅ 1! + 2 ⋅ 2! + 3 ⋅ 3! + ⋯+ 𝑘 ⋅ 𝑘! + 𝒌 + 𝟏 ⋅ 𝒌 + 𝟏 ! 1 ⋅ 1! + 2 ⋅ 2! + 3 ⋅ 3! + ⋯+ 𝑘 ⋅ 𝑘! + 𝒌 + 𝟏 ⋅ 𝒌 + 𝟏 ! 
Indução Matemática 
• Exemplo 3: 
 
 
1
 𝑖 ⋅ 𝑖 + 1 
𝒏
𝑖=1
 = 
𝒏
𝑛 + 1
 , ∀𝑛 ∈ ℕ
∗
 
 
1
 𝑖 ⋅ 𝑖 + 1 
𝟑
𝑖=1
 =
1
 1 ⋅ 2 
 +
1
 2 ⋅ 3 
+
1
 𝟑 ⋅ 4 
 = 
• n = 3 
1
 2 
 +
1
 6 
+
1
 12 
= 
6 + 2 + 1
12
 
=
9
 3
 12 4 
= 
𝟑
 4 
 
Indução Matemática 
• Provar por indução 
 
– Base: 
 
 
– Passo: 
n = 1  
1
 𝑖 ⋅ 𝑖 + 1 
𝟏
𝑖=1
 =
1
 𝟏 ⋅ 2 
=
𝟏
 𝟐 
 
𝟏
 𝟏 + 1 
 =
𝟏
 𝟐 
 
∀𝑘 
1
 𝑖 ⋅ 𝑖 + 1 
𝑘
𝑖=1
 =
𝒌
𝒌 + 1
 ⟹ 
1
 𝑖 ⋅ 𝑖 + 1 
𝑘+1
𝑖=1
 =
𝒌 + 𝟏
𝑘 + 2
 
 
? 
 
1
 𝑖 ⋅ 𝑖 + 1 
𝒏
𝑖=1
 = 
𝒏
𝑛 + 1
 , ∀𝑛 ∈ ℕ
∗
 
– Passo: hipótese de indução 
1
1 ⋅ 2
+
1
2 ⋅ 3
+
1
3 ⋅ 4
+ ⋯+
1
𝑘 ⋅ 𝑘 + 1
 + 
𝟏
𝒌 + 𝟏 ⋅ 𝒌 + 𝟐
 = 
1
1 ⋅ 2
+
1
2 ⋅ 3
+
1
3 ⋅ 4
+ ⋯+
1
𝑘 ⋅ 𝑘 + 1
 + 
 
𝑖
𝑖 ⋅ 𝑖 + 1
𝑘+1
𝑖=1
= 
Indução Matemática 
𝑘
𝑘 + 1
 + 
1
𝑘 + 1 ⋅ 𝑘 + 2
 = Pela hipótese de indução ⇒ 
 
1
𝑖 ⋅ 𝑖 + 1
𝑘
𝑖=1
 + 
𝟏
𝒌 + 𝟏 ⋅ 𝒌 + 𝟐
 
1
1 ⋅ 2
+
1
2 ⋅ 3
+
1
3 ⋅ 4
+ ⋯+
1
𝑘 ⋅ 𝑘 + 1
 + 
 
1
 𝑖 ⋅ 𝑖 + 1 
𝑘
𝑖=1
 =
𝒌
𝒌 + 1
 
 
𝑖
𝑖 ⋅ 𝑖 + 1
𝑘+1
𝑖=1
 = 
𝑘 ⋅ 𝑘 + 2 + 1
𝑘 + 1 ⋅ 𝑘 + 2
= 
𝑘2 + 2𝑘 + 1
𝑘 + 1 ⋅ 𝑘 + 2
 
𝑘 + 1 2
𝑘 + 1 ⋅ 𝑘 + 2
 = 
𝑘 + 1 ⋅ 𝑘 + 1
𝑘 + 1 ⋅ 𝑘 + 2
 
𝑖
𝑖 ⋅ 𝑖 + 1
𝑘+1
𝑖=1
 = = 
𝒌 + 𝟏
𝑘 + 2
 
Indução Matemática 
• AVA: Exercícios 
– MATERIAL DIDÁTICO 
• Slides: Indução Matemática – prof. Ricardo Mesquita 
• Slides: Demonstrações por Indução – prof. Ricardo Mesquita 
– MIDIATECA 
• Princípio de Indução Matemática - Livro-texto: págs. 76 – 88. 
 Exercícios 2.2: págs. 84 a 88. 
Indução Matemática 
• AVA: MIDIATECA 
• Princípio de Indução Matemática – Livro-texto: págs. 76 – 88. 
Obrigado! 
 
 
Aula 8 
• Recorrências 
– Sequências 
– Conjuntos 
– Operações e funções (matemáticas) 
– Algoritmos ou funções (computacionais) 
 
 
Recorrências 
• Conceito de Recorrência 
– Definição de algo que se “autorreferencia” 
• Contextos 
– Operações ou funções (matemáticas) recorrentes 
– Algoritmos ou funções (computacionais) recursivos(as) 
– Sequências definidas por recorrência 
– Conjuntos definidos por recorrência 
 
 
• Fatorial 
 f(n) = 1  2  3  ...  n 
 ou 
 n! = 1  2  3  ...  n 
De outra forma: 
 n! = n  (n–1)  (n–2)  ...  3  2  1 
Recorrências: operações/funções (matemáticas) 
2! = 1  2 = 2 
1! = 1 
3! = 1  2  3 = 60! = 1 
4! = 1  2  3  4 = 24 
• Exemplo 1 
Fatorial: definição por recorrência 
n! = n  (n–1)  (n–2)  ...  3  2  1 
0! = 1 
1! = 1  0! = 
3! = 3  2! = 
4! = 4  3! = 
n! = n  (n–1)! 
2! = 2  1! = 
1  1 = 1 
2  1 = 2 
3  2 = 6 
4  6 = 24 
(n–1)! 
Recorrências: operações/funções (matemáticas) 
0! = 1 
, n > 0 
CONDIÇÃO DE PARADA BASE 
PASSO 
• Operações/funções definidas por Recorrência 
– BASE 
• Definição “direta” (não recorrente) do valor da função 
• Função definida para um ou mais valores “iniciais” 
• Condição de parada 
– PASSO 
• Definição “recorrente” da operação 
• Operação/função será definida a partir dos resultados 
previamente obtidos pela aplicação de si mesma para 
outros valores (em geral, menores) 
Recorrências: operações/funções (matemáticas) 
• Exemplo 2 
 f (m,0) = 1, m ∊ ℝ* 
 f (2,0) = 
f (2,2) = 2 ⋅ f (2,1) = 
f (2,3) = 2 ⋅ f (2,2) = 
f (m, n) = m ⋅ f (m, n–1), m ∊ ℝ* e n ∊ ℕ* 
f (2,1) = 2 ⋅ f (2,0) = 
Recorrências: operações/funções (matemáticas) 
1 
2 ⋅ 1 = 2 
2 ⋅ 2 = 22 
2 ⋅ 22 = 23 
f (m,n) = mn, m ∊ ℝ* e n ∊ ℕ 
Faltar provar ⇒ Resolução de Recorrências! 
BASE 
PASSO 
• Exemplo 2: outras notações 
 
m0 = 1, m ∊ ℝ* 
mn = m ⋅ mn–1, m ∊ ℝ* e n ∊ ℕ* 
Recorrências: operações/funções (matemáticas) 
1, n = 0 
m ⋅ mn–1, n > 0 
mn = m ∊ ℝ* e n ∊ ℕ 
BASE 
PASSO 
BASE 
PASSO 
• Exemplo 3 
 f (m,0) = 0, m ∊ ℝ 
 f (2,0) = 
f (2,2) = 2 + f (2,1) = 
f (2,3) = 2 + f (2,2) = 
f (m, n) = m + f (m, n–1), m ∊ ℝ e n ∊ ℕ* 
f (2,1) = 2 + f (2,0) = 
Recorrências: operações/funções (matemáticas) 
0 
2 + 0 = 2 
2 + 2 = 2 ⋅ 2 
2 + 2 ⋅ 2 = 2 ⋅ 3 
Faltar provar ⇒ Resolução de Recorrências! 
f (m,n) = m ⋅ n, m ∊ ℝ e n ∊ ℕ 
BASE 
PASSO 
• Exemplo 3: outras notações 
 
Recorrências: operações/funções (matemáticas) 
m ⋅ 0 = 0, m ∊ ℝ 
m ⋅ n = m + m ⋅ (n–1), m ∊ ℝ e n ∊ ℕ* 
0, n = 0 
m + m ⋅ (n–1), n > 0 
m ⋅ n = m ∊ ℝ* e n ∊ ℕ 
BASE 
PASSO 
BASE 
PASSO 
• Exemplo: S = 2, 9, 16, 23, 30, ... 
Recorrências: sequências 
S7 = S100000 = ? 42325  S ? 
 n  ℕ | Sn = 42325 ? 
ou 
44 
S1: 1º termo S1 = 2 Sn: n-ésimo termo ou termo geral 
S2: 2º termo S2 = 9 
 
• Sequências – Formas de especificação 
1. Por enumeração: S = 2, 9, 16, 23, 30, ... 
2. Fórmula fechada para o termo geral: Sn = 7n – 5 
 
S7 = 7  7 – 5 = 44 
Recorrências: sequências 
S100000 = 7  100000 – 5 = 699995 
• Sequências – Formas de especificação 
2. Fórmula fechada para o termo geral: Sn = 7n – 5 
Recorrências: sequências 
 n  ℕ | Sn = 42325 ? 
7n – 5 = 42325 7n = 42325 + 5 
n = 42330 / 7  6047,14 … n ∉ ℕ 
42325 ∉ S 
Recorrências: sequências 
• Sequências – Formas de especificação 
1. Por enumeração: S = 2, 9, 16, 23, 30, ... 
3. Por recorrência: 
 BASE 
PASSO Sn = Sn–1 + 7 
S1 = 2 
2. Fórmula Fechada ? 
R. “Resolver” a recorrência 
• Resolvendo recorrências ⇒ fórmula fechada 
– Exemplo 4: 
S(1) = 2 
S(n) = S(n–1) + 7 
 
 
 
 
 
 
Recorrências: sequências 
• Encontrar a fórmula fechada 
 1ª Forma 
 
 
 
 
Recorrências: sequências 
S(1) = 2 
S(n) = S(n–1) + 7 
S(3) = S(2) + 7 
S(2) = S(1) + 7 
S(1) = 2 
S(n) = S(n–1) + 7 
S(n–1) = S(n–2) + 7 
S(n–2) = S(n–3) + 7 
... 
Somando todos os termos de cada lado; e 
cancelando os que estejam nos dois lados: 
∑ ∑ 
S(n) = 2 + 7(n–1) 
S(n) = 7n – 5 
• Encontrar a fórmula fechada 
 2ª Forma: expandido os termos 
 
 
 
 
Recorrências: sequências 
S(1) = 2 
S(n) = S(n–1) + 7 
S(1) = 2 
S(2) = S(1) + 7 = 
S(3) = S(2) + 7 = 
2 + 7 
2 + 7 + 7 = 
S(4) = S(3) + 7 = 2 + 2 ∙ 7 + 7 = 
2 + 2 ∙ 7 
2 + 3 ∙ 7 
S(5) = S(4) + 7 = 2 + 3 ∙ 7 + 7 = 2 + 4 ∙ 7 
S(6) = S(5) + 7 = 2 + 4 ∙ 7 + 7 = 2 + 5 ∙ 7 
S(n) = 2 + (n–1) ∙ 7 
S(n) = 7n – 5 
... 
• Encontrar a fórmula fechada 
 3ª Forma: expandindo os termos 
 
 
 
 
Recorrências: sequências 
S(n) = S(n–1) + 7 
S(n) = S(n–2) + 7 + 7 = 
S(1) = 2 
S(n) = S(n–1) + 7 
= S(n–2) + 2 ∙ 7 
S(n) = S(n–3) + 7 + 2 ∙ 7 = 
= S(n–3) + 3 ∙ 7 
S(n) = S(n–4) + 7 + 3 ∙ 7 = 
= S(n–4) + 4 ∙ 7 
⋮ 
S(n) = S(n–k) + k ∙ 7 
• Encontrar a fórmula fechada 
 3ª Forma: (cont.) 
 
 
 
 
Recorrências: sequências 
S(1) = 2 
S(n) = S(n–1) + 7 
Para n – k = 1 
S(n) = S(n–k) + 7k 
⇒ k = n –1, temos 
S(n) = S( n – (n –1) ) + 7(n –1) = 
= S(1) + 7(n –1) 
S(n) = 2 + 7(n–1) 
S(n) = 7n – 5 
• Encontrar a fórmula fechada 
– Exemplo 5: 
 T(1) = 1 
 T(n) = 2T(n–1) + 1 
 
 
 
 
 
Recorrências: sequências 
T = 1, 3, 7, 15, 31, 63, ... 
Por enumeração: 
• Encontrar a fórmula fechada 
– Exemplo 5: 
 
 
 
 
 
Recorrências: sequências 
... 
T(n) = 2 T(n–1) + 1 
T(n) = 2 ( 2T(n–2) + 1 ) + 1 
T(1) = 1 
T(n) = 2T(n–1) + 1 
= 4 T(n–2) + 1 + 2 
T(n) = 4 ( 2T(n–3) + 1 ) + 2 + 1 
= 8 T(n–3) + 4 + 2 + 1 
T(n) = 16 T(n–4) + 8 + 4 + 2 + 1 
= 16 T(n–4) + 1 + 2 + 4 + 8 
 ⋮ 
T(n) = 2k T(n–k) + 1 + 2 + 4 + ... + 2k–1 
• Encontrar a fórmula fechada 
– Exemplo 5: 
 
 
 
 
Recorrências: sequências 
Para n – k = 1 ⇒ k = n –1, temos 
T(n) = 2n –1 ⋅ T( n
 – (n –1) ) + 1 + 2 + 4 + ... + 2n–2 
= 2n –1 ⋅ T(1) + 1 + 2 + 4 + ... + 2n–2 = 
= 1 + 2 + 4 + ... + 2k–2 + 2n –1 
T(1) = 1 
T(n) = 2T(n–1) + 1 
T(n) = 2k T(n–k) + 1 + 2 + 4 + ... + 2k–1 
• Encontrar a fórmula fechada 
– Exemplo 5: 
 
 
 
 
Recorrências: sequências 
T(1) = 1 
T(n) = 2T(n–1) + 1 
T(n) = 1 + 2 + 4 + 8 + ... + 2n –1 
T(n) = 20 + 21 + 22+ 23 + ... + 2n –1 
Soma dos n termos da PG: 1 + q + q2 + q3 + ... + qn –1 (veja exercícios de indução) 
S = 
𝑞𝑛−1
𝑞−1
 Para q = 2, temos T(n) = 2n – 1 
• Encontrar a fórmula fechada 
– Exemplo 5: 
 
 
 
 
Recorrências: sequências 
T(1) = 1 
T(n) = 2T(n–1) + 1 
Provar, por indução, que 
1 + 𝑞 + 𝑞2 + 𝑞3 + ⋯+ 𝑞𝑛−1 = 
𝑞𝑛 − 1
𝑞 − 1
 
Obrigado! 
 
 
Aula 9 
• Recorrências (cont.) 
– Sequências 
– Conjuntos 
– Operações e funções (matemáticas) 
– Algoritmos ou funções (computacionais) 
 
 
• Sequências definidas por Recorrência 
– BASE 
• Definição “direta” (não recorrente) 
• Um ou mais termos, usualmente termos iniciais 
– ATENÇÃO: pode-se definir vários termos iniciais na base da recorrência 
– PASSO 
• Definição “recorrente” do “termo geral” 
• Definido em função de um ou mais termos anteriores 
– ATENÇÃO: um termo pode ser definido a partir de “vários” outros 
Recorrências: sequências 
• Exemplo 6 
– Sequência de Fibonacci (duas definições equivalentes) 
• F0 = 0 
• Fn
 = Fn–1
 + Fn–2 n > 1 
F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 
• F1 = 1 
• Fn = n 0 ≤ n ≤ 1 
• Fn
 = Fn–1
 + Fn–2 n > 1 
OU 
Recorrências: sequências 
• Exemplo 6 
– Sequência de Fibonacci (outra definição) 
• F(1) = F(2) = 1 
• F(n) = F(n-1) + F(n-2) n > 2 
F = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 
Recorrências: sequências 
• Exemplo 6 
– Sequência de Fibonacci: FÓRMULA FECHADA 
• F(1) = F(2) = 1 
• F(n) = F(n-1) + F(n-2) n > 2 
Recorrências: sequências 
 𝐹 𝑛 = 
5
5
 
1 + 5
2
 
𝑛
−
5
5
 
1 − 5
2
 
𝑛
 
1. Escreva os 8 termos iniciais de cada sequência a seguir 
(mostre os cálculos) 
Identifique quais são definidas por recorrências e quais por fórmula fechada 
a. S(1) = 1 
S(n) = S(n–1) + n2, n > 1 
b. R(n) = 2n + n2, n ≥ 1 
c. R(n) = 2n – n, n ≥ 1 
Exercícios de Recorrências: sequências 
1. Escreva os 8 termos iniciais de cada sequência a seguir 
(mostre os cálculos) 
Identifique quais são definidas por recorrências e quais por fórmula fechada 
d. T(1) = 1 
T(2) = 2 
T(n) = T(n–1) + T(n–2) + n, n ≥ 3 
e. R(n) = 2 (n+1)2 – 2n, n ≥ 1 
f. S(1) = 3 
S(n) = S(n–1) + (n–1)2, n > 1 
 
 
 
Exercícios de Recorrências: sequências 
2. Para a sequência S = 7, 13, 19, 25,  
a. Defina S por recorrência 
b. Encontre a fórmulafechada para S 
c. Utilizando a fórmula fechada, responda (justifique sua resposta) 
 
 59995  S ? 
 
Exercícios de Recorrências: sequências 
3. Escreva a recorrência – BASE E PASSO – que defina cada sequência 
a. S = 1, 3, 6, 10, 15, 21, … 
b. S = 1, 3, 8, 22, 60, 164, … 
c. S = 2, 3, 7, 13, 27, … 
d. S = 2, 3, 12, 13, 22, 23, 32, 33… 
e. S = 1, 2, 6, 24, 120, 720, … 
f. S = 1, 3, 7, 15, 31, 63, 127, … 
 
Exercícios de Recorrências: sequências 
Gabarito 
1. Apenas os 5 iniciais 
Exercícios de Recorrências: sequências 
a) S(1) = 1 
S(2) = S(1) + 22 = 1 + 4 = 5 
S(3) = S(2) + 32 = 5 + 9 = 14 
S(4) = S(3) + 42 = 14 + 16 = 30 
S(5) = S(4) + 52 = 30 + 25 = 55 
b) R(1) = 21 + 12 = 2 + 1 = 3 
R(2) = 22 + 22 = 4 + 4 = 8 
R(3) = 23 + 32 = 8 + 9 = 17 
R(4) = 24 + 42 = 16 + 16 = 32 
R(5) = 25 + 52 = 32 + 25 = 57 
c) R(1) = 21 – 1 = 2 – 1 = 1 
R(2) = 22 – 2 = 4 – 2 = 2 
R(3) = 23 – 3 = 8 – 3 = 5 
R(4) = 24 – 4 = 16 – 4 = 12 
R(5) = 25 – 5 = 32 – 5 = 27 
d) T(1) = 1 
T(2) = 2 
T(3) = T(2) + T(1) + 3 = ... = 6 
T(4) = T(3) + T(2) + 4 = ... = 12 
T(5) = T(4) + T(3) + 5 = ... = 23 
e) R(1) = ... = 6 
R(2) = ... = 14 
R(3) = ... = 24 
R(4) = ... = 34 
R(5) = ... = 40 
f) S(1) = 3 
S(2) = ... = 4 
S(3) = ... = 8 
S(4) = ... = 17 
S(5) = ... = 33 
Gabarito 
2. 
Exercícios de Recorrências: sequências 
a) S(1) = 7 
S(n) = S(n–1) + 6, n  1 
b) Expandir os termos 
 
S(n) = 7 + 6 (n–1)  S(n) = 6n + 1 
c) S(n) = 59995 = 6n +1 
... 
n = 59999 / 6 = 9999  S(9999) = 59995  59995  S 
Gabarito 
3. 
Exercícios de Recorrências: sequências 
a) S(1) = 1 
S(n) = S(n–1) + n n ≥ 2 
b) S(1) = 1 
S(2) = 3 
S(n) = 2 [ S(n–1) + S(n–2) ] n > 2 
 
c) S(1) = 2 
S(2) = 3 
S(n) = S(n–1) + 2 S(n–2) n > 2 
d) S(1) = 2 
S(2) = 3 
S(n) = S(n–2) + 10 n > 2 
Gabarito 
3. 
Exercícios de Recorrências: sequências 
e) S(1) = 1 
S(n) = n ∙ S(n–1), n > 1 
f) S(1) = 1 
S(n) = 2 ∙ S(n–1) + 1, n > 1 
Exercícios: slides prof. Ricardo 
Encontre uma forma recorrente para as sequências abaixo. 
Depois encontre suas fórmulas fechadas. 
 
4. S = x, x + a, x + 2a, x + 3a, x + 4a, ... 
5. S = 7, 9, 11, 13, 15, 17, ... 
Gabarito – slides do prof. Ricardo 
Exercícios de Recorrências: sequências 
Exercícios: Deduzir as fórmulas fechadas. 
6. 
𝑆 1 = 3 
𝑆 𝑛 = 2 ∙ 𝑆 𝑛 − 1 , 𝑛 > 1
 
7. 
𝑆 1 = 3 
𝑆 𝑛 = 𝑆 𝑛 − 1 + 5, 𝑛 > 1
 
8. S = 1, 3, 7, 15, 31, 63, 127, … 
 
Exercícios de Recorrências: sequências 
Exercícios: Deduzir as fórmulas fechadas. 
6. 
𝑆 1 = 3 
 𝑆 𝑛 = 2 ∙ 𝑆 𝑛 − 1 , 𝑛 > 1
 
7. 
𝑆 1 = 3 
 𝑆 𝑛 = 𝑆 𝑛 − 1 + 5, 𝑛 > 1
 
8. S = 1, 3, 7, 15, 31, 63, 127, … 
Gabarito 
6. S(n) = 3 ∙ 2n-1 7. S(n) = 5n – 2 8. S(n) = 2n – 1 
Exercícios de Recorrências: sequências 
Exercícios: Deduzir as fórmulas fechadas. 
9. Especifique a recorrência para a sequência S. Depois calcule S(6). 
 
 S = 1, 5, 12, 34, 92, ... 
Gabarito 
9. S(6) = 252 
Exercícios de Recorrências: sequências 
Obrigado! 
 
 
Aula 10 
• Recorrências (cont.) 
– Sequências 
– Operações e funções (matemáticas) 
• Recursividade 
– Algoritmos ou funções (computacionais) 
 
 
Exercícios: Deduzir as fórmulas fechadas. 
6. 
𝑆 1 = 3 
𝑆 𝑛 = 2 ∙ 𝑆 𝑛 − 1 , 𝑛 > 1
 
7. 
𝑆 1 = 3 
𝑆 𝑛 = 𝑆 𝑛 − 1 + 5, 𝑛 > 1
 
8. S = 1, 3, 7, 15, 31, 63, 127, … 
Exercícios sobre recorrências: sequências 
• Resolvendo recorrências 
 1ª Forma 
 
 
 
 
Exercícios sobre recorrências: sequências 
6. 
𝑆 1 = 3 
 𝑆 𝑛 = 2 ∙ 𝑆 𝑛 − 1 , 𝑛 > 1 
 
S(3) = S(2) · 2 
S(2) = S(1) · 2 
S(1) = 3 
S(n) = S(n–1) · 2 
S(n–1) = S(n–2) · 2 
S(n–2) = S(n–3) · 2 
... 
Multiplicando todos os termos de cada lado; 
cancelando os que estejam nos dois lados: 
∏ ∏ S(n) = 3 · 2
n-1 
• Resolvendo recorrências 
 2ª Forma: expandido os termos 
 
 
 
 
Exercícios sobre recorrências: sequências 
S(1) = 3 
S(2) = S(1) · 2 = 
S(3) = S(2) · 2 = 
3 · 2 
3 · 2 · 2 = 
S(4) = S(3) · 2 = 3 · 22 · 2 = 
3 ∙ 22 
3 ∙ 23 
S(5) = S(4) · 2 = 3 · 23 · 2 = 3 ∙ 24 
S(6) = S(5) · 2 = 3 · 24 · 2 = 3 ∙ 25 
S(n) = 3 ∙ 2n-1 
6. 
𝑆 1 = 3 
 𝑆 𝑛 = 2 ∙ 𝑆 𝑛 − 1 , 𝑛 > 1 
 
Exercícios: Deduzir as fórmulas fechadas. 
6. 
𝑆 1 = 3 
𝑆 𝑛 = 2 ∙ 𝑆 𝑛 − 1 , 𝑛 > 1
 Resolva utilizando a expansão da 3ª forma 
7. 
𝑆 1 = 3 
𝑆 𝑛 = 𝑆 𝑛 − 1 + 5, 𝑛 > 1
 
8. S = 1, 3, 7, 15, 31, 63, 127, … Veja Exemplo 5. 
Gabarito 
6. S(n) = 3 ∙ 2n-1 7. S(n) = 5n – 2 8. S(n) = 2n – 1 
Exercícios sobre recorrências: sequências 
• Recursividade 
– Fundamental em Matemática e Ciência da Computação 
• Função recorrente é definida em termos dela mesma 
• Programa recursivo é um programa que chama a si mesmo 
– Note: “recorrência” – Matemática, “recursividade” – Computação. 
– Exemplos: 
• Números naturais, Função fatorial, Árvore 
– Conceito poderoso: 
• Define conjuntos infinitos com comandos finitos! 
Recorrências: Algoritmos/funções recursivos 
prof. Ricardo Mesquita 
• Definição 
– A função “invoca” a si mesma 
• A função chama ou ativa outra “instância” de si mesma 
– Recorrência direta 
• A função A chama a própria função A 
– Recorrência indireta: 
• A função A chama uma função B que, por sua vez, chama a função A 
 
Recorrências: Algoritmos/funções recursivos 
prof. Ricardo Mesquita 
• Nenhum programa ou função pode ser exclusivamente 
definido por si 
– O programa entraria em um loop infinito 
– A função teria uma definição circular, infinita 
• Condição de parada 
– Permite determinar que o procedimento pare sua execução em 
algum momento 
• Exemplo: F(x) > 0, onde x é decrescente 
Recorrências: Algoritmos/funções recursivos 
prof. Ricardo Mesquita 
09/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
10/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
11/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
12/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
13/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
14/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
15/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
16/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
17/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
18/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
19/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
20/31 
Exemplo: Função Fatorial – prof. Ricardo Mesquita 
• Exemplo 
Função F(m: real, n: inteiro) // m ≠ 0 
 Se n = 0 então 
 Retorne 1 
 Senão 
 Retorne m * F(m, n-1) 
 FimSe 
FimFunção 
Recursividade 
F(2,3) = 2 * F(2,2) = 
F(2,2) = 
F(2,0) = 
F(2,1) = 
2 * F(2,1) = 
2 * F(2,0) = 
1 
2 * 1 = 2 
2 * 2 = 22 
2 * 22 = 23 
F(2,3) = 8 F(m,n) = mn 
• Exemplo 
Função F(m: real, n: inteiro) 
 Se n = 0 então 
 Retorne 0 
 Senão 
 Retorne m + F(m, n-1) 
 FimSe 
FimFunção 
Recursividade 
F(2,3) = 2 + F(2,2) = 
F(2,2) = 
F(2,0) = 
F(2,1) = 
2 + F(2,1) = 
2 + F(2,0) = 
0 
2 + 0 = 2 
2 + 2 = 2 · 2 
2 + 2 · 2 = 2 · 3 
F(2,3) = 6 F(m,n) = m · n 
• Exercício 
Recursividade 
f (12) = 12 · f (11) = 
f (11) = 
f (10) = 
11 · f (10) = 
10 
11 · 10 
12 · 11 · 10 
Seja a função 𝑓(𝑥) definida por: 
 𝑓 𝑥 = 
𝑥 
 𝑥 ⋅ 𝑓(𝑥 − 1) 
se 0 ≤ 𝑥 ≤ 10
caso contrário 
 
 Assinale qual o valor de 𝑓 12 ? 
a) 12! 
b) 12! /8! 
c) 12! / 9! 
d) 12! / 10! 
e) 12! / 11! 
c) 12! / 9! 
• Exemplo: sequência de Fibonacci 
int Fib(int n) // Versão Recursiva n >= 1 
{ 
 if (n <= 0) return 0; // exception? 
 
 if ((n == 1) || (n == 2)) 
 return 1; 
 else 
 return Fib(n-1) + Fib(n-1); 
} 
Recursividade 
• Exemplo: valor máximo em um vetor com n elementos 
int MaxVet (int vet[], int n) // Versão ITERATIVA 
{ 
 int maximo = INT_MIN; // #include <limits.h> 
 
 
 for (i = 0; i < n; i++) 
 if (vet[i] > maximo) 
 maximo = vet[i]; 
 return maximo; 
} 
Recursividade 
• Exemplo: valor máximo em um vetor com n elementos 
int MaxVet2 (int vet[], int n) // Versão 2.0 - RECURSIVA 
{ 
 int maximo; 
 
 
 if (n == 1) 
 return vet[0]; 
 
 
 maximo = MaxVet2 (vet, n-1); 
 
 if (maximo > vet[n-1]) 
 return maximo; 
 else 
 return vet[n-1]; 
} 
Recursividade 
• Exemplo: valor máximo em um vetor com n elementos 
int MaxVet3 (int vet[], int ini, int fim) // Versão 3.0 - RECURSIVA 
{ 
 int max1, max2, meio; 
 
 if (ini == fim) 
 return vet[ini]; 
 
 meio = (ini + fim) / 2; 
 
 max1 = MaxVet3 (vet, ini, meio); 
 max2 = MaxVet3 (vet, meio+1, fim ); 
 
 if (max1 > max2) 
 return max1; 
 else 
 return max2; 
} 
Recursividade 
Obrigado! 
 
 
Obrigado!