Princípios de Contagem em Matemática

Prévia do material em texto

Mestrado Profissional
em Matemática em Rede Nacional
Iniciação à Matemática
Autores:
Krerley Oliveira Adán J. Corcho
Unidade III:
Capítulos V e VI
160
5
Contagem
Toda vez que puder, 
onte. Fran
is Galton
Neste capítulo discutiremos problemas envolvendo a contagem de
elementos de um conjunto �nito dado. Por exemplo, responderemos
perguntas do tipo: de quantos modos podemos distribuir 32 seleções
nacionais de futebol em seis grupos de quatro times cada?
Para solucionar questões como esta, utilizaremos como ferramentas
básicas os princípios aditivo e multiplicativo da contagem. Veremos
também que o uso simultâneo destes princípios será muito útil para
resolver problemas com certos níveis de complexidade. Além disso,
serão abordados os conceitos de permutações, arranjos e combinações,
sendo estes de muita importância por serem os alicerces de um ramo
da matemática denominado combinatória.
Antes de prosseguirmos daremos algumas de�nições e notações que
serão úteis ao longo de todo o capítulo. Dado um conjunto A deno-
tamos por |A| a quantidade de elementos que este possui. O produto
cartesiano de n conjuntos A1, A2, . . . , An−1 e An é o conjunto de�nido
161
162 5 Contagem
por
A1 × A2 × · · · × An :=
{
(a1, a2, . . . , an); ai ∈ Ai, i = 1, 2, . . . , n
}
,
onde cada elemento (a1, a2, . . . , an) é chamado de n-upla ordenada.
Denotaremos o conjunto vazio com o símbolo ∅. O leitor que deseja
rever os conceitos básicos da teoria de conjuntos, pode achá-los muito
bem expostos em [3].
5.1 Princípio Aditivo da Contagem
O princípio aditivo da contagem garante que dados dois conjuntos
�nitos que não têm elemento em comum, o número de elementos da
união é exatamente a soma do número de elementos de cada um, ou
seja, se A1 e A2 são disjuntos (isto é, A1 ∩ A2 = ∅), então
|A1 ∪ A2| = |A1|+ |A2|.
Apesar de sua simplicidade, muitos problemas podem ser resolvi-
dos utilizando esse simples princípio. A seguir enunciamos uma ex-
tensão deste princípio para um número �nito qualquer de conjuntos.
Princípio Aditivo da contagem: Dados os conjuntos �nitos A1,
A2, . . . , An dois a dois disjuntos (isto é, Ai ∩ Aj = ∅ ,∀ i 6= j),
temos que
|A1 ∪ A2 ∪ · · · ∪ An| = |A1|+ |A2|+ · · ·+ |An|.
Exemplo 5.1. Em Maceió entraram em cartaz 4 �lmes distintos e
2 peças de teatro. Se Pedro Vítor só tem dinheiro para assistir a um
�lme ou a uma peça de teatro, diga quantos são os possíveis programas
de Pedro Vítor.
5.1 Princípio Aditivo da Contagem 163
Solução. Denotemos por f1, f2, f3 e f4 os quatro �lmes que estão em
cartaz e por t1 e t2 as duas peças de teatro. Agora, representemos pelo
par (i, j), com 0 ≤ i ≤ 4 e 0 ≤ j ≤ 2, o programa que consiste em as-
sistir ao �lme fi e à peça tj (caso i = 0 ou j = 0 isso signi�ca que não
será assistido a nenhum �lme ou a nenhuma peça, respectivamente).
Pelas limitações econômicas do Pedro Vítor temos que ele só pode
escolher um programa dentro dos seguintes conjuntos disjuntos:
A1 =
{
(1, 0), (2, 0), (3, 0), (4, 0)
}
e A2 =
{
(0, 1), (0, 2)
}
.
Logo, no total são |A1 ∪ A2| = |A1| + |A2| = 6 programas distintos,
entre os quais Pedro Vítor terá que escolher um.
Exemplo 5.2. Numa reunião havia um certo número de pessoas e
todos os presentes apertaram as mãos entre si. Sabendo-se que ao todo
foram feitos 66 cumprimentos, calcule o número de pessoas presentes
à reunião.
Solução. Vamos enumerar as pessoas com os números do conjunto
P = {1, 2, . . . , n}. A cada aperto de mão associaremos um par (i, j),
signi�cando que a pessoa i apertou a mão da pessoa j. Assim, os
apertos de mão envolvendo a pessoa 1 foram:
A1 = {(1, 2), (1, 3), . . . , (1, n)}.
Do mesmo modo, de�nimos os apertos de mão envolvendo a pessoa 2
que não envolvem a pessoa 1, como:
A2 = {(2, 3), (2, 4), . . . , (2, n)}.
Note que o aperto (2, 1) é o mesmo que o aperto (1, 2), já que se 1
aperta a mão de 2, então 2 aperta a mão de 1. Analogamente,
Ai = {(i, i+ 1), (i, i+ 2), . . . , (i, n)}, para 1 ≤ i ≤ n.
164 5 Contagem
Note que Ai ∩ Aj = ∅ para i 6= j. Observe também que todos os
apertos aparecem em um dos conjuntos Ai. Assim, A1 ∪ · · · ∪ An
contém todos os apertos de mão. Logo, pelo princípio aditivo:
|A1 ∪ A2 ∪ · · · ∪ An| = |A1|+ |A2|+ . . . |An|
= (n− 1) + (n− 2) + · · ·+ 2 + 1
=
(n− 1)n
2
= 66.
Resolvendo em n, temos que n = 12.
Vimos que o princípio aditivo nos fornece o número de elementos
de qualquer união de conjuntos dois a dois disjuntos. Discutiremos
agora uma extensão do princípio para qualquer união de conjuntos,
não necessariamente dois a dois disjuntos.
Proposição 5.3. Sejam A1 e A2 dois conjuntos �nitos quaisquer.
Então,
|A1 ∪ A2| = |A1|+ |A2| − |A1 ∩ A2|.
Demonstração. Observe que
A1 ∪ A2 = (A1 − A2) ∪ A2
onde a união é dois a dois disjunta. Pelo princípio aditivo, temos que
|A1 ∪ A2| = |A1 − A2|+ |A2|. (5.1)
Analogamente, aplicando novamente este princípio, temos que
|A1| = |A1 − A2|+ |A1 ∩ A2|; (5.2)
A proposição segue imediatamente combinando as igualdades (5.1) e
(5.2).
5.1 Princípio Aditivo da Contagem 165
Para chegar a uma expressão análoga à do princípio aditivo, vamos
fazer mais um caso, considerando agora três conjuntos.
Corolário 5.4. Sejam A1, A2 e A3 três conjuntos �nitos quaisquer.
Então,
|A1 ∪ A2 ∪ A3| =|A1|+ |A2|+ |A3|
−
(
|A1 ∩ A2|+ |A1 ∩ A3|+ |A2 ∩ A3|
)
+ |A1 ∩ A2 ∩ A3|.
Demonstração. Pela Proposição 5.3 temos que,
|A1 ∪ (A2 ∪ A3)| = |A1|+ |A2 ∪ A3| − |A1 ∩ (A2 ∪ A3)|,
de onde,
|A1 ∪ A2 ∪ A3| = |A1|+ |A2 ∪ A3| − |(A1 ∩ A2) ∪ (A1 ∩ A3)|.
Novamente, pela Proposição 5.3 temos que,
|A1∪A2∪A3| = |A1|+ |A2|+ |A3|− |A2∩A3|− |(A1∩A2)∪ (A1∩A3)|.
Aplicando mais uma vez a Proposição 5.3 temos que,
|(A1∩A2)∪ (A1∩A3)| = |A1∩A2|+ |A1∩A3|− |(A1∩A2)∩ (A1∩A3).
Combinando as duas últimas igualdades obtemos
|A1 ∪ A2 ∪ A3| =|A1|+ |A2|+ |A3|
−
(
|A1 ∩ A2|+ |A1 ∩ A3|+ |A2 ∩ A3|
)
+ |A1 ∩ A2 ∩ A3| ,
como desejávamos.
166 5 Contagem
Para facilitar nossa escrita, vamos denotar por A1A2 . . . Ak o con-
junto A1 ∩A2 ∩ · · · ∩Ak. Assim, outra forma de enunciar o Corolário
5.4 é a seguinte:
∣∣∣∣∣
3⋃
i=1
Ai
∣∣∣∣∣ =
3∑
i=1
|Ai| −
∑
1≤i1<i2≤3
|Ai1Ai2 |+
∑
1≤i1<i2<i3≤3
|Ai1Ai2Ai3|.
De forma geral, dados os conjuntos �nitos A1, A2, . . . , An, as ex-
pressões anteriores nos levam a de�nir os números:
S1 =
n∑
i=1
|Ai|
S2 =
∑
1≤i1<i2≤n
|Ai1Ai2|,
...
Sk =
∑
1≤i1<i2<···<ik≤n
|Ai1Ai2 . . . Aik |,
...
Sn = |A1A2 . . . An|.
Assim, a versão mais geral do princípio aditivo, também conhecida
como princípio de inclusão e exclusão, é:
Princípio Aditivo - Versão Geral: Sejam A1, A2 . . . , An
conjuntos �nitos quaisquer. Então,
∣∣∣∣∣
n⋃
i=1
Ai
∣∣∣∣∣ = S1 − S2 + S3 − S4 + · · ·+ (−1)
n−1Sn.
Não iremos provar essa versão, mas o leitor pode (e deve!) mostrá-la
como exercício, repetindo os argumentos anteriores.
5.1 Princípio Aditivo da Contagem 167
Exemplo 5.5. No Colégio Fantástico foram entrevistados 78 estudan-
tes. Destes, 32 estavam fazendo um curso de francês; 40 um curso de
física; 30 um curso de matemática; 23 um curso de história; 19 francês
e física; 13 francês e matemática; 15 física e matemática; 2 francês e
história; 15 física e história; 14 matemática e história; 8 francês, fí-
sica e matemática; 8 francês, física e história; 2 francês, matemática
e história; 6 física, matemática e história e 2 estavam fazendo todos
os quatro cursos. Quantos estudantes estavam fazendo pelo menos 1
curso nas 4 áreas mencionadas?
Solução. Denotemos por A1, A2, A3, e A4 os conjuntos dos estudan-
tes que fazem francês, física, matemática e história, respectivamente.
Observemos que as igualdades
|A1| = 32,
|A2| = 40,
|A3| = 30,
|A4| = 23,
nos dão que S1 =
4∑
i=1
|Ai| = 125; as igualdades
|A1A2| = 19,
|A1A3| = 13,
|A1A4| = 2,
|A2A3| = 15,
|A2A4| = 15,
|A3A4| = 14,
168 5 Contagem
nos dão que S2 =
∑
1≤i1<i2≤4
|Ai1Ai2 | = 78; as igualdades
|A1A2A3| = 8,
|A1A2A4| = 8,
|A1A3A4| = 2,
|A2A3A4| = 6,
nos dão que S3 =
∑
1≤i1<i2<i3≤4
|Ai1Ai2Ai3| = 24; assim como que S4 =
|A1A2A3A4| =2.
Segue-se então, do princípio aditivo, que
∣∣∣∣∣
4⋃
i=1
Ai
∣∣∣∣∣ = 125−78 + 24−
2 = 69.
De�nição 5.6. De�nimos o complementar do conjunto A em relação
ao conjunto U como sendo um subconjunto de U dado por
Ac =
{
x ∈ U ; x /∈ A
}
.
U
A
Figura 5.1: A área branca corresponde a Ac e o conjunto U é representado
por todo o retângulo
5.1 Princípio Aditivo da Contagem 169
Neste caso é fácil veri�car que os conjuntos A e Ac são disjuntos e
que U = A ∪ Ac. Segue-se do princípio aditivo que |U| = |A| + |Ac|;
portanto,
|Ac| = |U| − |A|.
Analogamente, dados dois conjuntos A1 ⊂ U e A2 ⊂ U , temos que
A1∪A2 e (A1∪A2)c são disjuntos e, aliás, U = (A1∪A2)∪(A1∪A2)c.
Novamente, pelo princípio aditivo, vale que
|U| = |A1 ∪ A2|+ |(A1 ∪ A2)c|;
e consequentemente temos que
|(A1 ∪ A2)c| = |U| − (|A1|+ |A2|) + |A1A2|.
Similarmente, dados três conjuntos A1 ⊂ U , A2 ⊂ U e A3 ⊂ U
podemos demonstrar que
|(A1 ∪ A2 ∪ A3)c| = |U| − (|A1|+ |A2|+ |A3|)
+ (|A1A2|+ |A1A3|+ |A2A3|)
− |A1A2A3|.
Então, usando a notação S0 = |U|, temos a seguinte proposição:
Proposição 5.7. Para toda família de subconjuntos Ai ⊂ U , i =
1, 2, . . . , n, vale a relação:
∣∣∣∣∣
(
n⋃
i=1
Ai
)c∣∣∣∣∣ = S0 −
(
S1 − S2 + S3 − S4 − · · ·+ (−1)n−1Sn
)
= S0 − S1 + S2 − S3 + S4 − · · ·+ (−1)nSn,
ou resumidamente,
∣∣∣∣∣
(
n⋃
i=1
Ai
)c∣∣∣∣∣ = |A
c
1A
c
2 · · ·Acn| =
n∑
j=0
(−1)jSj.
170 5 Contagem
Observação 5.8. Observemos que na última relação da proposição
usamos a conhecida Lei de DeMorgan: o complementar da união de
uma família �nita de conjuntos, em relação a um conjunto U , é a
intersecção dos complementares de cada um deles.
5.2 Princípio Multiplicativo de Contagem
Começamos esta seção discutindo um problema relacionado com o
apaixonante jogo de xadrez. Ele consiste no seguinte: queremos saber
de quantas maneiras diferentes podemos colocar duas torres num tabu-
leiro de xadrez de forma tal que nenhuma ataque a outra. Uma situa-
ção como a que procuramos é mostrada na Figura 5.2, pois lembramos
que torres só se movimentam na direção horizontal ou na direção verti-
cal do tabuleiro. Antes de prosseguir deixamos claro o seguinte: se na
Figura 5.2 trocamos a posição da torre a com a torre b consideraremos
isto como uma situação diferente.
a
b
Figura 5.2: Torres que não se atacam
Notemos o seguinte: uma vez que coloquemos uma das torres numa
5.2 Princípio Multiplicativo de Contagem 171
casa do tabuleiro não podemos colocar a segunda torre na mesma
linha ou coluna em que esta se encontra, pois ela seria ameaçada.
Como cada linha e cada coluna contém 8 casas do tabuleiro, sendo
uma delas comum a ambas, então temos 15 posições proibidas para
colocar a segunda torre, ou seja, ela só pode ser colocada em 64−15 =
49 posições diferentes. Resumindo, por cada uma das 64 possíveis
posições para a torre a temos 49 possibilidades diferentes para colocar
a torre b, totalizando 64·49 = 3.136 formas diferentes de colocar ambas
as torres no tabuleiro sem que elas se ataquem.
O exemplo acima traz a essência do que é chamado princípio mul-
tiplicativo da contagem: se um evento A1 pode ocorrer de m maneiras
distintas e, se para cada uma dessas m maneiras possíveis de A1 ocor-
rer, um outro evento A2 pode ocorrer de n maneiras distintas, então o
número de maneiras de ocorrerem sucessivamente os eventos A1 e A2
é m · n.
Na linguagem matemática: relembramos que dados dois conjuntos
A1 e A2, podemos construir um par ordenado (a1, a2) tomando um
elemento a1 ∈ A1, denominado o primeiro elemento do par, e um
elemento a2 ∈ A2, denominado o segundo elemento do par. O conjunto
A1×A2 é constituido por todos os pares ordenados construídos dessa
forma. Assim sendo, a versão mais simples do princípio multiplicativo
nos garante que
|A1 × A2| = |A1| |A2|.
Uma extensão deste princípio para um número �nito qualquer de
conjuntos é a seguinte:
princípio multiplicativo da contagem: Dados os conjuntos
172 5 Contagem
�nitos A1, A2, . . . , An temos que
|A1 × A2 × · · · × An| = |A1| · |A2| · · · |An|.
Note que neste princípio, não é necessária nenhuma hipótese adi-
cional sobre os conjuntos Ai. Vamos agora dar alguns exemplos de
como aplicar esse princípio.
Exemplo 5.9. Em Maceió entraram em cartaz 4 �lmes distintos e
2 peças de teatro. Se agora o Pedro Vítor tem dinheiro para assistir
exatamente a um �lme e a uma peça de teatro, diga quantos são os
possíveis programas que Pedro Vítor pode fazer.
Solução. Denotemos por f1, f2, f3 e f4 os quatro �lmes que estão em
cartaz e por t1 e t2 as duas peças de teatro. De�namos os conjuntos
A1 = {f1, f2, f3, f4} e A2 = {t1, t2}.
Neste caso, as condições econômicas do Pedro Vítor permitem que
ele escolha um elemento do conjunto A1 e outro elemento do conjunto
A2. Este tipo de escolha representa-se pelo conjunto
A1 × A2 =
{
(fi, tj); 1 ≤ i ≤ 4 e 1 ≤ j ≤ 2
}
,
onde cada par (fi, tj) representa o programa que consiste em assistir
ao �lme fi e à peça tj. Logo, no total são |A1 × A2| = |A1| · |A2| = 8
programas distintos.
Exemplo 5.10. Se numa loja de doces existem 9 tipos distintos de
balas e 5 tipos distintos de chiclete, diga quantas escolhas podemos
fazer para comprar somente uma bala e um chiclete.
5.2 Princípio Multiplicativo de Contagem 173
Solução. Denotemos por b1, b2, b3, b4, b5, b6, b7, b8 e b9 os nove tipos
distintos de balas e por c1, c2, c3, c4 e c5 os cinco tipos distintos de
chicletes. De�namos os conjuntos
B = {b1, b2, b3, b4, b5, b6, b7, b8, b9} e C = {c1, c2, c3, c4, c5}.
Como precisamos comprar simultaneamente um elemento do conjunto
B e um elemento do conjunto C, então o conjunto B × C me dá o
conjunto de todas as escolhas possíveis. Logo, o número de escolhas
possíveis para comprar simultaneamente um tipo de bala e um tipo
de chiclete é |B × C| = 9 · 5 = 45.
Exemplo 5.11. De quantas maneiras 2 pessoas podem estacionar seus
carros numa garagem com 10 vagas?
Solução. Observando que a primeira pessoa pode estacionar seu carro
de 10 formas distintas e que a segunda pessoa pode estacionar seu
carro de 9 formas distintas, temos pelo princípio multiplicativo que
existem 9 · 10 = 90 formas possíveis nas quais duas pessoas podem
estacionar seus carros numa garagem com 10 vagas.
Exemplo 5.12. Dado o número 720, diga
(a) quantos divisores inteiros e positivos ele possui;
(b) entre seus divisores inteiros e positivos, quantos são pares;
(c) entre seus divisores inteiros e positivos, quantos são ímpares;
(d) dos divisores acima, quantos são quadrados perfeitos.
174 5 Contagem
Solução. Pelo teorema fundamental da aritmética, todo número in-
teiro positivo é primo ou produto de primos. Observe que a decom-
posição de 720 em fatores primos vem dada por:
720 = 24 · 32 · 51. (5.3)
Agora de�namos os seguintes conjuntos:
A ={todos os divisores de 720 que são da forma 2k, onde k ∈ Z+},
B ={todos os divisores de 720 que são da forma 3m, onde m ∈ Z+},
C ={todos os divisores de 720 que são da forma 5n, onde n ∈ Z+}.
Observemos que 0 ≤ k ≤ 4, pois se k > 4 então pelo menos a potência
25 deveria estar presente em (5.3); como isto não acontece segue-se
que 0 ≤ k ≤ 4, de modo que
A =
{
20, 21, 22, 23, 24
}
,
seguindo o mesmo raciocínio, podemos demonstrar que 0 ≤ m ≤ 2 e
que 0 ≤ n ≤ 1. Assim,
B =
{
30, 31, 32
}
e C =
{
50, 51
}
.
(a) O conjunto de todos os possíveis divisores de 720 pode ser identi-
�cado com o conjunto A×B×C. De onde o número de divisores
inteiros e positivos de 720 é |A×B×C|. Porém, o princípio mul-
tiplicativo nos garante que |A×B×C| = |A| · |B| · |C|. Portanto,
o número de divisores inteiros e positivos de 720 é 5×3×2 = 30,
pois |A| = 5, |B| = 3 e |C| = 2.
(b) Para obter o conjunto de todos os divisores pares de 720 deve-
mos remover o elemento 20 do conjunto A. Assim, o conjunto de
5.2 Princípio Multiplicativo de Contagem 175
todos os divisores pares e positivos de 720 vem dado pelo con-
junto A− {20} ×B ×C. O princípio multiplicativo nos garante
que
∣∣(A − {20}
)
× B × C
∣∣ =
∣∣A − {20}
∣∣ · |B|· |C|. Portanto, o
número de divisores pares e positivos de 720 é 4 × 3 × 2 = 24,
pois
∣∣A− {20}
∣∣ = 4, |B| = 3 e |C| = 2.
(c) Para obter o conjunto de todos os divisores ímpares de 720 deve-
mos remover os elementos 21, 22, 23 e 24 do conjunto A. Assim,
o conjunto de todos os divisores ímpares e positivos de 720 vem
dado pelo conjunto
(
A− {21, 22, 23, 24}
)
×B × C.
O princípio multiplicativo nos garante que
∣∣(A−{21, 22, 23, 24}
)
×B ×C
∣∣ =
∣∣A−{21, 22, 23, 24}
∣∣ · |B| · |C|.
Portanto, o número de divisores ímpares e positivos de 720 é
1× 3× 2 = 6; pois
∣∣A− {21, 22, 23, 24}
∣∣ = 1, |B| = 3 e |C| = 2.
(d) Para obter o conjunto de todos os divisores de 720 que são qua-
drados perfeitos devemos �car com as potências pares nos con-
juntos A, B e C, respectivamente. Portanto, devemos remover
os elementos 21, 23 do conjunto A. Também devemos remover o
elemento 31 do conjunto B. Finalmente do conjunto C devemos
remover o elemento 51. Logo, o conjunto de todos os divisores
quadrados perfeitos e positivos de 720 vem dado pelo conjunto
D :=
(
A− {21, 23}
)
×
(
B − {31}
)
×
(
C − {51}
)
.
O princípio multiplicativo nos garante que
∣∣D
∣∣ =
∣∣A− {21, 23}
∣∣ ·
∣∣B − {31}
∣∣ ·
∣∣C − {51}
∣∣.
176 5 Contagem
Portanto, o número de divisores quadrados perfeitos e positivos
de 720 é 3 · 2 · 1 = 6; pois
∣∣A − {21, 23}
∣∣ = 3,
∣∣B − {31}
∣∣ = 2
e
∣∣C − {31}
∣∣ = 1. Observe que {1, 4, 9, 16, 36, 144} é o conjunto
dos divisores de 720 que são quadrados perfeitos.
Exemplo 5.13. Se um número natural n se fatora como
n = pk11 · pk22 · · · pkrr , (5.4)
onde os pi são números primos distintos e cada ki ∈ Z+, então o
número de divisores positivos de n, denotado por d(n) é
d(n) = (k1 + 1)(k2 + 1) . . . (kr + 1).
Solução. De�na o conjunto
A1 ={todos os divisores de n que são da forma pm11 , onde m ∈ Z+},
e em geral, de�na
Ai ={ todos os divisores de n que são da forma pmii , onde t ∈ Z+}.
Observemos que mi ≤ pi, pois se mi > pi, então pelo menos a potência
pki+1i deveria estar presente em (5.4);como isto não acontece segue-se
que mi ≤ pi, de modo que
Ai =
{
p0i , p
1
i , p
2
i , . . . , p
ki
i
}
, para i = 1, 2, 3, . . . , ki.
É imediato ver que
∣∣Ai
∣∣ = ki + 1.
5.2 Princípio Multiplicativo de Contagem 177
O conjunto de todos os possíveis divisores de n vem dado pelo
conjunto A1 × A2 × · · · × Ar, de onde se conclui que o número de
divisores inteiros e positivos de n é
d(n) = |A1 × A2 × · · · × Ar| = |A1| · |A2| · · · |Ar|,
onde na última igualdade usamos o princípio multiplicativo. Portanto,
o número de divisores inteiros e positivos de n é
d(n) = (k1 + 1)(k2 + 1) · · · (kr + 1).
Exemplo 5.14. De quantas maneiras podemos escolher dois inteiros
de 1 a 20 de forma que a soma seja ímpar?
Solução. Observemos que
• a soma de dois números inteiros pares é um número par. Com
efeito, para quaisquer a, b ∈ Z temos que 2a+ 2b = 2(a+ b);
• a soma de dois números inteiros ímpares é um número par. Com
efeito, para quaisquer a, b ∈ Z temos que (2a + 1) + (2b + 1) =
2(a+ b+ 1);
• a soma de um número inteiro par com qualquer outro inteiro
ímpar sempre é um inteiro ímpar. Com efeito, para quaisquer
a, b ∈ Z temos que 2a+ (2b+ 1) = 2(a+ b) + 1.
Isto nos sugere de�nir os conjuntos
P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20},
I = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19},
onde P × I são todas as formas possíveis de somar um número inteiro
par com outro ímpar. O princípio multiplicativo nos garante que nossa
resposta é |P × I| = |P | · |I| = 100, pois |P | = |I| = 10.
178 5 Contagem
5.3 Uso Simultâneo dos Princípios Aditivo
e Multiplicativo
Aproveitamos esta seção para apresentar problemas um pouco mais
difíceis que os tratados nas seções anteriores. Nestes problemas, pre-
cisaremos empregar simultaneamente o Princípio Aditivo e o princípio
multiplicativo. Vamos ao primeiro deles:
Exemplo 5.15. Sabemos que no início da premiação da 1a fase da
Olimpíada Alagoana de Matemática existem 10 livros diferentes de
Álgebra, 7 livros diferentes de combinatória e 5 livros diferentes de
geometria para homenagear os vencedores. Danielle é a primeira a
pegar o prêmio que consiste em 2 livros, com a condição de que estes
não podem ser da mesma matéria. Diga quantas escolhas Danielle
pode fazer para pegar seu prêmio.
Solução. Denotemos por
A = {a1, . . . , a10}, C = {c1, . . . , c7} e G = {g1, . . . , g5},
os conjuntos de livros de álgebra, combinatória e geometria, respecti-
vamente. Observemos que |A| = 10, |C| = 7 e |G| = 5 e Danielle tem
as seguintes possibilidades de escolha:
• escolher um livro de A e um livro de C. Neste caso, Danielle tem
|A × C| = |A| · |C| = 70 escolhas possíveis (devido ao princípio
multiplicativo).
• escolher um livro de A e um livro de G. Neste caso, Danielle tem
|A × G| = |A| · |G| = 50 escolhas possíveis (devido ao princípio
multiplicativo) ou
5.3 Uso Simultâneo dos Princípios Aditivo e Multiplicativo 179
• escolher um livro de C e um livro de G. Neste caso, Danielle tem
|C × G| = |C| · |G| = 35 escolhas possíveis (devido ao princípio
multiplicativo).
Agora o Princípio Aditivo nos garante que o número total de escolhas
que Danielle pode fazer é 70 + 50 + 35 = 155.
Exemplo 5.16. Há 18 moças e 12 rapazes, onde 5 deles são irmãos
(3 moças e 2 rapazes) e os restantes não possuem parentesco. Diga
quantos casamentos são possíveis naquela turma (sabendo que irmãos
não se casam).
Solução. Observemos que 15, entre as 18 moças, não têm parentesco
nenhum com os 12 rapazes, logo, pelo princípio multiplicativo temos
que é possível efetuar 15 · 12 = 180 casamentos diferentes entre eles.
Por outro lado, as 3 moças restantes podem efetuar casamento com 10
dos 12 rapazes, pois 2 deles são seus irmãos. Novamente, pelo princípio
multiplicativo é possível realizar 3·10 = 30 casamentos diferentes neste
caso. Finalmente, o Princípio Aditivo nos dá que podem ser realizados
um total de 180 + 30 = 210 casamentos.
Exemplo 5.17. Quantas palavras de 5 caracteres podem ser formadas
com as letras α, β e γ de modo que em cada palavra não falte nenhuma
dessas letras?
Solução. De�namos os seguintes conjuntos,
U ={palavras de 5 caracteres só com as letras α, β e γ};
Aα ={palavras que estão em U e onde não aparece a letra α};
Aβ ={palavras que estão em U e onde não aparece a letra β};
Aγ ={palavras que estão em U e onde não aparece a letra γ}.
180 5 Contagem
Por exemplo,
• a palavra γγγγγ ∈ Aα ∩ Aβ;
• a palavra γααγα ∈ Aβ;
• a palavra βαβββ ∈ Aγ.
Primeiramente, notemos que cada caracter de U pode ser escolhido
de 3 formas distintas. Segue-se então do Princípio Multiplicativo que
existem 35 formas de escrever uma palavra de 5 caracteres usando um
alfabeto de 3 letras, isto é,
S0 = |U| = 35 = 243.
Calculemos agora |Aα|, isto é, o número de palavras onde não apa-
rece a letra α. Para isto, observemos que cada caractere em Aα pode
ser escolhido de 2 formas. Logo, o princípio multiplicativo nos garante
que existem 25 palavras em Aα, ou seja, |Aα| = 25. Analogamente,
podemos mostrar que |Aβ| = |Aγ| = 25. Portanto,
S1 = |Aα|+ |Aβ|+ |Aγ| = 25 + 25 + 25 = 96.
Prosseguimos com o cálculo de |AαAβ|, isto é, do número de pala-
vras onde não aparecem as letras α e β; portanto, cada caractere em
AαAβ pode ser escolhido de 1 forma. Logo, o princípio multiplicativo
nos garante que existe 15 = 1 palavra em AαAβ, ou seja, |AαAβ| = 1.
Similarmente, podemos mostrar que |AαAγ| = |AβAγ| = 1. Portanto,
S2 = |Aα|+ |Aβ|+ |Aγ| = 3.
Por �m, achamos |AαAβAγ|, que nos dá o número de palavras onde
não aparecem as letras α, β e γ; mas cada palavra em AαAβAγ tem
5.4 Permutações Simples 181
que usar pelo menos um dos caracteres proibidos. Logo,
S3 = |AαAβAγ| = 0.
Finalmente, observamos que o conjunto das palavras de 5 caracte-
res que podem ser formadas com as letras α, β e γ de modo que em
cada palavra não falte nenhuma dessas letras é exatamente o conjunto
AcαA
c
βA
c
γ. Usando a Proposição 5.7, temos:
|AcαAcβAcγ| =S0 − S1 + S2 − S3
=243− 96 + 3− 0
=150.5.4 Permutações Simples
De�nimos o fatorial n! de um inteiro positivo n
n! = n · (n− 1) · (n− 2) · · · 2 · 1
se n > 0 e 0! = 1, por convenção. Observe que o fatorial cresce muito
rapidamente quando n cresce. Por exemplo, para os 10 primeiros
valores de n
1!=1 2!=2 3!=6 4!=24 5!=120
6!=720 7!=5.040 8!=40.320 9!=362.880 10!=3.628.800
De�nição 5.18. Uma permutação simples de n objetos distintos é
qualquer agrupamento ordenado desses n objetos. Denotaremos por
Pn o número de todas as permutações simples de n objetos dados.
182 5 Contagem
Por exemplo, todas as permutações dos 3 elementos do conjunto
A = {a1, a2, a3} são:
σ1 = (a1, a2, a3),
σ2 = (a1, a3, a2),
σ3 = (a2, a1, a3),
σ4 = (a2, a3, a1),
σ5 = (a3, a1, a2),
σ6 = (a3, a2, a1).
Proposição 5.19. Seja n ≥ 1. O número total de permutações sim-
ples de n objetos O = {o1, o2, . . . , on} é dado por Pn = n!
Demonstração. É claro que a fórmula vale para n = 1. Vejamos agora
que existe a seguinte relação entre Pn e Pn−1 para n ≥ 2:
Pn = nPn−1. (5.5)
Para comprovar isto, para cada i de�namos Ai como sendo as permu-
tações dos n − 1 objetos {o1, . . . , oi−1, oi+1, . . . , on}. Note que |Ai| =
Pn−1, para cada i = 1, 2, . . . , n. Assim, para obtermos uma permu-
tação dos n objetos, basta que �xemos o objeto inicial oi e tomemos
um elemento do conjunto Ai, que é uma permutação dos n−1 objetos
restantes. Pelo princípio aditivo, temos que:
Pn = |A1|+ |A2|+ · · ·+ |An| = nPn−1.
Como a equação (5.5) é válida para todo n ≥ 2, podemos aplicá-la
para n− 1, obtendo:
Pn−1 = (n− 1)Pn−2,
5.4 Permutações Simples 183
de onde vem que
Pn = n(n− 1)Pn−2.
Repetindo este argumento, obtemos que
Pn = n(n− 1)(n− 2) · · · 3 · 2 · 1 = n!,
como queríamos demonstrar.
Exemplo 5.20. De quantas maneiras podemos formar uma �la com
4 pessoas?
Demonstração. Observe que se enumeramos os lugares da �la e enu-
meramos as pessoas, pa, pb, pc, pd, cada distribuição vai corresponder a
uma permutação do conjunto {1, 2, 3, 4}. Por exemplo, a distribuição
(pc, pa, pb, pd) corresponde à permutação (3, 1, 2, 4). Assim, o número
de distribuições na �la é 4! = 24.
Exemplo 5.21. De quantas maneiras k moças e k rapazes podem
formar pares para uma dança?
Solução. Estando as moças em uma �la e os rapazes em outra, pode-
mos enumerá-los com números de 1, 2, . . . , k. A uma permutação des-
ses números, digamos (a1, a2, . . . , ak) com ai ∈ {1, 2, . . . , k} faremos
uma associação da mulher i com o rapaz ai. Por exemplo, a permu-
tação (2, 1, 3, . . . , k) signi�ca que a moça 1 dançará com o rapaz 2, a
moça 2 com o rapaz 1, e a moça i com o rapaz i, para i ≥ 3.
Observe que toda associação de k moças e k rapazes produz uma
permutação, de modo que o número de associações possíveis das mo-
ças com os rapazes é igual ao número de permutações dos elementos
do conjunto {1, 2, 3, . . . , k}. Pela Proposição 5.19 existem k! modos
diferentes de combinar as moças com os rapazes.
184 5 Contagem
5.5 Arranjos Simples
De�nição 5.22. Consideremos n objetos e p um inteiro positivo tal
que 0 < p ≤ n. Um arranjo simples de classe p dos n objetos dados
é uma seleção de p objetos distintos dentre estes que diferem entre si
pela ordem de colocação ou pela natureza de cada um, isto é, o que
importa é quem participa ou o lugar que ocupa. Denotaremos por Apn
o número de arranjos simples de classe p de n objetos.
Por exemplo, dados os objetos o1, o2 e o3 todos os arranjos possíveis
de classe 2 são: A1 = (o1, o2), A2 = (o2, o1), A3 = (o1, o3), A4 =
(o3, o1), A5 = (o2, o3) e A6 = (o3, o2).
Observação 5.23. Notemos que um arranjo simples de classe n de n
objetos dados não é mais que uma permutação desses n objetos. Logo,
Pn = A
n
n = n!.
Proposição 5.24. Seja n ≥ 1. O número total de arranjos simples
de classe p de n objetos O = {o1, o2, . . . , on} é dado por Apn = n!(n−p)! .
Demonstração. Para n = 1 a fórmula é obviamente válida. Similar-
mente ao caso das permutações, primeiramente provaremos que para
n ≥ 2 vale a seguinte igualdade:
Apn = nA
p−1
n−1. (5.6)
Agora de�nimos os conjuntos Ai como sendo os arranjos simples de
classe p − 1 dos n − 1 objetos {o1, . . . , oi−1, oi+1, . . . , on}. Note que
|Ai| = Ap−1n−1, para cada i = 1, 2, . . . , n. Assim, para obtermos um
arranjo simples de classe p dos n objetos, basta que �xemos o objeto
inicial oi e tomemos um elemento do conjunto Ai, que é uma arranjo
5.5 Arranjos Simples 185
de classe p − 1 dos n − 1 objetos restantes. Pelo princípio aditivo,
temos que:
Apn = |A1|+ |A2|+ · · ·+ |An| = nAp−1n−1.
Como nossa equação (5.6) é válida para todo n ≥ 2, podemos aplicá-la
para n− 1, obtendo:
Ap−1n−1 = (n− 1)Ap−2n−2,
de onde vem que
Apn = n(n− 1)Ap−2n−2.
Repetindo este argumento sucessivamente, obtemos que
Apn = n(n− 1)(n− 2) · · · (n− (p− 2))Ap−(p−1)n−(p−1)
= n(n− 1)(n− 2) · · · (n− p+ 2)A1n−p+1.
Notemos agora que A1n−p+1 = n − p + 1; logo, da igualdade anterior
segue-se que
Apn = n(n− 1)(n− 2) · · · (n− p+ 2)(n− p+ 1)
=
n(n− 1)(n− 2) · · · (n− p+ 2)(n− p+ 1)× (n− p) · · · 1
(n− p) · · · 1
=
n!
(n− p)! ,
como desejávamos.
Agora vamos dar alguns exemplos de como aparecem problemas
práticos que requerem fazer este tipo de cálculo. O primeiro dele tem
186 5 Contagem
a ver com a formação de palavras diferentes com um conjunto dado
de letras.
Um anagrama de uma palavra é uma permutação de letras dessa
palavra para formar outra, a qual pode carecer de signi�cado. Por
exemplo:
• um anagrama de amor é roma;
• um anagrama de celia é alice;
• um anagrama de caterina é natercia;
• um anagrama de elvis é lives.
Exemplo 5.25. Quantos anagramas de p letras distintas podemos
formar com um alfabeto de 23 letras, sendo p < 23?
Solução. Como as letras são diferentes, nosso problema consiste em
achar todos os arranjos de classe p de 23 objetos dados, que neste caso
são as 23 letras do alfabeto. Logo, este número é
Ak23 =
23!
(23− k)! .
Exemplo 5.26. De quantos modos 2 pessoas podem se sentar em 5
cadeiras que estão em �la?
Solução. Este problema é equivalente a achar o número total de ar-
ranjos de classe 2 de 5 objetos, correspondendo as 5 cadeiras aos 5
objetos e as duas pessoas indicando a ordem do arranjo. Logo, este
número é dado por
A25 =
5!
3!
= 20.
5.5 Arranjos Simples 187
Exemplo 5.27. Considere os dígitos 2, 3, 4, 5, 7 e 9. Supondo que a
repetição de dígitos não seja permitida, responda às seguintes pergun-
tas:
(a) Quantos números de três dígitos podem ser formados?
(b) Entre os achados em (a) quantos são pares?
(c) Entre os achados em (a) quantos são ímpares?
(d) Entre os achados em (a) quantos são múltiplos de 5?
(e) Entre os achados em (a) quantos são menores do que 400?
Solução. Seja O = {2, 3, 4, 5, 7, 9} nosso conjunto de objetos.
(a) A quantidade de números de três dígitos que podemos formar
sem repetição de algum deles é claramente o número de arranjos
de classe 3 dos 6 dígitos de O, isto é,
A36 =
6!
3!
= 120.
(b) Sabemos que em todo número par o último dígito é um múltiplo
de 2, isto é, ele acaba em 0, 2, 4, 6 ou 8. Então, em nosso caso
as únicas possibilidades são que o número termine em 2 ou 4.
Supondo que o último dígito seja 2, temos que preencher as duas
casas restantes com os dígitos pertencentes ao conjunto O−{2}.
Assim, existem A2|O−{2}| = A
2
5 =
5!
3!
= 20 números dos achados
em (a) que �nalizam em 2. De forma análoga, existem A2|O−{4}| =
A25 =
5!
3!
= 20 números dos achados em (a) que �nalizam em 4.
Logo, entre os números achados em (a) existem 20 + 20 = 40
números pares.
188 5 Contagem
(c) Todo conjunto de números pode ser dividido em duas classes
disjuntas: a classe dos números pares e a classe dos números ím-
pares que pertencem ao mesmo. Segue-se que dentre os números
achados em (a) existem 120− 40 = 80 números ímpares.
(d) Todo número múltiplo de 5 acaba em 0 ou 5; no nosso caso te-
mos que a única possibilidade para o último dígito é 5. Assim
o problema consiste em preencher as duas casas restantes com
dígitosdo conjunto O − {5}. De onde se segue que a quanti-
dade de números múltiplos de 5 existentes em (a) vem dada por
A2|O−{5}| = A
2
5 =
5!
3!
= 20.
(e) Para obter os números menores do que 400 a casa das centenas
só poderá ser ocupada pelos dígitos 1, 2 ou 3. Como 1 /∈ O,
temos que as únicas possibilidades em nosso caso são 2 ou 3.
Então, supondo que o primeiro dígito do número seja 2, devemos
preencher duas casas restantes com os dígitos pertencentes a
O − {2}. De forma análoga, existem A2|O−{3}| = A25 = 5!3! = 20
números dos achados em (a) e que começam com 3. Logo, dentre
os números achados em (a) existem 20+20 = 40 menores do que
400.
5.6 Combinações Simples
O conceito de combinação simples surge naturalmente quando tenta-
mos responder à seguinte pergunta:de quantas formas diferentes pode-
mos selecionar p objetos dentro de n objetos dados?
5.6 Combinações Simples 189
Por exemplo, suponha que queremos enfeitar uma festa de aniver-
sário com bolas de dois tipos de cores e na loja onde as compraremos
existem bolas nas cores azul, verde e vermelha. De quantas formas
distintas podemos enfeitar nossa festa? É claro que podemos enfeitar
a festa de 3 formas diferentes: com bolas em azul e verde; com bolas
em azul e vermelho ou com bolas em verde e vermelho.
Notemos que, ao contrário do caso em que trabalhamos com arran-
jos, quando fazemos uma seleção de duas cores não estamos inte-
ressados na ordem em que elas foram escolhidas.
De�nição 5.28. Consideremos n objetos e p um inteiro positivo tal
que 0 < p ≤ n. Uma combinação simples de classe p dos n objetos
dados é uma seleção de p objetos distintos entre estes que diferem
entre si apenas pela natureza de cada um, isto é, o que importa é
simplesmente quem participa no grupo selecionado. Denotaremos por(
n
p
)
o número de combinações simples de classe p de n objetos.
Proposição 5.29. Seja n ≥ 1. O número total de combinações
simples de classe p de n objetos O = {o1, o2, . . . , on} é dado por(
n
p
)
= n!
p!(n−p)! .
Demonstração. Veremos a seguir que arranjos simples e combinações
simples de classe p estão estreitamente relacionados. Com efeito, para
cada combinação simples formada por p objetos distintos de O pode-
mos gerar todos os arranjos simples de classe p formados por estes p
objetos. Basta para isto fazer todas as suas permutações possíveis.
Obtém-se assim p ! arranjos simples diferentes com esses p objetos.
Resumindo, para cada combinação simples de classe p formada com
p objetos diferentes de O podemos fazer p ! arranjos simples diferen-
tes de classe p com estes mesmos objetos; logo, no total, teremos a
190 5 Contagem
seguinte relação:
p !
(
n
p
)
= Apn =
n!
(n− p)! ,
de onde segue-se que
(
n
p
)
=
n!
p!(n− p)! .
Exemplo 5.30. De quantas formas diferentes podemos construir uma
palavra de tamanho n com i letras a e n− i letras b?
Solução. A solução do problema equivale em escolher a posição das
i letras a em questão, uma vez que a posição das (n − i) letras b
restantes estará determinada. Se enumeramos as posições das letras
de 1 a n, uma palavra será formada ao �xarmos a posição das i letras
a. Isso é exatamente
(
n
i
)
, já que corresponde ao número de grupos
com i elementos (posições com letra a) tomados em um conjunto de n
elementos (todas as posições), que diferem somente por sua natureza.
Exemplo 5.31. De quantas formas podemos dividir um grupo 5 pes-
soas em um grupo de duas e outro de três?
Solução. Temos
(
5
2
)
= 5 !
2 !3 !
= 10 formas diferentes de escolher duas
pessoas do grupo. Por cada uma dessas escolhas o outro grupo de três
pessoas é automaticamente determinado; logo, temos 10 possibilidades
diferentes de fazer a divisão.
Exemplo 5.32. De quantos modos podemos dividir 6 pessoas em:
(a) Dois grupos de 3 pessoas cada?
5.6 Combinações Simples 191
(b) Três grupos de 2 pessoas cada?
Solução. Começamos por (a). À primeira vista, parece que a resposta
deve ser
(
n
3
)
= 6!
3! 3!
= 20, similarmente ao exemplo anterior. Porém,
aqui há um problema devido ao fato de estarmos dividindo em grupos
que têm a mesma quantidade de pessoas e, portanto, as permutações
de cada dois grupos formados são consideradas divisões iguais; logo,
devemos dividir o resultado por 2 !, obtendo assim 10 formas diferentes
de obter dois grupos com 3 pessoas cada.
Para resolver o item (b) seguimos os seguintes passos:
• Primeiramente calcularemos o número de formas possíveis para
dividir 6 pessoas em um grupo de 2 e outro grupo de 4; esta
quantidade vem dada por
(
6
2
)
= 6!
4! 2!
.
• Agora dividiremos as 4 pessoas restantes em um grupo de 2 e
outro grupo de 2; esta quantidade vem dada por
(
4
2
)
= 4!
2! 2!
.
Pelo princípio multiplicativo temos que existem
(
6
2
)(
4
2
)
= 6!
(2!)3
possi-
bilidades de dividir 6 pessoas em 3 grupos com duas pessoas cada.
Igualmente ao caso anterior, aqui as permutações possíveis de cada 3
grupos formados são consideradas iguais; logo, devemos dividir este
último resultado por 3 !. Portanto, existem 15 formas diferentes de
dividir 6 pessoas em três grupos de 2 pessoas cada.
Exemplo 5.33. Se você possui 10 amigos, de quantas maneiras você
pode escolher dois ou mais deles para jantar?
Solução. Esquematizamos a solução da seguinte maneira:
• Primeiramente, vamos encontrar a quantidade de maneiras pelas
quais você pode jantar com 2 amigos; isto é feito de
(
10
2
)
formas
diferentes.
192 5 Contagem
• Depois, vamos encontrar a quantidade de maneiras pelas quais
você pode jantar com 3 amigos; isto é feito de
(
10
3
)
formas dife-
rentes.
• Em seguida, encontramos a quantidade de maneiras pelas quais
você pode jantar com 4 amigos; isto é feito de
(
10
4
)
formas dife-
rentes.
• Em geral, o número de maneiras diferentes que você tem de
jantar com p amigos é dado por
(
10
p
)
.
Pelo princípio aditivo, temos que a quantidade de formas diferentes
que você tem de jantar com 2 ou mais de seus amigos, é dada por
(
10
2
)
+
(
10
3
)
+ · · ·+
(
10
9
)
+
(
10
10
)
= 1013,
sendo este o número procurado.
Exemplo 5.34. De um grupo de 10 pessoas das quais 4 são mulheres,
quantas comissões de 5 pessoas podem ser formadas de modo que pelo
menos uma mulher faça parte?
Solução. Sendo que o grupo tem 10 pessoas e 4 destas são mulheres,
segue-se que no grupo temos 6 homens. Para formar um grupo de 5
pessoas com pelo menos uma mulher, temos as seguintes alternativas:
• Nosso grupo é composto por uma mulher e 4 homens; neste caso
poderemos formar
(
4
1
)(
6
4
)
= 60 comissões de 5 pessoas.
• Nosso grupo é composto por 2 mulheres e 3 homens; neste caso
poderemos formar
(
4
2
)(
6
3
)
= 120 comissões de 5 pessoas.
5.7 O Binômio de Newton 193
• Nosso grupo é composto por 3 mulheres e 2 homens; neste caso
poderemos formar
(
4
3
)(
6
2
)
= 60 comissões de 5 pessoas.
• Nosso grupo é composto por 4 mulheres e um homem; neste caso
poderemos formar
(
4
4
)(
6
1
)
= 6 comissões de 5 pessoas.
Pelo princípio aditivo temos que é possível formar 246 comissões de 5
pessoas de modo que pelo menos uma mulher faça parte.
5.7 O Binômio de Newton
Nesta seção, estudaremos uma fórmula que generaliza a conhecida
expressão
(a+ b)2 = a2 + 2ab+ b2.
Essa fórmula é conhecida como o binômio de Newton ou fórmula bino-
mial de Newton, devido ao Matemático Isaac Newton (1642-1727). A
fórmula binomial de Newton pode ser motivada pelas seguintes igual-
dades que são fáceis de veri�car:
(a+ b)1 = a+ b =
(
1
0
)
a+
(
1
1
)
b,
(a+ b)2 = a2 + 2ab+ c2 =
(
2
0
)
a2 +
(
2
1
)
ab+
(
2
2
)
b2,
(a+ b)3 = a3 + 3a2b+ 3ab2 + c3 =
(
3
0
)
a3 +
(
3
1
)
a2b+
(
3
2
)
ab2 +
(
3
3
)
b3.
Os casos particulares acima podem ser estendidos para qualquer po-
tência inteira positiva de a+ b, ou seja, vale o seguinte resultado:
194 5 Contagem
Teorema 5.35 (Fórmula Binomial de Newton). Sejam a e b números
reais e n ∈ N, então
(a+b)n =
(
n
0
)
an+
(
n
1
)
an−1b1+· · ·+
(
n
i
)
an−ibi+· · ·+
(
n
n−1
)
a1bn−1+
(
n
n
)
bn.
Os números
(
n
i
)
, 0 ≤ i ≤ n, são chamados também de coe�cientes bino-
miais.
Demonstração. Expandimos o binômio no produto de seus n fatores,
isto é,
(a+ b)n = (a+ b)(a+ b) · · · (a+ b)︸ ︷︷ ︸
n−fatores
. (5.7)
Se desenvolveremos o produto destes n fatores iguais acima obtemos
uma soma �nita de termos da forma a1a2 · · · an, onde cada aj, 1 ≤
j ≤ n, toma valor a ou b. Notemos que em cada termo se o número
b aparece i vezes, então o número a aparecerá (n − i) vezes, ou seja,
quando cada termo for multiplicado deverá tomar valor igual a an−ibi,
para algum 1 ≤ i ≤ n. Por exemplo, os n termos
abb · · · b = abn, bab · · · b = abn, . . . , bbb · · · ba = abn
têm o mesmo valor . Assim, para calcular o coe�ciente do termo aibn−i
que aparece na equação (5.7), basta responder à seguinte pergunta: de
quantos modos podemos formar uma palavra com i letras a e (n− i)
letras b? A resposta dessa pergunta foi estudada no Exemplo 5.30 e é
simplesmente
(
n
i
)
. Logo, a expressão na equação (5.7) é
(a+ b)n =
(
n
0
)
an +
(
n
1
)
an−1b1 + · · ·+
(
n
n− 1
)
a1bn−1 +
(
n
n
)
bn,
o que prova o teorema.
5.8 Contagem e Probabilidades 195
A fórmula binomial de Newton nos dá algumas propriedades interes-
santes dos coe�cientes binomiais que resumimos na próxima proposi-
ção.
Proposição 5.36. Seja n ∈ N. As seguintes igualdades são válidas:
(a)
(
n
0
)
+
(
n
1
)
+ · · ·+
(
n
i
)
+ · · ·+
(
n
n−1
)
+
(
n
n
)
= 2n;
(b)
(
n
0
)
−
(
n
1
)
+ · · ·+ (−1)i
(
n
i
)
+ · · ·+ (−1)n
(
n
n
)
= 0.
Demonstração. Para a letra (a), basta tomar a = b = 1 e expanda
2n = (1 + 1)n no Binômio de Newton. Para a letra (b), tome a = 1
e b = −1 e expanda 0 = (1− 1)n no binômio de Newton, observando
que (−1)n é igual a 1 se n é par, e igual a 1 se n é ímpar.
5.8 Contagem e Probabilidades
Uma das aplicações interessantes da contagem de elementos de um
conjunto é quando desejamos estudar a probabilidade de eventos alea-
tórios. Por exemplo, se lançarmos um dado de seis faces, temos os
seguintes resultados possíveis:
Ω = {1, 2, . . . , 6}.
Se desejamos saber qual é a chance de que ocorra um número
primo no lançamento, devemos contar quantos primos aparecem em
{1, 2, 3, 4, 5, 6} e dividir por 6. Ou seja, a chance de ocorrer um número
primo num lançamento de um dado de seis faces é 3/6 = 0, 5.
De�nimos a probabilidade de um subconjunto A ⊂ Ω como o nú-
mero
p(A) =
|A|
|Ω| .
196 5 Contagem
Também chamamos o subconjunto Ω de todos os resultados possíveis
de espaço amostral e um subconjunto A de Ω de evento. Por exemplo,
podemos calcular a probabilidade de escolhermos um número par no
conjunto 1, 2, 3, . . . , 15. Neste caso, o conjunto Ω está claro e é igual a
Ω = {1, 2, 3, . . . , 15}. O conjunto A é A = {2, 4, 6, . . . , 14}. Logo,
p(A) =
|A|
|Ω| =
7
15
.
Assim, �ca claro que a maior di�culdade para calcular a proba-
bilidade de um evento é contar quantos elementos pertencem a este
evento e quantos elementos pertencem ao espaço amostral. A seguir,
veremos um exemplo mais elaborado onde aplicamos a noção de ar-
ranjo simples.
Exemplo 5.37. Calcular a probabilidade de que escolhendo um grupo
de 44 pessoas, existam pelo menos duas que fazem aniversário no
mesmo dia do ano.
Solução. Podemos reescrever isso do seguinte modo: num saco existem
bolas enumeradas com os números 1, 2, . . . , 365 (correspondentes aos
dias do ano). Retiramos a bola b1 e anotamos o número que apareceu.
Devolvemos a bola ao saco e efetuamos uma nova retirada, anotando
novamente o número que aparece. Repetindo este processo 44 vezes,
obtemos uma lista com 44 números. Assim, a pergunta se transforma
em: de quantos modos diferentes podemos escolher 44 bolas enume-
radas com os números 1, 2, 3, . . . , 365 com reposição, tal que existam
pelo menos duas bolas com o mesmo número?
A primeira coisa que devemos fazer é calcular o espaço amostral,
de todas as possibilidades possíveis de resultado. Como escolhemos
44 bolas enumeradas num saco, cada resultado possível é uma lista
5.9 Exercícios Propostos 197
(n1, n2, . . . , n44) com 44 números. Observe que, pelo princípio multi-
plicativo, |Ω| = 36544, pois temos 365 opções para escolher n1, 365
opções para escolher n2, etc.
A segunda pergunta trata-se de saber quantos resultados são favo-
ráveis, ou seja, quantas são as escolhas tais que existam pelo menos
duas bolas com o mesmo número. Para isso é mais fácil contar quantas
escolhas existem tais que os 44 números são diferentes. Neste caso,
devemos escolher uma ordenação de 44 números distintos entre 365.
Isso corresponde à quantidade de arranjos de classe 44 num grupo de
365 elementos. Assim, concluímos que a probabilidade de que este
evento ocorra é
p =
36544 −A44365
36544
= 1−
365!
(365!−44!)
36544
.
Obter um valor aproximado para o número acima com o computador é
uma tarefa fácil nos dias atuais. Porém, aproximar expressões envolvendo
fatoriais (sem o uso do computador) é um fato conhecido há muito tempo
pela humanidade, através da famosa fórmula de Stirling.1 Com a ajuda
desta fórmula, obtemos que p é aproximadamente p ∼= 0.93, como havíamos
prometido no Capítulo 1.
Além dos exercícios abaixo, recomendamos a leitura de [9]. Lá, o
leitor encontrará material adicional sobre análise combinatória, bem
como uma ampla variedade de problemas.
5.9 Exercícios Propostos
1. De quantas maneiras podemos escolher três números distintos do
conjunto I50 = {1, 2, 3, . . . , 49, 50} de modo que sua soma seja
1Grosseiramente, a fórmula de Stirling diz que o quociente entre n! e√
2πnnne−n está próximo de 1, para valores de n grandes.
198 5 Contagem
a) um múltiplo de 3?
b) um número par?
2. Considere o conjunto In = {1, 2, 3, . . . , n−1, n}. Diga de quantos
modos é possível formar subconjuntos de k elementos nos quais
não haja números consecutivos?
3. Considere as letras da palavra PERMUTA. Quantos anagramas
de 4 letras podem ser formados, onde:
a) não há restrições quanto ao número de consoantes ou vogais?
b) o anagrama começa e termina por vogal?
c) a letra R aparece?
d) a letra T aparece e o anagrama termina por vogal?
4. Calcular a soma de todos os números de 5 algarismos distintos
formados com os algarismos 1, 3, 5, 7 e 9.
5. Quantos números podem ser formados pela multiplicação de al-
guns ou de todos os números 2, 2, 3, 3, 3, 5, 5, 6, 8, 9, 9?
6. Entre todos os números de sete dígitos, diga quantos possuem
exatamente três dígitos 9 e os quatro dígitos restantes todos
diferentes?
7. De quantas maneiras podemos distribuir 22 livros diferentes en-
tre 5 alunos se 2 deles recebem 5 livros cada e os outros 3 recebem
4 livros cada?
8. Quantos são os números naturais de sete dígitos nos quais o
dígito 4 �gura exatamente 3 vezes e o dígito 8 �gura exatamente
2 vezes?
5.9 Exercícios Propostos 199
9. De quantas maneiras uma comissão de 4 pessoas pode ser for-
mada, de um grupo de 6 homens e 6 mulheres, se a mesma é
composta de um número maior de homens do que de mulheres?
10. O comprimento de uma palavra é a quantidade de caracteres que
ela possui. Encontre a quantidade de palavras de comprimento
5 que podemos formar fazendo uso de 10 caracteres distintos, de
forma que não existam três caracteres consecutivos idênticos em
cada palavra.
11. Quantos números inteiros existem entre 1 e 10.000 que não são
divisíveis por 3, 5 e 7?
12. Quantas são as permutações da palavra PROPOR nas quais não
existem letras consecutivas iguais?
13. De quantos modos 6 casais podem sentar-se ao redor de uma
mesa circular de tal forma que marido e mulher não �quem jun-
tos?
14. Quantas são as permutações das letras da palavra BRASIL em
que o B ocupa o primeiro lugar, ou o R ocupa o segundo lugar,
ou o L o sexto lugar?
15. De quantas formas podemos representar o número 15 como soma
de vários números naturais?
16. Quantos quadrados perfeitos existem entre 40.000 e 640.000 que
são múltiplos simultaneamente de 3, 4 e 5?
17. Oito amigos vão aocinema assistir a um �lme que custa um real.
Quatro deles possuem uma nota de um real e quatro possuem
200 5 Contagem
uma nota de dois reais. Sabendo-se que o caixa do cinema não
possui nenhum dinheiro, como eles podem organizar uma �la
para pagar o �lme permitindo o troco pelo caixa?
18. Se considerarmos todas as con�gurações do tabuleiro com duas
torres que não se atacam, como no Exemplo 5.2, sem distinguir
as torres, quantas con�gurações obteremos?
19. Continuando o problema anterior, generalize-o para 3, 4, 5, . . .
torres que não se atacam, encontrando também o número máxi-
mo de torres que podem ser colocadas no tabuleiro de modo que
duas delas não se ataquem.
20. Tente fazer o problema anterior para cavalos de xadrez.
21. Mostre que em toda sequência de n2 + 1 inteiros distintos possui
uma subsequência crescente de n + 1 elementos ou uma sub-
sequência decrescente de n+ 1 elementos.
22. Encontre o número de zeros que termina o número 2010!.
23. O jogo do 7 consiste em lançar dois dados e somar o número
obtido nas suas faces. Caso a soma seja 7, o jogador A ganha o
dois reais do jogador B. Caso a soma não seja 7, o jogador B
ganha um real de A. Pergunta-se: quem leva vantagem?
24. A função φ de Euler associa a cada número natural n o valor
φ(n) igual ao número de inteiros positivos menores ou iguais a
n relativamente primos com n. Ou seja,
φ(n) =
∣∣{1 ≤ m ≤ n; (m,n) = 1}
∣∣.
5.9 Exercícios Propostos 201
Usando os princípios estudados, mostre que se n se decompõe
em fatores primos como n = p1α1p2α2 . . . p
αk
k , então
φ(n) = n
(
1− 1
p1
)(
1− 1
p2
)
. . .
(
1− 1
pk
)
.
O leitor pode achar mais informações sobre a função φ de Euler
nos livros [11] ou ainda [10].
202 5 Contagem
6
Indução Matemática
Se as pessoas não a
ham a Matemáti
a simples é só por que aindanão per
eberam o quanto a vida é 
ompli
ada. John von Neumann
Imagine uma �la com in�nitos dominós, um atrás do outro. Supo-
nha que eles estejam de tal modo distribuídos que, uma vez que um
dominó caia, o seu sucessor na �la também cai. O que acontece quando
derrubamos o primeiro dominó?
Apesar da simplicidade da pergunta acima ela traz em sua essência
toda a ideia usada no método da indução �nita. Muitas descobertas
em Matemática são feitas baseadas na realização de testes que nos
fornecem evidências empíricas. Tais evidências são estudadas para
efetivamente veri�carmos se os resultados que elas insinuam são ver-
dadeiros. O método da indução �nita constitui uma ferramenta muito
útil na hora de desvendar a veracidade de resultados provenientes deste
tipo de estudo. Esse método é uma das grandes armas do matemático
moderno e tem utilidade na solução de vários problemas, como iremos
ver ao longo deste capítulo.
203
204 6 Indução Matemática
6.1 Formulação Matemática
No início do século XX, o matemático Giuseppe Peano (1858-1932)
estabeleceu os axiomas necessários que nos permitem hoje descrever
com precisão o conjunto dos números naturais. O último dos seus
axiomas diz o seguinte: seja A um subconjunto de N (A ⊂ N). Se 1 ∈
A e se, além disso, A contém todos os sucessores dos seus elementos,
então A = N.
Este axioma é conhecido como axioma de indução e serve como
base do método de demonstração por indução, o qual é de grande
utilidade para estabelecer provas rigorosas em Matemática.
O princípio da boa ordenação dos naturais, enunciado no Capí-
tulo 3, e o axioma de indução não são independentes e sem nenhuma
conexão. De fato, eles são equivalentes, ou seja, se consideramos o
princípio da boa ordenação como sendo um postulado podemos dedu-
zir o axioma de indução e, reciprocamente, se consideramos o axioma
de indução como sendo um postulado podemos deduzir o princípio da
boa ordenação.
No resto do capítulo, p(n) representa uma a�rmação em relação ao
natural n, podendo esta ser verdadeira ou falsa.
Teorema 6.1 (Princípio da Indução Finita). Considere n0 um in-
teiro não negativo. Suponhamos que, para cada inteiro n ≥ n0, seja
dada uma proposição p(n). Suponha que se pode veri�car as seguintes
propriedades:
(a) p(n0) é verdadeira;
(b) se p(n) é verdadeira então p(n + 1) também é verdadeira, para
todo n ≥ n0.
6.1 Formulação Matemática 205
Então, p(n) é verdadeira para qualquer n ≥ n0.
A a�rmação (a) é chamada de base da indução e a (b) de passo
indutivo. O fato de que p(n) é verdadeira no item (b) é chamado de
hipótese da indução.
Demonstração. De�namos o conjunto
V = {m inteiros não negativos; m ≥ n0 e p(m) é verdadeira} .
Notemos que V é não vazio, pois a condição (a) nos assegura que
n0 ∈ V . A prova do teorema é equivalente a mostrarmos que
V = {n0, n0 + 1, n0 + 2, n0 + 3, · · · },
ou equivalentemente, a provarmos que o conjunto
F = {m inteiros não negativos; m ≥ n0 e p(m) é falsa}
é vazio. Suponhamos que F é não vazio. Pelo principio da boa orde-
nação existe um menor elemento m0 ∈ F , onde p(m0) é falso. Obser-
vemos que,
• m0 ≥ n0 + 1. De fato, m0 ≥ n0, porém a possibilidade m0 = n0
contradiz a condição (a);
• m0 − 1 ∈ V . Com efeito, p(m0 − 1) é verdadeira pois, caso
contrário, m0−1 ∈ F e, além disso, m0−1 < m0, contradizendo
isto a minimalidade de m0.
Finalmente, como p(m0 − 1) é verdadeira, segue da condição (b) que
p(m0) também é verdadeira, o que é impossível pela de�nição de m0.
Portanto, o conjunto F é vazio, concluindo-se assim a prova.
206 6 Indução Matemática
Para um pouco mais sobre a relação entre os princípios de indução
e da boa ordenação, recomendamos o Apêndice A da referência [11].
Observação 6.2. Uma grande vantagem do princípio da indução �-
nita é poder provar que uma quantidade in�nita de a�rmações são
verdadeiras, simplesmente veri�cando que uma quantidade �nita des-
tas a�rmações são verdadeiras. Deixaremos clara a utilidade deste
método resolvendo alguns problemas na próxima seção.
6.2 Aplicações
Dentro da grande gama de problemas que podem ser abordados apli-
cando o método de indução podemos distinguir três importantes gru-
pos:
• demonstração de identidades;
• demonstração de desigualdades;
• demonstração de problemas de divisibilidade.
A seguir damos vários exemplos de como aplicar o método em
problemas referentes a cada um destes grupos.
6.2.1 Demonstrando Identidades
Começamos com os seguintes problemas clássicos:
(P1) Determinar uma fórmula para a soma dos n primeiros números
pares, isto é,
sp(n) := 2 + 4 + 6 + · · ·+ 2n.
6.2 Aplicações 207
(P2) Determinar uma fórmula para a soma dos n primeiros números
ímpares, isto é,
si(n) := 1 + 3 + 5 + · · ·+ 2n− 1.
Para induzir ambas as fórmulas, primeiro fazemos os cálculos para
vários valores de n, os quais apresentamos na seguinte tabela.
n 1 2 3 4 5 · · ·
sp(n) 2 = 1 · 2 6 = 2 · 3 12 = 3 · 4 20 = 4 · 5 30 = 5 · 6 · · ·
si(n) 1 = 12 4 = 22 9 = 32 16 = 42 25 = 52 · · ·
Os resultados na tabela sugerem que sp(n) = n(n + 1) e que
si(n) = n
2. Entretanto, isto não constitui por si só uma prova ri-
gorosa destas fórmulas, pois para poder garantir a veracidade delas
utilizando a tabela teríamos que veri�car cada valor de n natural,
sendo isto impossível. Provaremos agora que, de fato, as fórmulas
induzidas são válidas usando o método de indução �nita.
Exemplo 6.3. Demonstre que para qualquer n ∈ N é válida a igual-
dade:
2 + · · ·+ 2n = n(n+ 1).
Solução. De�namos a proposição
p(n) : 2 + · · ·+ 2n = n(n+ 1)
e observemos que a mesma vale para n = 1 (base da indução); de fato
p(1) : 2 = 1(1 + 1).
Agora partimos para a prova do passo indutivo:
208 6 Indução Matemática
• Hipótese: suponhamos que p(k) é verdadeira para um certo k >
1, k ∈ N.
• Tese: devemos mostrar que p(k + 1) também é verdadeira.
Com efeito, como
2 + · · ·+ 2k = k(k + 1),
somando 2(k + 1) a ambos os lados desta igualdade, temos que
2 + · · ·+ 2k + 2(k + 1) = k(k + 1) + 2(k + 1)
= (k + 2)(k + 1).
Esta última igualdade a�rma que p(k + 1) também é verdadeira. O
Princípio de Indução nos garante que p(n) é verdadeira para qualquer
n ∈ N.
Exemplo6.4. Demonstre que para qualquer n ∈ N é válida a igual-
dade:
1 + 3 + 5 + · · ·+ 2n− 1 = n2.
Solução. Aqui de�nimos a proposição:
p(n) : 1 + 3 + 5 + · · ·+ 2n− 1 = n2
e notamos que a mesma é válida se tomarmos, por exemplo, n = 1.
De fato,
p(1) : 1 = 2 · 1− 1.
Agora só resta provar o passo indutivo:
• Hipótese: suponhamos que p(k) seja verdadeira para um certo
k > 1, k ∈ N.
6.2 Aplicações 209
• Tese: devemos mostrar que p(k + 1) também é verdadeira.
Com efeito, como
1 + 3 + 5 + · · ·+ 2k − 1 = k2,
somando 2k + 1 a ambos os lados desta igualdade, temos que
1 + 3 + 5 + · · ·+ 2k − 1 + 2k + 1 = k2 + 2k + 1
= (k + 1)2.
O princípio de indução nos garante que p(n) é verdadeira para
qualquer n ∈ N.
Uma consequência imediata do Exemplo 6.3 é a fórmula para a
soma dos n primeiros números naturais, dada por
sn = 1 + 2 + 3 + · · ·+ n =
n(n+ 1)
2
. (6.1)
Com efeito, como
2 + 4 + · · ·+ 2n = n(n+ 1),
então dividindo por 2 ambos os membros da igualdade acima, obtemos
a equação (6.1).
Continuando com o mesmo raciocínio, é natural nos perguntarmos
se é possível obter uma fórmula para a soma dos n primeiros quadrados
perfeitos, ou seja, determinar qn onde:
qn = 1
2 + 22 + 32 + · · ·+ n2.
Para induzir a fórmula, consideramos os valores de sn e qn numa tabela:
210 6 Indução Matemática
n 1 2 3 4 5 6 · · ·
sn 1 3 6 10 15 21 · · ·
qn 1 5 14 30 55 91 · · ·
Aparentemente não existe nenhuma relação entre sn e qn. Mas, se
considerarmos o quociente qn/sn, vejamos o que acontece:
n 1 2 3 4 5 6 · · ·
qn/sn 3/3 5/3 7/3 9/3 11/3 13/3 · · ·
Isso nos sugere que vale a relação
qn
sn
=
2n+ 1
3
,
logo nosso candidato para valor de qn é
qn =
sn(2n+ 1)
3
=
n(n+ 1)(2n+ 1)
6
.
Convidamos o leitor a provar a veracidade da equação acima utilizando o
Método da Indução no Exercício 1 no �nal do capítulo.
6.2.2 Demonstrando Desigualdades
Apresentamos agora alguns exemplos de como usar indução para provar
desigualdades.
Exemplo 6.5. Prove que 3n−1 < 2n
2
para todo n ∈ N.
Solução. Denotamos por p(n) a propriedade: 3n−1 < 2n
2
. É claro que p(1)
é válida, pois 1 < 2. Agora supondo que P (n) é verdadeira temos que
3n = 3n−1 · 3 < 2n2 · 22n+1 = 2(n+1)2 ,
logo p(n+1) também vale. Observamos que na desigualdade acima usamos
o fato de que 3 < 22n+1 para qualquer n ∈ N.
6.2 Aplicações 211
Exemplo 6.6. Mostre que para todo número n ∈ N, n > 3, vale que 2n < n!
Demonstração. Para n = 4 a desigualdade é veri�cada, pois 24 = 16 < 4! =
24. Vamos assumir como hipótese de indução que a desigualdade é válida
para n ≥ 4. Então, precisamos mostrar que a mesma vale também para
n+ 1. De fato, por hipótese de indução:
2n < n! (6.2)
Como 2 < n + 1, podemos multiplicar o lado esquerdo da desigualdade
em (6.2) por 2 e o lado direito por n+1, sem alterar o sinal de desigualdade.
Logo, temos que:
2n.2 = 2n+1 < n!(n+ 1) = (n+ 1)!,
concluindo-se a demonstração.
Exemplo 6.7. Prove que, para todo n ∈ N,
√
2 +
√
2 +
√
2 + · · ·+
√
2
︸ ︷︷ ︸
n−radicais
< 2.
Demonstração. Claramente a desigualdade vale para n = 1, pois
√
2 < 2.
Suponhamos que para certo n ∈ N a desigualdade acontece, então
√
2 +
√
2 +
√
2 + · · ·+
√
2
︸ ︷︷ ︸
n−radicais
< 2.
Logo, adicionando 2 em ambos os lados desta desigualdade tem-se
2 +
√
2 +
√
2 +
√
2 + · · ·+
√
2
︸ ︷︷ ︸
n−radicais
< 2 + 2.
212 6 Indução Matemática
Tomando raiz quadrada em ambos os lados desta última desigualdade ob-
temos √√√√
2 +
√
2 +
√
2 +
√
2 + · · ·+
√
2
︸ ︷︷ ︸
n+1−radicais
< 2,
como desejávamos.
6.2.3 Indução e Problemas de Divisibilidade
Agora damos alguns exemplos de problemas de divisibilidade que podem
ser mostrados utilizando o método da indução:
Exemplo 6.8. Mostre que para qualquer n ∈ N, n3+2n é sempre divisível
por 3.
Solução. Para n = 1 a a�rmação é válida, pois 13+2·1 = 3, que obviamente
é divisível por 3.
Assumamos como hipótese indutiva que a a�rmação vale para algum
k ∈ N, isto é,
Hipótese: k3 + 2k é divisível por 3.
Devemos mostrar que a a�rmação também é verdadeira para k + 1, ou
seja, temos que provar que
Tese: (k + 1)3 + 2(k + 1) é divisível por 3.
Para provar isto último, usamos o fato de que
(k + 1)3 + 2(k + 1) = (k3 + 3k2 + 3k + 1) + (2k + 2);
6.2 Aplicações 213
agrupando adequadamente,
(k + 1)3 + 2(k + 1) = (k3 + 2k) + (3k2 + 3k + 3)
= (k3 + 2k)︸ ︷︷ ︸
múltiplo de 3
+3(k2 + k + 1)︸ ︷︷ ︸
múltiplo de 3
= múltiplo de 3,
concluindo assim a prova.
Exemplo 6.9. Mostre que a soma dos cubos de três números naturais con-
secutivos é divisível por 9.
Solução. De�namos a seguinte proposição:
p(n) : n3 + (n+ 1)3 + (n+ 2)3 é um múltiplo de nove.
Notemos que P (1) é válida, pois
13 + 23 + 33 = 1 + 8 + 27 = 36 = 9 · 4.
Precisamos provar agora o passo indutivo, isto é,
• Hipótese: P (k) é verdadeira para algum k ∈ N.
• Tese: P (k + 1) também é verdadeira.
Para provar isto, observamos que
(k+1)3 + (k+2)3 + (k+3)3 = (k+1)3 + (k+2)3 + (k3 +9k2 +27k+27).
Ordenando adequadamente, temos que o lado direito da última igualdade
se escreve como
k3 + (k + 1)3 + (k + 2)3 + (9k2 + 27k + 27)
= k3 + (k + 1)3 + (k + 2)3︸ ︷︷ ︸
múltiplo de 9
+9(k2 + 3k + 3)︸ ︷︷ ︸
múltiplo de 9
= múltiplo de 9,
completando assim nossa demonstração.
214 6 Indução Matemática
Muitas vezes, para conseguir mostrar que a hipótese p(n + 1) é verda-
deira, precisamos supor que p(k) é verdadeira para todo n0 ≤ k ≤ n. Isto
é a base do princípio forte da indução �nita que enunciamos a seguir:
Teorema 6.10 (Princípio Forte da Indução Finita). Considere n0 um in-
teiro não negativo. Suponhamos que, para cada inteiro n ≥ n0 seja dada
uma proposição p(n) e que valem as propriedades
(a) p(n0) é verdadeira;
(b) se para cada inteiro não negativo k, com n0 ≤ k ≤ n, temos que p(k)
é verdadeira, então p(n+ 1) é também verdadeira.
Então, a proposição p(n) é verdadeira para qualquer n ≥ n0.
Utilizando o princípio forte da indução, vamos dar uma prova diferente
do teorema fundamental da aritmética da apresentada no Capítulo 3.
Exemplo 6.11 (Teorema Fundamental da Aritmética). Todo número na-
tural N maior que 1 pode ser escrito como um produto
N = p1 · p2 · p3 · · · pm, (6.3)
onde m ≥ 1 é um número natural e os pi, 1 ≤ i ≤ m são números primos.
Além disso, a fatoração em (6.3) é única se exigirmos que p1 ≤ p2 ≤ · · · ≤
pm.
Solução. Para cada n ∈ N, n ≥ 2, de�namos a proposição
p(n) : n é escrito de modo único como um produto de números primos.
Notemos que p(2) é verdadeira, pois 2 é um número primo.
Agora enunciemos o passo indutivo:
• Hipótese indutiva: p(k) é verdade para cada inteiro k tal que 2 ≤ k ≤
n.
6.3 Indução na Geometria 215
• Tese: p(n+1) é verdade. Em outras palavras, temos que mostrar que
n+ 1 é escrito de modo único como um produto de números primos.
Faremos a prova dividindo em dois casos:
(a) Se n + 1 é um número primo, então p(n + 1) é verdade e isto acaba
nossa demonstração.
(b) Se n + 1 não é um número primo, então existem α, β ∈ N com 2 ≤
α ≤ n e 2 ≤ β ≤ n tais que n+ 1 = α · β.
Nossa hipótese indutiva é válida para α e β. Isto signi�ca que α se
escreve de modo único como um produto de números primos e que β
se escreve de modo único um produto de números primos. Portanto,
n+ 1 = α · β se escreve como um produto de números primos.
Agora mostraremos que n+1 se escreve de modo único como produto
de primos. Assuma que
p1p2 . . . pk = q1q2 . . . qm = n+ 1, (6.4)
com p1 ≤ p2 ≤ · · · ≤ pk e q1 ≤ q2 ≤ · · · ≤ qm todos primos. Vamos
mostrar que necessariamente k = m e pi = qi.
De fato, como p1 é primo, ele divide algum qi. Logo, como qi é primo,
p1 = qi ≥ q1. Analogamente, existe um j tal que q1 = pj ≥ p1. Logo,
p1 = q1. Cancelando p1 em ambos os lados da equação (6.4), temos
que (n + 1)/p1 = p2 . . . pk = q2 . . . qm ≤ n. Logo, por hipótese de
indução, k = m e p2 = q2, . . . , pm = qm, encerrando a demonstração.
6.3 Indução na Geometria
Tratamos aqui alguns exemplos que mostram a utilidade do método de
indução na resolução de problemas geométricos. Vamos começar estudando
216 6 InduçãoMatemática
duas propriedades importantes dos polígonos. A primeira delas trata da
soma dos ângulos internos de um polígono convexo de n lados (n-ágono).
Um polígono convexo é um polígono tal que qualquer segmento de reta
que liga dois de seus pontos está contido no interior dele. No caso de
polígonos, isto é equivalente ao fato de que todo segmento que liga dois
vértices ou é uma aresta ou está contido no interior do polígono.
Exemplo 6.12. Mostre que a soma dos ângulos internos de um polígono
convexo de n lados (n ≥ 3) é igual a (n− 2)π radianos.
Solução. No caso de n = 3 a propriedade acima é muito bem conhecida.
Desde Tales de Mileto e Euclides se conhecia que a soma dos ângulos internos
de um triângulo é π radianos. Façamos mais um caso, tomando n = 4. Neste
caso, podemos dividir um quadrilátero em dois triângulos, como mostra a
Figura 6.1 (a). Assim, a soma dos ângulos internos de um quadrilátero é
2π radianos.
A1 A2
A3
A4
(a) A1 A2A3
A4
A5 (b)
Figura 6.1: Dividindo polígonos
Para elucidar o processo de indução e não deixar dúvidas sobre o que
iremos fazer, vamos considerar mais um polígono, o pentágono (n = 5).
Neste caso, para mostrar que a soma dos seus ângulos internos é (5−2)π =
3π radianos, iremos dividir o pentágono A1A2A3A4A5 em um quadrilátero
A1A2A3A4 e um triângulo A1A4A5, como mostra a Figura 6.1 (b). Assim,
6.3 Indução na Geometria 217
a soma dos ângulos internos do pentágono A1A2A3A4A5 é igual à soma dos
ângulos internos do triângulo A1A4A5 (igual a π) mais a soma dos ângulos
internos do quadrilátero A1A2A3A4 (igual a 2π), ou seja, é igual a 3π.
Finalmente, vamos assumir como hipótese de indução que para um certo
n ≥ 3 mostramos que a soma dos ângulos internos do n-ágono é dada pela
expressão (n − 2)π. Precisamos mostrar que a soma dos ângulos internos
de um n + 1-ágono é [(n + 1) − 2]π = (n − 1)π. De fato, podemos repetir
o processo anterior. Vamos denominar de A1, A2, . . . , An, An+1 os vértices
consecutivos do (n+1)-ágono. Podemos dividi-lo no n-ágono A1A2 . . . An e
no triângulo A1An+1An. Logo, a soma dos ângulos internos do (n+1)-ágono
é (n− 2)π + π = (n− 1)π.
Exemplo 6.13. Mostre que o número de diagonais de um polígono convexo
de n-lados é igual a n(n−3)
2
.
Solução. Observe que para n = 3 temos que existem 0 = 3.(3 − 3)/2 dia-
gonais num triângulo. Para n = 4, temos 2 = 4(4 − 3)/2 diagonais num
quadrilátero convexo (veja a Figura 6.2).
Vamos agora assumir como hipótese de indução que se n é um n-
ágono convexo então o seu número de diagonais é n(n− 3)/2 e vamos pro-
var que a fórmula vale para um (n + 1)-ágono convexo. De fato, denote
por A1, A2, . . . , An, An+1 os vértices consecutivos do n + 1-ágono. Pode-
mos decompô-lo como a união do n-ágono A1, A2, . . . , An e do triângulo
A1, An, An+1. Neste caso, para contarmos as diagonais do (n + 1)-ágono
devemos considerar os seguintes casos:
• Diagonais do n-ágono A1, A2, . . . , An; por hipótese de indução, o nú-
mero dessas diagonais é n(n− 3)/2.
• n− 2 diagonais que partem do vértice An+1 mais a diagonal A1An.
Assim, o número total de diagonais do (n+ 1)-ágono é
n(n− 3)
2
+(n−2)+1 = n
2 − 3n+ 2n− 2
2
=
n2 − n− 2
2
=
(n+ 1)(n− 2)
2
,
218 6 Indução Matemática
como queríamos demonstrar.
A1 A2
A3
A4
(a) A1 A2A3
A4
A5 (b)
Figura 6.2: Diagonais de polígonos
Exemplo 6.14. Mostre que podemos cobrir os n2 pontos no reticulado a
seguir traçando 2n− 2 segmentos de reta sem tirar o lápis do papel.
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
︸ ︷︷ ︸
n×n−pontos
Figura 6.3: O problema de bar n× n
6.3 Indução na Geometria 219
Solução. O caso n = 3 já foi enunciado no Problema 1.12 do Capítulo 1. A
�gura a seguir mostra a solução, onde o caminho realizado com as 4 linhas
é o seguinte: A→ B → C → D → B.
• • •
• • •
• • •A
B
C
D
Figura 6.4: Solução do problema de bar 3× 3
Daremos a prova do problema acima por indução. Para isso, veja que
podemos resolver o caso n = 4 continuando a solução do caso n = 3. Como
paramos num dos vértices do quadrado 3×3, acrescentamos mais uma linha
e uma coluna para obter um reticulado 4×4. Assim, conseguimos cobrir os
16 pontos utilizando 4+ 2 = 6 linhas, sem tirar o lápis do papel e cobrindo
dois lados do quadrado, como mostram as linhas descontínuas na Figura
6.5.
• • •
• • •
• • •
•
•
•
••••
A
B
C
D
Figura 6.5: Completando o reticulado
220 6 Indução Matemática
Finalmente, vamos assumir como hipótese de indução que podemos co-
brir n ≥ 2 um reticulado n×n com 2n− 2 linhas, sendo que a última delas
cobre um dos lados do reticulado. Acrescentando 2n+1 pontos como mostra
a Figura 6.5, obtemos um reticulado (n+1)× (n+1) que pode ser coberto
com 2n− 2 + 2 = 2(n+ 1)− 2 pontos, como queríamos demonstrar.
6.4 Miscelânea
Nesta seção discutiremos alguns exemplos interessantes de como podemos
aplicar o método da indução aos mais variados tipos de problemas. O
primeiro deles é uma generalização do Problema 1.8.
Exemplo 6.15 (A Moeda Falsa). Um rei muito rico possui 3n moedas de
ouro. Porém, uma destas moedas é falsa e seu peso é menor que o peso das
demais. Com uma balança de 2 pratos e sem nenhum peso, mostre que é
possível encontrar a moeda falsa com apenas n pesagens.
Solução. Para resolver este problema, vamos utilizar o Método da Indução.
De fato, se n = 1, procederemos da seguinte forma: pegamos duas moedas
quaisquer e colocamos na balança, deixando uma do lado de fora. Caso a
balança se equilibre, a moeda que está do lado de fora é necessariamente a
que tem menor peso. Caso a balança se desequilibre, a que tem menor peso
está na balança, no prato mais alto. O caso n = 2 foi feito no Problema
1.8.
Vamos agora assumir como hipótese de indução que dadas 3n moedas,
podemos achar a moeda mais leve com n pesagens. Vamos mostrar que
para 3n+1 moedas, é su�ciente n + 1 pesagens. De fato, dividiremos as
3n+1 moedas em 3 grupos, A,B e C com 3n moedas cada. Colocamos na
balança os grupos A e B. Caso os dois grupos se equilibrem, a moeda mais
leve está no grupo C. Caso o grupo A esteja mais leve, a moeda mais leve se
encontra no grupo A. De qualquer modo, com uma pesagem conseguimos
6.4 Miscelânea 221
determinar em qual grupo de 3n elementos a moeda mais leve se encontra.
Por hipótese de indução, precisamos de mais n pesagens para encontrar a
moeda mais leve, totalizando n+1 pesagens. Desa�amos o leitor a mostrar
que não é possível realizar tal tarefa com menos de n pesagens.
Exemplo 6.16. Mostre que utilizando um balde com 5 litros de capacidade
e outro com 7 litros, é possível separar qualquer quantidade superior ou igual
a 24 litros.
Solução. Novamente, faremos a prova utilizando o Método da Indução.
Neste caso, começaremos o processo de indução a partir de 24. De fato,
podemos separar 24 litros utilizando duas vezes o balde de 7 e duas vezes o
balde de 5 litros. Note que o problema acima equivale a mostrar que
Todo número maior ou igual a 24 pode ser escrito da forma
7x + 5y, onde x e y são números inteiros maiores ou iguais a
zero.
Neste caso, escrevemos 24 como 24 = 2 · 7 + 2 · 5. Por hipótese de
indução, vamos supor que conseguimos escrever um número n ≥ 24 como
n = 7x+5y, com x e y números inteiros maiores ou iguais a zero. Devemos
mostrar que n+ 1 se escreve deste modo também. Para isso, vamos dividir
a análise em dois casos:
Caso 1: y ≤ 3
Logo, x ≥ 2 pois se isso não ocorresse, teríamos 7x + 5y ≤ 22 < 24, o
que é impossível. Assim, podemos escrever:
n+ 1 = 7x+ 5y + 1 = 7(x− 2) + 5(y + 3),
pois x− 2 ≥ 0.
Caso 2: y ≥ 4
222 6 Indução Matemática
Neste caso, y − 4 ≥ 0. Logo, podemos escrever:
n+ 1 = 7x+ 5y + 1 = 7(x+ 3) + 5(y − 4),
�nalizando a nossa prova por indução.
6.4.1 Cuidados ao Usar o Princípio da Indução
Observação 6.17. Quando aplicamos o princípio da indução devemos to-
mar certos cuidados. A seguir damos um exemplo de como o método pode
ser aplicado de forma errada. Vamos mostrar a seguinte a�rmação:
A�rmação: Num conjuntoqualquer de n bolas, todas as bolas
possuem a mesma cor.
Observe que nossa proposição é claramente falsa. Mas, mesmo assim, vamos
dar uma prova por indução.
Para n = 1, nossa proposição é verdadeira pois em qualquer conjunto
com uma bola, todas as bolas têm a mesma cor, pois só existe uma bola. As-
suma por hipótese de indução que a proposição é verdadeira para n e prove-
mos que a proposição é verdadeira para n+1. Ora, seja A = {b1, . . . , bn, bn+1}
o conjunto com n + 1 bolas referido. Considere os subconjuntos de B e C
de A com n elementos, construídos como:
B = {b1, b2, . . . , bn} e C = {b2, . . . , bn+1}
Observe que ambos os conjuntos têm n elementos. Assim, as bolas
b1, b2, . . . , bn do conjunto B têm a mesma cor. Do mesmo modo, as bo-
las do conjunto C têm a mesma cor. Em particular, a bola bn tem a mesma
cor da bola bn+1. Assim, todas as bolas têm a mesma cor. Ache o erro no
argumento! Se você não conseguir, leia a nota de rodapé. 1
1Uma dica da solução encontra-se no �nal do capítulo.
6.5 Indução e Recorrências 223
6.5 Indução e Recorrências
Vamos começar esta seção discutindo um problema muito conhecido e inte-
ressante.
Exemplo 6.18 (As Torres de Hanói2). Diz uma antiga lenda que na origem
dos tempos, em um templo de Hanói, foram colocados 64 discos perfurados
de ouro puro e de diâmetros diferentes ao redor de uma de três hastes de
diamante. Muitos sacerdotes moviam os discos, respeitando as seguintes
regras: eles começam empilhados em ordem crescente de acordo com seu
tamanho (ver Figura 6.6). Os discos podem ser deslocados de uma coluna
para qualquer outra, sendo que nunca pode ser colocado um disco maior em
cima de um menor e a cada segundo os sacerdotes movem um disco.
Quando os sacerdotes transportassem todos os discos de uma coluna para
outra, o mundo se acabaria. Suponha que eles começaram esse processo no
ano 2000 e que a lenda é verdadeira, quanto tempo ainda resta para a Terra?
Figura 6.6: Torre de Hanói
Para responder esse problema, consideraremos o problema geral de des-
cobrir quantos movimentos são necessários para mover n anéis de uma haste
para outra. Argumentaremos do seguinte modo: observe que podemos mover
os discos para outra haste se n = 1 ou 2. Com efeito, se temos somente um
anel basta mover este para qualquer outra haste com um único movimento.
2Este jogo foi inventado, em 1882, pelo matemático Francês Édouard Lucas.
224 6 Indução Matemática
Se temos 2 anéis então movemos o menor deles para a segunda haste, o
maior para a terceira haste e, �nalmente, o menor para a terceira haste,
realizando um total de 3 movimentos. Para calcular o caso geral, vamos
empregar um método chamado de método recursivo: o número ak+1 de mo-
vimentos necessários para mover k+1 anéis será expresso como uma função
de ak.
De fato, se temos k+1 anéis na primeira haste e sabemos mover k anéis
de uma haste para outra utilizando ak movimentos, então podemos mover
todos os k + 1 anéis para a segunda haste usando 2ak + 1 movimentos.
De fato, movemos todos eles, exceto o maior, para a terceira haste usando
ak movimentos. A seguir, colocamos o maior na segunda haste usando 1
movimento. Imediatamente, deslocamos todos os anéis da terceira haste
para a segunda haste usando mais ak movimentos. Logo, movemos todos os
k + 1 anéis utilizando 2ak + 1 movimentos. Em resumo:
ak+1 = 2ak + 1, (6.5)
onde ak é o número de movimentos necessários para mover k discos de uma
haste para outra. Vamos agora usar indução para provar que ak = 2k − 1.
Uma vez constatada a veracidade da a�rmação para k = 1, 2, para
calcular ak, por hipótese de indução, vamos assumir que ak = 2k−1. Temos
pela equação (6.5):
ak+1 = 2ak + 1 = 2(2
k − 1)− 1 = 2k+1 − 1.
como queríamos demonstrar.
Vamos aproveitar o Exemplo 6.18 para discutir algumas equações que
aparecem em muitas situações em Matemática: as equações de recorrência.
Em geral, uma equação de recorrência é uma equação envolvendo uma
certa quantidade de termos de sequência xn. Para ilustrar isso, observe
a equação (6.5). Aqui, estaremos interessados em um tipo particular de
equação de recorrência, as equações de recorrência lineares.
6.5 Indução e Recorrências 225
De�nição 6.19. Uma equação de recorrência linear de grau k é uma ex-
pressão da forma:
xn+1 =rk−1xn + rk−2xn−1 + · · ·+ r0xn−k+1
x1 = a1, x2 = a2, . . . , xk = ak,
(6.6)
onde r0, r1, . . . , rk−1 são números reais e r0 6= 0.
Por exemplo, são equações de recorrência lineares as seguintes equações
2xn − 3xn+1 = 0 e − 3xn +
2
3
xn+1 = 5xn+2
e não são equações de recorrência lineares as equações
2(xn)
3 − 5xn+1 = 0 e − 3xn +
2
3
xn+1 = 5xn+2 + 3.
Exemplo 6.20 (Sequência de Fibonacci). Um exemplo muito interessante
de equação de recorrência é a sequência conhecida por sequência de Fibo-
nacci, devido ao matemático italiano Leonardo di Pisa (1170-1250). Esta
sequência adquiriu muita fama devido a suas conexões com áreas das mais
variadas na cultura humana. Ela aparece em problemas de Biologia, Ar-
quitetura, Engenharia, Física, Química e muitos outras áreas da ciência e
arte.
De�nimos a sequência de Fibonacci como sendo a sequência Fn que
satisfaz a seguinte equação de recorrência:
F1 = 1;
F2 = 1;
Fn = Fn−1 + Fn−2, se n ≥ 3.
Agora vamos utilizar indução para mostrar algumas de suas proprieda-
des.
226 6 Indução Matemática
Exemplo 6.21. Considere Fn a sequência de Fibonacci. Mostre que
Fn <
(
7
4
)n
.
Solução. De�namos a proposição p(n) := Fn <
(
7
4
)n
. Para n = 1 temos
que F1 = 1 < 74 , de modo que p(1) é verdadeira. Suponhamos que
p(1), p(2), . . . , p(n),∀n ≥ 2,
sejam todas verdadeiras. Mostraremos que Fn+1 <
(
7
4
)n+1
. Com efeito,
Fn+1 = Fn + Fn−1 <
(
7
4
)n
+
(
7
4
)n−1
< 74
(
7
4
)n−1
+
(
7
4
)n−1
<
(
1 + 74
) (
7
4
)n−1
.
Como
(
1 + 74
)
<
(
7
4
)2
, segue-se que Fn+1 <
(
7
4
)2 (7
4
)n−1
. Portanto,
Fn+1 <
(
7
4
)n+1
.
Exemplo 6.22. Dada a seguinte relação de recorrência
a0 = 8;
a1 = 10;
an = 4an−1 − 3an−2, ∀n ≥ 2.
Mostre que an = 7 + 3n, para todo n ∈ Z+.
Solução. De�namos a proposição P (n) : an = 7 + 3n. P (0) é verdadeira,
pois P (0) = 7 + 30 = 7 + 1 = 8. Suponhamos que P (k) é verdadeiro para
cada inteiro k tal que 1 ≤ k ≤ n. Vamos mostrar que P (k) é verdade para
6.5 Indução e Recorrências 227
k = n+ 1. Com efeito,
an+1 = 4an − 3an−1
= 4(7 + 3n)− 3(7 + 3n−1)
= 7 + 4× 3n − 3× 3n−1
= 7 + 3n−1
(
4× 3− 3
)
= 7 + 3n−1
(
9
)
= 7 + 3n−1 × 32
= 7 + 3n+1.
Vamos agora discutir o caso geral da equação de recorrência linear (6.6).
Para isso, vamos fazer algumas observações preliminares que deixaremos a
cargo do leitor:
• se an e bn são soluções da equação (6.6), então an + bn também é
solução;
• se an é solução da equação (6.6) e α é um número real, então αan
também é solução.
Com isto em mente, vamos descrever agora como obter todas as soluções
xn da equação (6.6) em função de n. Observe que dados os termos iniciais
a1, a2, . . . , ak a sequencia xn �ca inteiramente determinada pela equação de
recorrência. O interessante aqui é determinar o termo xn+1 sem que seja
preciso o cálculo dos termos xn, xn−1, . . . , xn−k+1.
Vamos primeiro procurar o que se chama de solução particular da equa-
ção (6.6). Particular porque ela assume uma forma característica e porque
não assumiremos que as condições x1 = a1, . . . , xk = ak valham.
Vamos procurar soluções do tipo xn = λn, onde λ é um número real
positivo. Neste caso, temos que:
λn+1 = xn+1 =rk−1xn + rk−2xn−1 + · · ·+ r0xn−k+1
= rk−1λ
n + rk−2λ
n−1 + · · ·+ r0λn−k+1.
228 6 Indução Matemática
Passando os termos do lado direito da igualdade e colocando em evi-
dência o termo λn−k+1 temos:
λn−k+1
(
λk − rk−1λk−1 − rk−2λk−2 − · · · − r0
)
= 0. (6.7)
Assim, como λk 6= 0, pois λ > 0, temos que
λk − rk−1λk−1 − rk−2λk−2 − · · · − r0 = 0. (6.8)
O polinômio
p(λ) = λk − rk−1λk−1 − rk−2λk−2 − · · · − r0
recebe o nome especial de polinômio característico da equação de recorrên-
cia (6.6). Acabamos de mostrar que qualquer