em Matemática em Rede Nacional - PROFMATmoodle.profmat-sbm.org.br/MA21/OLD/unidade3.pdf5 Contagem da o T vez que puder, onte. c ancis r F Galton Neste capítulo discutiremos problemas

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 GaltonNeste 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 deniçõ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 denido

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 signica 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),

signicando 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, denimos 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 ∪ · · · ∪ Anconté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).


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 denir 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.


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.

Denição 5.6. Denimos 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


Neste caso é fácil vericar 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 ⊂ Upodemos 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∣∣∣∣∣ = |Ac1Ac2 · · ·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. Denamos 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.


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. Denamos 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 denamos 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


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, onú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. Dena o conjunto

A1 =todos os divisores de n que são da forma pm11 , onde m ∈ Z+,

e em geral, dena

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

1i , p

2i , . . . , p

kii

, para i = 1, 2, 3, . . . , ki.

É imediato ver que∣∣Ai∣∣ = ki + 1.


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 denir 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. Denamos 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αAcβ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

Denimos 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

Deniçã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 denamos 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) signica 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

Deniçã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 Apno 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 = Ann = 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 = nAp−1n−1. (5.6)

Agora denimos 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 signicado. 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| = A25 = 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ígitos do 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| = A2

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| = A2

5 = 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.

Deniçã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(np

)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(np

)= 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(ni

), 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(52

)= 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(n3

)= 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(62

)= 6!

4! 2!.

• Agora dividiremos as 4 pessoas restantes em um grupo de 2 e

outro grupo de 2; esta quantidade vem dada por(42

)= 4!

2! 2!.

Pelo princípio multiplicativo temos que existem(62

)(42

)= 6!

(2!)3possi-

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(102

)formas

diferentes.

192 5 Contagem

• Depois, vamos encontrar a quantidade de maneiras pelas quais

você pode jantar com 3 amigos; isto é feito de(103

)formas dife-

rentes.

• Em seguida, encontramos a quantidade de maneiras pelas quais

você pode jantar com 4 amigos; isto é feito de(104

)formas dife-

rentes.

• Em geral, o número de maneiras diferentes que você tem de

jantar com p amigos é dado por(10p

).

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(41

)(64

)= 60 comissões de 5 pessoas.

• Nosso grupo é composto por 2 mulheres e 3 homens; neste caso

poderemos formar(42

)(63


5.7 O Binômio de Newton 193

• Nosso grupo é composto por 3 mulheres e 2 homens; neste caso

poderemos formar(43

)(62


• Nosso grupo é composto por 4 mulheres e um homem; neste caso

poderemos formar(44

)(61


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 vericar:

(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úmerosreais 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(ni

), 0 ≤ i ≤ n, são chamados também de coecientes 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 coeciente 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(ni

). 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 coecientes binomiais que resumimos na próxima proposi-

ção.

Proposição 5.36. Seja n ∈ N. As seguintes igualdades são válidas:

(a)(n0

)+(n1

)+ · · ·+

(ni

)+ · · ·+

(nn−1)

+(nn

)= 2n;

(b)(n0

)−(n1

)+ · · ·+ (−1)i

(ni

)+ · · ·+ (−1)n

(nn

)= 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.

Denimos 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 diculdade 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 menosduas bolas com o mesmo número. Para isso é mais fácil contar quantasescolhas 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 de365 elementos. Assim, concluímos que a probabilidade de que esteevento ocorra é

p =36544 −A44

365

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 quantosmodos é 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?


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 ao cinema 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 congurações do tabuleiro com duas

torres que não se atacam, como no Exemplo 5.2, sem distinguir

as torres, quantas conguraçõ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

∣∣.


Usando os princípios estudados, mostre que se n se decompõe

em fatores primos como n = p1α1p2α2 . . . pαkk , 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 NeumannImagine uma la com innitos 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 vericarmos 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 armaçã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 vericar 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 armaçã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. Denamos 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 denição de m0.

Portanto, o conjunto F é vazio, concluindo-se assim a prova.


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 innita de armações são

verdadeiras, simplesmente vericando que uma quantidade nita des-

tas armaçõ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) = n2. 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 vericar 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. Denamos 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:


• 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 arma que p(k + 1) também é verdadeira. O

Princípio de Indução nos garante que p(n) é verdadeira para qualquer

n ∈ N.

Exemplo 6.4. Demonstre que para qualquer n ∈ N é válida a igual-

dade:

1 + 3 + 5 + · · ·+ 2n− 1 = n2.

Solução. Aqui denimos 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.


• 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 = 12 + 22 + 32 + · · ·+ n2.

Para induzir a fórmula, consideramos os valores de sn e qn numa tabela:


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, seconsiderarmos 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

qnsn

=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 < 2n2para todo n ∈ N.

Solução. Denotamos por p(n) a propriedade: 3n−1 < 2n2. É 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.


Exemplo 6.6. Mostre que para todo número n ∈ N, n > 3, vale que 2n < n!

Demonstração. Para n = 4 a desigualdade é vericada, 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


< 2.

Logo, adicionando 2 em ambos os lados desta desigualdade tem-se

2 +

√

2 +

√2 +

√2 + · · ·+

√2


< 2 + 2.


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 armação é válida, pois 13+2·1 = 3, que obviamente

é divisível por 3.

Assumamos como hipótese indutiva que a armação vale para algum

k ∈ N, isto é,

Hipótese: k3 + 2k é divisível por 3.

Devemos mostrar que a armaçã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);


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. Denamos 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.


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, denamos 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 signica 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


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 A2

A3

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,


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 =

n2 − 3n+ 2n− 2

2=n2 − n− 2

2=

(n+ 1)(n− 2)

2,



A1 A2

A3

A4

(a) A1 A2

A3

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


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


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, é suciente 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. Desaamos 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


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 armação:

Armação: Num conjunto qualquer 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+1o 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.


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 armaçã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(2k − 1)− 1 = 2k+1 − 1.


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.


Deniçã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

3xn+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

3xn+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.

Denimos 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.


Exemplo 6.21. Considere Fn a sequência de Fibonacci. Mostre que

Fn <

(7

4

)n.

Solução. Denamos a proposição p(n) := Fn <(74

)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 <(74

)n+1. Com efeito,

Fn+1 = Fn + Fn−1 <(74

)n+(74

)n−1

< 74

(74

)n−1+(74

)n−1

<(1 + 7

4

) (74

)n−1.

Como(1 + 7

4

)<(74

)2, segue-se que Fn+1 <

(74

)2 (74

)n−1. Portanto,

Fn+1 <(74

)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. Denamos 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


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 αantambé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.


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 raiz do polinômio caracterís-

tico gera uma solução particular da equação (6.6).

Vamos assumir que a equação (6.8) possui k raízes diferentes, digamos

λ1 > λ2 > · · · > λk. Então vale o seguinte teorema:

Teorema 6.23. Se escolhermos números reais c1, c2, . . . , ck, então

xn = c1λn1 + c2λ

n2 + · · ·+ ckλ

nk (6.9)

é uma solução da equação de recorrência, onde os termos iniciais ai para

i = 1, 2, . . . , k são:

ai = c1λi1 + c2λ

i2 + · · ·+ ckλ

ik.

Demonstração. Para mostrar o teorema, como x1 = a1, . . .xk = ak pela

denição dos ai's, basta mostrar que xn é uma solução.

Ora, o produto de uma solução por um número real também é uma

solução. Assim, como λni é uma solução para i = 1, 2, . . . , k e ci é um

6.6 Exercícios 229

número real, temos que ciλni é solução para i = 1, 2, . . . , k. Como já vimos

acima, a soma de soluções é também uma solução. Logo,

xn = c1λn1 + c2λ

n2 + · · ·+ ckλ

nk

é uma solução.

Neste ponto, voltamos a equação (6.6). Desde o princípio, dados os

números ai buscávamos a solução xn tal que x1 = a1, . . . , xk = ak. A

Equação (6.9) nos dá uma variedade de soluções, onde podemos escolher

os números ci como bem entendermos. Usando equações lineares, podemos

mostrar que sempre é possível escolher os números ci de modo que x1 =

a1, . . . , xk = ak. Isso encerra nossa busca. Para complementar esta seção,

recomendamos a leitura do Capítulo 3 de [4].

6.6 Exercícios

1. Se qn denota a soma qn = 12 + 22 + · · · + n2, prove que para todo

n ∈ Nqn =

n(n+ 1)(2n+ 1)

6.

2. Use o princípio da indução para provar as seguintes armações:

(a) 3n+1 + 2n+2 é divisível por 7 para todo n ∈ N;

(b) a soma dos cubos de três números naturais consecutivos é divi-

sível por 9;

(c) 7 + 77 + 777 + · · ·+ 777 . . . 7︸︷︷︸n−vezes

= 7(10n+1 − 9n− 10)/81;

(d) (n+ 1)(n+ 2) . . . (n+ n) = 2n · 1 · 3 · 5 · · · (2n− 1).

3. Use o princípio da indução para provar as seguintes desigualdades:


(a) 2n−1(an + bn) > (a + b)n, ∀n ∈ N, com a, b ∈ R, a + b > 0 e

a 6= b;

(b)1√1+

1√2+

1√3+ · · ·+ 1√

n>√n, para todo n ∈ N;

(c)1

n+ 1+

1

n+ 2+

1

n+ 3+ · · ·+ 1

2n>

13

24, para todo n ∈ N.

4. Mostre a seguinte identidade trigonométrica

cosx+2 cos 2x+ · · ·+n cosnx =(n+ 1) cosnx− n cos(n+ 1)x− 1

4 sin2 x2.

5. Um torneio de xadrez tem n jogadores. Cada jogador joga uma única

partida com cada um dos outros jogadores. Calcule o número total

de partidas realizadas no torneio.

6. Demonstre que para qualquer n ∈ N é válida a igualdade

13 + 23 + 33 + · · ·+ n3 =

[n(n+ 1)

2

]2.

7. Demonstre que para qualquer n ∈ N é valida desigualdade

an =

(1 +

1

n

)n< 3.

8. Prove que, para todo n ∈ N e a > 0,√

a+

√a+

√a+ · · ·+√a


<1 +√4a+ 1

2.

9. Mostre que para qualquer número natural n ≥ 0, 11n+2 + 122n+1 é

sempre divisível por 133.

10. Mostre que para todo n ∈ Z+ temos que 32n+1 +2n+2 é um múltiplo

de 7.

6.6 Exercícios 231

11. Mostre que para todo n ∈ Z+ temos que 32n+2+26n+1 é um múltiplo

de 11.

12. Considere Fn a sequência de Fibonacci . Mostre que

Fn =1√5

(1 +√5

2

)n− 1√

5

(1−√5

2

)n.

13. Mostre as seguintes propriedades a respeito da sequência de Fibonacci

Fn:

(a)n∑

i=1

Fi = Fn+2 − 1; (b)n∑

i=1

F2i−1 = F2n;

(c)n∑

i=1

F2i = F2n+1 − 1; (d) Fn−1Fn+1 − F 2n = (−1)n.

14. De quantas formas diferentes podemos cobrir um tabuleiro de 2 ×n com peças de dominós que cobrem exatamente duas celas do ta-

buleiro?

15. Calcular o número de regiões em que o plano é dividido por n retas

distintas em cada uma das seguintes situações:

(a) as n retas são concorrentes;

(b) não existem duas retas paralelas nem três retas concorrentes.3

16. Dizemos que uma gura é enquadrável com régua e compasso, se a

partir dela é possível, utilizando apenas régua e compasso, construir

um quadrado de mesma área. Prove que:

3Até onde sabemos, este problema é conhecido como a pizza de Steiner, o qual

foi resolvido, em 1826, pelo notável geômetra Jacob Steiner (1796-1863).


(a) um triângulo é sempre enquadrável;

(b) um polígono qualquer é enquadrável.

Sugestão para o item (b): Utilize indução dividindo a gura em tri-

ângulos.

17. Dê uma resposta à situação á Observação 6.17.

Sugestão: Observe a validade do argumento quando o conjunto A tem

2 elementos. Veja que B e C não se intersectam. Ou seja, o passo

indutivo falha de n = 1 para n = 2.

Referências Bibliográcas

[1] AIGNER, M. e ZIEGLER, G. (2002). As Provas estão no

Livro. Edgard Blücher.

[2] GARCIA, A. e LEQUAIN, I. (2003). Elementos de Álgebra.

Projeto Euclides, IMPA.

[3] LIMA, E. L.; CARVALHO, P. C. P.; WAGNER, E. e MOR-

GADO, A.C. (2004). A Matemática do Ensino Médio. Volume

1. Sociedade Brasileira de Matemática.

[4] LIMA, E.L.; CARVALHO, P. C. P.; WAGNER, E. e MOR-

GADO, A.C. (2004). A Matemática do Ensino Médio. Volume


[5] LIMA,E.L.; CARVALHO,P. C. P.; WAGNER,E. e MOR-

GADO,A.C. (2004). A Matemática do Ensino Médio. Volume


[6] LIMA, E.L.; CARVALHO, P. C. P.; WAGNER,E. e MOR-

GADO, A.C. (2001). Temas e Problemas. Sociedade Brasileira

de Matemática.

[7] LIMA, E.L. (2001). Álgebra Linear. Sociedade Brasileira de

Matemática.

285

286 REFERÊNCIAS BIBLIOGRÁFICAS

[8] MORAIS FILHO, D. C. (2007). Um Convite à Matemática.

EDUFCG.

[9] MORGADO, A.; CARVALHO, J.; CARVALHO, P.; FER-

NANDEZ, P. (1991). Análise Combinatória e Probabilidade .

Sociedade Brasileira de Matemática.

[10] RIBENBOIM, P. (2001). Números Primos: Mistérios e Re-

cordes. Sociedade Brasileira de Matemática.

[11] SANTOS, J. P. O. (1993) Introdução à Teoria dos Números.

IMPA.

[12] SANTOS, J. P. O.; MELLO, M. P. e MURARI, I. T. C.

(2006). Introdução à Análise Combinatória. Editora Unicamp.

[13] SOARES, M. G. (2005). Cálculo em uma Variável Complexa.

Sociedade Brasileira de Matemática.

Documents

em Matemática em Rede Nacional - PROFMATmoodle.profmat-sbm.org.br/MA21/OLD/unidade3.pdf5 Contagem da o T vez que puder, onte. c ancis r F Galton Neste capítulo discutiremos problemas