MA12 Matemática Discreta 2012

Prévia do material em texto

1
1
Números Naturais
Sumário
1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 O Conjunto dos Números Naturais . . . . . . . . . . 3
1.3 O Axioma da Indução . . . . . . . . . . . . . . . . . 4
1.4 As Duas Operações: Adição e Multiplicação . . . . 5
1.5 A Ordenação nos Números Naturais . . . . . . . . . 6
1.6 Exercícios Recomendados . . . . . . . . . . . . . . . 8
1.7 Textos Complementares . . . . . . . . . . . . . . . . 10
1.1 Introdução
�Deus criou os números naturais. O resto é obra dos homens.�
Leopold Kronecker
Enquanto os conjuntos constituem um meio auxiliar, os números são um dos dois
objetos principais de que se ocupa a Matemática. O outro objeto é o espaço,
juntamente com as �guras geométricas nele contidas. Os números são objetos
abstratos que foram desenvolvidos pelo homem para servir como modelos que
permitem contar e medir e, portanto avaliar as diferentes quantidades de uma
grandeza.
Os compêndios tradicionais dizem o seguinte:
�Número é o resultado da comparação entre uma grandeza e a unidade. Se
a grandeza é discreta, essa comparação chama-se uma contagem e o resultado
é um número inteiro; se a grandeza é contínua, a comparação chama-se uma
medição e o resultado é um número real.�
Nos padrões atuais de rigor matemático, o trecho acima não pode ser consi-
derado como uma de�nição matemática, pois faz uso de idéias (como grandeza,
unidade, discreta, contínua) e processos (como comparação) de signi�cado não
estabelecido. Entretanto, todas as palavras que nela aparecem possuem um
sentido bastante claro na linguagem do dia-a-dia. Por isso, embora não sirva
para demonstrar teoremas a partir dela, a de�nição tradicional tem o grande
mérito de nos revelar para que servem e por qual motivo foram inventados os
números. Isto é muito mais do que se pode dizer sobre a de�nição que encon-
tramos no nosso dicionário mais conhecido e festejado, conforme reproduzimos
a seguir.
Número. [Do lat. numeru.] S.m. 1. Mat. O conjunto de todos os conjuntos
equivalentes a um conjunto dado.
Discutiremos este ponto logo mais, quando tratarmos de números cardinais.
+ Para Saber Mais - Comentários sobre De�nições e axiomas - Cli-
que para ler
Unidade 1Números Naturais
+ Na Sala de Aula - Re�exões sobre a sala de aula - Clique para ler
1.2 O Conjunto dos Números Naturais
Lentamente, à medida em que se civilizava, a humanidade apoderou-se desse
modelo abstrato de contagem (um, dois, três, quatro, ...) que são os números
naturais. Foi uma evolução demorada. As tribos mais rudimentares contam
apenas um, dois, muitos. A língua inglesa ainda guarda um resquício desse
estágio na palavra thrice, que tanto pode signi�car �três vezes� como �muito�
ou �extremamente�.
As necessidades provocadas por um sistema social cada vez mais complexo
e as longas re�exçõs, possíveis graças à disponibilidade de tempo trazida pelo
progresso econômico, conduziram, através dos séculos, ao aperfeiçoamento do
extraordinário instrumento de avaliação que é o conjunto dos números naturais.
Decorridos muitos milênios, podemos hoje descrever concisa e precisamente
o conjunto N dos números naturais, valendo-nos da notável síntese feita pelo
matemático italiano Giuseppe Peano no limiar do século 20.
N é um conjunto, cujos elementos são chamados números naturais. A
essência da caracterização de N reside na palavra �sucessor�. Intuitivamente,
quando n, n′ ∈ N, dizer que n′ é o sucessor de n signi�ca que n′ vem logo depois
de n, não havendo outros números naturais entre n e n′. Evidentemente, esta
explicação apenas substitui �sucessor� por �logo depois�, portanto não é uma
de�nição. O termo primitivo �sucessor� não é de�nido explicitamente. Seu uso
e suas propriedades são regidos por algumas regras, abaixo enumeradas:
a) Todo número natural tem um único sucessor;
b) Números naturais diferentes têm sucessores diferentes;
c) Existe um único número natural, chamado um e representado pelo símbolo
1, que não é sucessor de nenhum outro;
d) Seja X um conjunto de números naturais (isto é, X ⊂ N). Se 1 ∈ X e se,
além disso, o sucessor de todo elemento de X ainda pertence a X, então
X = N.
3
Unidade 1 O Axioma da Indução
As a�rmações (a), (b), (c) e (d) acima são conhecidas como os axiomas de
Peano. Tudo o que se sabe sobre os números naturais pode ser demonstrado
como consequência desses axiomas.
+ Para Saber Mais - Sobre o sistema de numeração - Clique para ler
+ Para Saber Mais - Um comentário gramatical - Clique para ler
+ Na Sala de Aula - Uma recomendação - Clique para ler
1.3 O Axioma da Indução
O último dos axiomas de Peano é conhecido como o axioma da indução. Ele
é a base de um e�ciente método de demonstração de proposições referentes a
números naturais (demonstrações por indução, ou por recorrência). Enunciado
sob a forma de propriedades em vez de conjuntos, ele se formula assim:
Seja P (n) uma propriedade relativa ao número natural n. Suponhamos que
i) P (1) é válida;
ii) Para todo n ∈ N, a validez de P (n) implica a validez de P (n′), onde n′ é o
sucessor de n.
Então P (n) é válida qualquer que seja o número natural n.
Com efeito, se chamarmos de X o conjunto dos números naturais n para
os quais P (n) é válida, veremos que:
1 ∈ X em virtude de (i); e que
n ∈ X ⇒ n′ ∈ X em virtude de (ii).
Logo, pelo axioma da indução, concluímos que X = N.
Definição 1 Esta formulação do Axioma da Indução é chamada de Princípio de Indução
Matemática
4
Unidade 1Números Naturais
+ Para Saber Mais - Cuidado! - Clique para ler
1.4 As Duas Operações: Adição e Multipli-
cação
Entre os números naturais estão de�nidas duas operações fundamentais:
a adição, que aos números n, p ∈ N faz corresponder a soma n + p e a
multiplicação, que lhes associa o produto np.
A soma n + p é o número natural que se obtém a partir de n aplicando-se
p vezes seguidas a operação de tomar o sucessor. Em particular, n + 1 é o
sucessor de n, n + 2 é o sucessor do sucessor de n, etc. Por exemplo, tem-se
2 + 2 = 4 simplesmente porque 4 é o sucessor do sucessor de 2.
De agora em diante, o sucessor do número natural n será designado por
n+ 1.
Quanto ao produto, põe-se n · 1 = n por de�nição e, quando p 6= 1, np é a
soma de p parcelas iguais a n.
Em última análise, a soma n+ p e o produto np têm mesmo os signi�cados
que lhes são atribuídos pelas explicações dadas acima. Entretanto, até que
saibamos utilizar os números naturais para efetuar contagens, não tem sentido
falar em �p vezes� e �p parcelas�. Por isso, as operações fundamentais devem
ser de�nidas por indução, como se segue.
Adição: n + 1 = sucessor de n e n + (p + 1) = (n + p) + 1 . Esta última
igualdade diz que se sabemos somar p a todos os números naturais n, sabemos
também somar p+1: a soma n+(p+1) é simplesmente o sucessor (n+p)+1
de n + p . O axioma da indução garante que a soma n + p está de�nida para
quaisquer n, p ∈ N.
Multiplicação: n·1 = n e n(p+1) = np+n. Ou seja: multiplicar um número
n por 1 não o altera. E se sabemos multiplicar todos os números naturais n por
p, sabemos também multiplicá-los por p+1: basta tomar n(p+1) = np+n. Por
indução, sabemos multiplicar todo n por qualquer p. Estas operações gozam das
conhecidas propriedades de associatividade, comutatividade e distributividade.
As demonstrações são feitas por indução. (Voltaremos ao assunto na Unidade
5 de MA12, onde mais detalhes serão apresentados.)
5
Unidade 1 A Ordenação nos Números Naturais
1.5 A Ordenação nos Números Naturais
Nossa breve descrição do conjunto N dos números naturais termina com a
relação de ordem m < n.
Dados m, n ∈ N, diz-se que m é menor do que n, e escreve-se m < n,
para signi�car que existe algum p ∈ N tal que n = m + p. (Isto quer dizer
que n é o sucessor do sucessor... do sucessor de m, o ato de tomar o sucessor
sendo iterado p vezes.)
A relação m < n tem as seguintes propriedades:
Transitividade: Se m < n e n < p então m < p.
Tricotomia: Dados m, n ∈ N, vale uma, e somente uma, das alternativas:m = n, m < n ou n < m.
Monotonicidade: Se m < n então, para qualquer p ∈ N, tem-se m+p < n+p
e mp < np.
Boa-ordenação: Todo subconjunto não-vazio X ⊂ N possui um menor ele-
mento. Isto signi�ca que existe um elemento m0 ∈ X que é menor do que
todos os demais elementos de X. A boa-ordenação pode muitas vezes
substituir com vantagem a indução como método de prova de resultados
referentes a números naturais.
São muito raros e pouco interessantes os exemplos de demonstração por
indução que podem ser dados sem usar as operações fundamentais e as desi-
gualdades. Por isso, somente agora apresentamos um deles, seguido de uma
demonstração por boa-ordenação.
Exemplo 1. Queremos provar a validez, para todo número natural n, da
igualdade
P (n) : 1 + 3 + 5 + . . .+ (2n− 1) = n2
Usaremos indução. Para n = 1, P (1) se resume a a�rmar que 1 = 1. Supondo
P (n) verdadeira para um certo valor de n, somamos 2n+1 a ambos os membros
da igualdade acima, obtendo
1 + 3 + 5 + . . .+ (2n− 1) + (2n+ 1) = n2 + 2n+ 1,
6
Unidade 1Números Naturais
ou seja:
1 + 3 + 5 + . . .+ [2(n+ 1)− 1] = (n+ 1)2.
Mas esta última igualdade é P (n+1). Logo P (n) ⇒ P (n+1). Assim, P (n)
vale para todo n ∈ N. Podemos então a�rmar que a soma dos n primeiros
números ímpares é igual ao quadrado de n.
Exemplo 2. (Usando boa-ordenação.) Lembremos que um número natural
p chama-se primo quando não pode ser expresso como produto p = mn de dois
números naturais, a menos que um deles seja igual a 1 (e o outro igual a p);
isto equivale a dizer que os fatores m, n não podem ser ambos menores do que
p. Um resultado fundamental em Aritmética diz que todo número natural é
primo ou é um produto de fatores primos. Provaremos isto por boa ordenação.
Usaremos a linguagem de conjuntos. Seja X o conjunto dos números naturais
que são primos ou produtos de fatores primos. Observemos que se m e n
pertencem a X então o produto mn pertence a X. Seja Y o complementar
de X. Assim, Y é o conjunto dos números naturais que não são primos nem
são produtos de fatores primos. Queremos provar que Y é vazio. Isto será
feito por redução ao absurdo (como sempre se dá nas demonstrações por boa-
ordenação). Com efeito, se Y não fosse vazio, haveria um menor elemento
a ∈ Y . Então todos os números menores do que a pertenceriam a X. Como a
não é primo, ter-se-ia a = m · n, com m < a e n < a, logo m ∈ X e n ∈ X.
Sendo assim, mn ∈ X. Mas mn = a, o que daria a ∈ X, uma contradição.
Segue-se que Y = ∅ , concluindo a demonstração.
7
Unidade 1 Exercícios Recomendados
1.6 Exercícios Recomendados
1. Dado o número natural a, seja Y ⊂ N um conjunto com as seguintes
propriedades:
(1) a ∈ Y ;
(2) n ∈ Y ⇒ n+ 1 ∈ Y .
Prove que Y contém todos os números naturais maiores do que ou iguais
a a.
(Sugestão: considere o conjunto X = Ia ∪ Y , onde Ia é o conjunto dos números
naturais 6 a, e prove, por indução, que X = N.)
2. Use o exercício anterior para provar que 2n+ 1 6 2n para todo n > 2 e,
em seguida, que n2 < 2n para todo n > 5.
3. Complete os detalhes da seguinte demonstração do Princípio de Boa
Ordenação: Seja A ⊂ N um conjunto que não possui um menor ele-
mento. Considere o conjunto X formado pelos números naturais n tais
que 1, 2, ..., n não pertencem a A. Observe que 1 ∈ X e, além disso, se
n ∈ X então todos os elementos de A são > n + 1. Como n + 1 não
pode ser o menor elemento de A, conclua que n + 1 ∈ X. Logo, por
indução, segue-se que X = N. Portanto A é vazio.
4. Prove, por indução, que (n+ 1
n
)n
6 n
para todo n > 3 e conclua daí que a sequência
1,
√
2,
3
√
3,
4
√
4 . . .
é decrescente a partir do terceiro termo.
5. Prove, por indução, que
1 + 22 + 32 + · · ·+ n2 = n(n+ 1)(2n+ 1)
6
.
6. Critique a seguinte argumentação: Quer-se provar que todo número natu-
ral é pequeno. Evidentemente, 1 é um número pequeno. Além disso, se n
for pequeno, n+ 1 também o será, pois não se torna grande um número
pequeno simplesmente somando-lhe uma unidade. Logo, por indução,
todo número natural é pequeno.
8
Unidade 1Números Naturais
7. Use a distributividade para calcular (m + n)(1 + 1) de duas maneiras
diferentes e em seguida use a lei do corte para concluir que m+n = n+m.
8. Seja X ⊂ N um conjunto não-vazio, com a seguinte propriedade: para
qualquer n ∈ N, se todos os números naturais menores do que n perten-
cem a X então n ∈ X. Prove que X = N. (Sugestão: boa ordenação.)
9. Seja P (n) uma propriedade relativa ao número natural n. Suponha que
P (1), P (2) são verdadeiras e que, para qualquer n ∈ N, a verdade de
P (n) e P (n + 1) implica a verdade de P (n + 2). Prove que P (n) é
verdadeira para todo n ∈ N.
10. Use indução para provar que
13 + 23 + 33 + · · ·+ n3 = 1
4
n2(n+ 1)2.
9
Unidade 1 Textos Complementares
1.7 Textos Complementares
Na Sala de Aula Re�exões sobre a sala de aula
Do ponto de vista do ensino em nível do ensino médio, não tem cabimento
expor a Matemática sob forma axiomática. Mas é necessário que o professor
saiba que ela pode ser organizada sob a forma acima delineada. Uma linha de
equilíbrio a ser seguida na sala de aula deve basear-se nos seguintes preceitos:
1. Nunca dar explicações falsas sob o pretexto de que os alunos ainda não têm
maturidade para entender a verdade. (Isto seria como dizer a uma criança que
os bebês são trazidos pela cegonha.) Exemplo: �in�nito é um número muito
grande�. Para outro exemplo, vide RPM 29, págs. 13-19.
2. Não insistir em detalhes formais para justi�car a�rmações que, além de
verdadeiras, são intuitivamente óbvias e aceitas por todos sem discussão nem
dúvidas. Exemplo: o segmento de reta que une um ponto interior a um ponto
exterior de uma circunferência tem exatamente um ponto em comum com essa
circunferência.
Em contraposição, fatos importantes cuja veracidade não é evidente, como
o Teorema de Pitágoras ou a Fórmula de Euler para poliedros convexos, devem
ser demonstrados (até mesmo de várias formas diferentes).
Excetuam-se, naturalmente, demonstrações longas, elaboradas ou que fa-
çam uso de noções e resultados acima do alcance dos estudantes desse nível
(como o Teorema Fundamental da Algebra, por exemplo).
Provar o óbvio transmite a falsa impressão de que a Matemática é inútil. Por
outro lado, usar argumentos elegantes e convincentes para demonstrar resulta-
dos inesperados é uma maneira de exibir sua força e sua beleza. As demons-
trações, quando objetivas e bem apresentadas, contribuem para desenvolver o
raciocínio, o espírito crítico, a maturidade e ajudam a entender o encadeamento
lógico das proposições matemáticas.
3. Ter sempre em mente que, embora a Matemática possa ser cultivada por
si mesma, como um todo coerente, de elevado padrão intelectual, formado por
conceitos e proposições de natureza abstrata, sua presença no currículo escolar
não se deve apenas ao valor dos seus métodos para a formação mental dos
jovens.
A importância social da Matemática provém de que ela fornece modelos
10
Unidade 1Números Naturais
para analisar situações da vida real. Assim, por exemplo, conjuntos são o
modelo para disciplinar o raciocínio lógico, números naturais são o modelo para
contagem e números reais são o modelo para medida; funções a�ns servem de
modelo para situações, como o movimento uniforme, em que os acréscimos da
função são proporcionais aos acréscimos da variável independente. E assim por
diante.
11
Unidade 1 Textos Complementares
Na Sala de Aula Uma recomendação
Não se deve dar muita importância à eterna questão de saber se 0 (zero) deve
ou não ser incluído entre os números naturais. (Vide �Meu Professor de Ma-
temática�, pág. 150.) Praticamente todos os livros de Matemática usados nas
escolas brasileiras consideram 0 como o primeiro número natural (consequente-
mente 1 é o segundo, 2 é o terceiro, etc). Como se viu acima, não adotamos
esse ponto-de-vista. Trata-se, evidentemente, de uma questão de preferência.
Deve-se lembrar que o símbolo 0 (sob diferentes formas grá�cas) foi empregado
inicialmente pelos maias,posteriormente pelos hindus, difundido pelos árabes e
adotado no ocidente, não como um número e sim como um algarismo, com o
utilíssimo objetivo de preencher uma casa decimal vazia. (No caso dos maias, a
base do sistema de numeração era 20, e não 10.) De resto, a opção do número
natural para iniciar a sequência não se limita a escolher entre 0 e 1. Frequente-
mente esquecemos que, do mesmo modo que conhecemos e usamos o zero mas
começamos os números naturais com 1, a Matemática grega, segundo apre-
sentada por Euclides, não considerava 1 como um número. Nos �Elementos�,
encontramos as seguintes de�nições:
�Unidade é aquilo pelo qual cada objeto é um. Número é uma multitude de
unidades�.
12
Unidade 1Números Naturais
Para Saber MaisComentários sobre De�nições e axiomas
Uma de�nição matemática é uma convenção que consiste usar um nome, ou
uma breve sentença, para designar um objeto ou uma propriedade, cuja descrição
normalmente exigiria o emprego de uma sentença mais longa. Vejamos algumas
de�nições, como exemplo.
• Ângulo é a �gura formada por duas semirretas que têm a mesma origem.
• Primos entre si são dois ou mais números naturais cujo único divisor
comum é a unidade.
Mas nem sempre foi assim. Euclides, por exemplo, começa os �Elementos�
com uma série de de�nições, das quais selecionamos as seguintes:
• Linha é um comprimento sem largura.
• Superfície é o que possui comprimento e largura somente.
• Quando uma reta corta outra formando ângulos adjacentes iguais, cada
um desses ângulos chama-se reto e as retas se dizem perpendiculares.
As de�nições de ângulo e de números primos entre si, dadas acima, bem
como as de�nições de ângulo reto e retas perpendiculares dadas por Euclides,
são corretas. Elas atendem aos padrões atuais de precisão e objetividade. Por
outro lado, nas de�nições de linha e superície, Euclides visa apenas oferecer ao
seu leitor uma imagem intuitiva desses conceitos. Elas podem servir para ilustrar
o pensamento geométrico mas não são utilizáveis nos raciocínios matemáticos
porque são formuladas em termos vagos e imprecisos.
Na apresentação de uma teoria matemática, toda de�nição faz uso de termos
especí�cos, os quais foram de�nidos usando outros termos, e assim sucessiva-
mente. Este processo iterativo leva a três possibilidades:
a) Continua inde�nidamente, cada de�nição dependendo de outras anteriores,
sem nunca chegar ao �m.
b) Conduz a uma circularidade, como nos dicionários. (Onde se vê, por exemplo:
compreender → perceber, perceber → entender e entender → compreender.)
13
Unidade 1 Textos Complementares
c) Termina numa palavra, ou num conjunto de palavras (de preferência dotadas
de conotações intuitivas simples) que não são de�nidas, isto é, que são tomadas
como representativas de conceitos primitivos. Exemplos: ponto, reta, conjunto.
Evidentemente, as alternativas (a) e (b) acima citadas não convêm à Ma-
temática. A alternativa (c) é a adotada. Se prestarmos atenção, veremos que
foi assim que aprendemos a falar. Numerosas palavras nos foram apresentadas
sem de�nição e permanecem até hoje em nosso vocabulário como conceitos
primitivos, que aprendemos a usar por imitação e experiência.
Para poder empregar os conceitos primitivos adequadamente, é necessário
dispor de um conjunto de princípios ou regras que disciplinem sua utilização
e estabeleçam suas propriedades. Tais princípios são chamados axiomas ou
postulados. Assim como os conceitos primitivos são objetos que não se de�nem,
os axiomas são proposições que não se demonstram.
Uma vez feita a lista dos conceitos primitivos e enunciados os axiomas
de uma teoria matemática, todas as demais noções devem ser de�nidas e as
a�rmações seguintes devem ser demonstradas.
Nisto consiste o chamado método axiomático. As proposições a serem
demonstradas chamam-se teoremas e suas consequências imediatas são
denominadas corolários. Uma proposição auxiliar, usada na demonstração de
um teorema, é chamada um lema.
Ser um axioma ou ser um teorema não é uma característica intrínseca de
uma proposição. Dependendo da preferência de quem organiza a apresentação
da teoria, uma determinada proposição pode ser adotada como axioma ou então
provada como teorema, a partir de outra proposição que a substituiu na lista
dos axiomas.
A seguir veremos um resumo da teoria matemática dos números naturais,
onde os conceitos primitivos são �número natural� e �sucessor� e os axiomas são
os de Peano.
14
Unidade 1Números Naturais
Para Saber MaisSobre o sistema de numeração
Um engenhoso processo, chamado sistema de numeração decimal, permite
representar todos os números naturais com o auxílio dos símbolos 0, 1, 2, 3, 4,
5, 6, 7, 8 e 9. Além disso, os primeiros números naturais têm nomes: o sucessor
do número um chama se �dois�, o sucessor de dois chama-se �três�, etc. A partir
de um certo ponto, esses nomes tornam-se muito complicados, sendo preferível
abrir mão deles e designar os grandes números por sua representação decimal.
(Na realidade, os números muito grandes não possuem nomes. Por exemplo,
como se chamaria o número 101000?).
Deve �car claro que o conjunto N = {1, 2, 3, . . .} dos números naturais é
uma sequência de objetos abstratos que, em princípio, são vazios de signi�cado.
Cada um desses objetos (um número natural) possui apenas um lugar determi-
nado nesta sequência. Nenhuma outra propriedade lhe serve de de�nição. Todo
número tem um sucessor (único) e, com exceção de 1, tem também um único
antecessor (número do qual é sucessor).
Vistos desta maneira, podemos dizer que os números naturais são números
ordinais : 1 é o primeiro, 2 é o segundo, etc.
15
Unidade 1 Textos Complementares
Para Saber Mais Um comentário gramatical
Quando dizemos �o número um�, �o número dois� ou �o número três�, as
palavras �um�, �dois� e �três� são substantivos, pois são nomes de objetos. Isto
contrasta com o uso destas palavras em frases como �um ano, dois meses e
três dias�, onde elas aparecem para dar a ideia de número cardinal, isto é, como
resultados de contagens. Nesta frase, �um�, �dois� e �três� não são substanti-
vos. Pertencem a uma categoria gramatical que, noutras línguas (como francês,
inglês e alemão, por exemplo) é chamada adjetivo numeral e que os gramáticos
brasileiros e portugueses, há um par de décadas, resolveram chamar de numeral
apenas. Este comentário visa salientar a diferença entre os números naturais,
olhados como elementos do conjunto N, e o seu emprego como números cardi-
nais. Este segundo aspecto será abordado no capítulo seguinte.
16
Unidade 1Números Naturais
Para Saber MaisCuidado!
O axioma da indução é uma forma sagaz e operacional de dizer que qualquer
número natural n pode ser alcançado se partirmos de 1 e repetirmos su�ciente-
mente a operação de tomar o sucessor de um número. Ele está presente (pelo
menos de forma implícita) sempre que, ao a�rmarmos a veracidade de uma pro-
posição referente aos números naturais, veri�camos que ela é verdadeira para
n = 1, n = 2, n = 3 e dizemos �e assim por diante...�. Mas é preciso ter
cuidado com esta última frase. Ela pressupõe que P (n) ⇒ P (n′) para todo
n ∈ N. No �nal deste capítulo, apresentamos como exercícios algumas propo-
sições demonstráveis por recorrência, bem como alguns curiosos paradoxos que
resultam do uso inadequado do axioma da indução.
17
Unidade 1 Textos Complementares
18
2
1
Números Cardinais
Sumário
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Funções . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 A Noção de Número Cardinal . . . . . . . . . . . . 4
2.4 Conjuntos Finitos . . . . . . . . . . . . . . . . . . . 7
2.5 Exercícios Recomendados . . . . . . . . . . . . . . . 10
2.6 Exercícios Suplementares . . . . . . . . . . . . . . . 10
Unidade 2 Introdução
2.1 Introdução
A importância dos números naturais provém do fato de que eles constituem
o modelo matemático que torna possível o processo de contagem. Noutras
palavras,eles respondem a perguntas do tipo: �Quantos elementos tem este
conjunto?�
Para contar os elementos de um conjunto é necessário usar a noção de cor-
respondência biunívoca, ou bijeção. Trata-se de um caso particular do conceito
de função, abordado aqui de forma breve, que será desenvolvido com maiores
detalhes na Unidade 3 de MA11.
2.2 Funções
Definição 1 Dados os conjuntos X, Y , uma função f : X → Y (lê-se �uma função de
X em Y �) é uma regra (ou conjunto de instruções) que diz como associar a
cada elemento x ∈ X um elemento y = f(x) ∈ Y .
O conjunto X chama-se o domínio e Y é o contra-domínio da função f .
Para cada x ∈ X, o elemento f(x) ∈ Y chama-se a imagem de x pela função
f , ou o valor assumido pela função f no ponto x ∈ X. Escreve-se x 7→ f(x)
para indicar que f transforma (ou leva) x em f(x).
Exemplos particularmente simples de funções são a função identidade f :
X → X, de�nida por f(x) = x para todo x ∈ X e as funções constantes
f : X → Y , onde se toma um elemento c ∈ Y e se põe f(x) = c para todo
x ∈ X.
+ Para Saber Mais - Recomendações - Clique para ler
Exemplo 1 Sejam X o conjunto dos triângulos do plano Π e R o conjunto dos números
reais (que abordaremos logo mais). Se, a cada t ∈ X, �zermos corresponder o
número real f(t) = área do triângulo t, obteremos uma função f : X → R.
2
Unidade 2Números Cardinais
Exemplo 2Sejam S o conjunto dos segmentos de reta do plano Π e ∆ o conjunto das
retas desse mesmo plano. A regra que associa a cada segmento AB ∈ S sua
mediatriz g(AB) de�ne uma função g : S → ∆.
Exemplo 3A correspondência que associa a cada número natural n seu sucessor n+ 1
de�ne uma função s : N→ N, com s(n) = n + 1.
Definição 2Uma função f : X → Y chama-se injetiva quando elementos diferentes
em X são transformados por f em elementos diferentes em Y . Ou seja, f é
injetiva quando x 6= x′ em X ⇒ f(x) 6= f(x′).
Esta condição pode também ser expressa em sua forma contrapositiva:
f(x) = f(x′) ⇒ x = x′.
Nos três exemplos dados acima, apenas o terceiro é de uma função injetiva.
(Dois triângulos diferentes podem ter a mesma área e dois segmentos distintos
podem ter a mesma mediatriz mas números naturais diferentes têm sucessores
diferentes.)
Definição 3Diz-se que uma função f : X → Y é sobrejetiva quando, para qualquer
elemento y ∈ Y , pode-se encontrar (pelo menos) um elemento x ∈ X tal que
f(x) = y.
Nos três exemplos dados acima, apenas o segundo apresenta uma função
sobrejetiva. (Toda reta do plano é mediatriz de algum segmento mas apenas
os números reais positivos podem ser áreas de triângulos e o número 1 não é
sucessor de número natural algum.)
Definição 4Chama-se imagem do subconjunto A ⊂ X pela função f : X → Y ao
subconjunto f(A) ⊂ Y formado pelos elementos f(x), com x ∈ A.
3
Unidade 2 A Noção de Número Cardinal
Portanto, uma função f : X → Y é sobrejetiva quando f(X) = Y . O
conjunto f(X), imagem do domínio X pela função f chama-se também a
imagem da função f .
Nos Exemplos 1, 2 e 3, a imagem da função f é o conjunto dos números
reais positivos, a imagem de g é todo o conjunto ∆ e a imagem de s é o
conjunto dos números naturais ≥ 2.
Dada a função f : X → Y , para saber se um certo elemento b ∈ Y pertence
ou não à imagem f(X), escrevemos a �equação� f(x) = b e procuramos
achar algum x ∈ X que a satisfaça. Consequentemente, para mostrar que f é
sobrejetiva deve-se provar que a equação f(x) = y possui uma solução x ∈ X,
seja qual for o y ∈ Y dado.
+ Para Saber Mais - Recomendação - Clique para ler
Exemplo 4 Considere a tentativa de de�nir uma função f : N → N, estipulando que,
para todo n ∈ N, o número natural p = f(n) deve ser tal que p2 + 3 = n. O
número p = f(n) só pode ser encontrado se n for igual a 4, 7, 12, 19, ... pois
nem todos os números naturais são da forma p2 + 3. Assim, esta regra não
de�ne uma função com domínio N, porque tem exceções.
Exemplo 5 Indiquemos com X o conjunto dos números reais positivos e com Y o
conjunto dos triângulos do plano. Para cada x ∈ X, ponhamos f(x) = t caso t
seja um triângulo cuja área é x. Esta regra não de�ne uma função f : X → Y
porque é ambígua: dado o número x > 0, existe uma in�nidade de triângulos
diferentes com área x.
2.3 A Noção de Número Cardinal
A conceito de número cadinal se estabelece por meio da noção de bijeção.
Definição 5 Uma função f : X → Y chama-se uma bijeção, ou uma correspondência
biunívoca entre X e Y quando é ao mesmo tempo injetiva e sobrejetiva.
4
Unidade 2Números Cardinais
Exemplo 6Sejam X = {1, 2, 3, 4, 5} e Y = {2, 4, 6, 8, 10}. De�nindo f : X → Y
pela regra f(n) = 2n, temos uma correspondência biunívoca, onde f(1) = 2,
f(2) = 4, f(3) = 6, f(4) = 8 e f(5) = 10.
Exemplo 7Um exemplo particularmente curioso de correspondência biunívoca, que
estende o exemplo anterior, foi descoberto pelo físico Galileu Galilei, que viveu
há quatrocentos anos. Seja P o conjunto dos números naturais pares:
P = {2, 4, 6, . . . , 2n, . . .}.
Obtém-se uma correspondência biunívoca f : N→ P pondo-se f(n) = 2n para
todo n ∈ N. O interessante deste exemplo é que P é um subconjunto próprio
de N.
Exemplo 8Sejam Y a base de um triângulo e X um segmento paralelo a Y , unindo
os outros dois lados desse triângulo. Seja ainda P o vértice oposto à base
Y . Obtém-se uma correspondência biunívoca f : X → Y associando a cada
x ∈ X o ponto f(x) onde a semirreta Px intersecta a base Y .
5
Unidade 2 A Noção de Número Cardinal
Figura 2.1: Correspondência biunívoca entre dois segmentos
Exemplo 9 Neste exemplo, X = C \ {P} é o conjunto obtido retirando da circun-
ferência o ponto P e Y é uma reta perpendicular ao diâmetro que não passa
por P . De�na a correspondência biunívoca f : X → Y pondo, para cada
x ∈ X, f(x) = intersecção da semirreta Px com a reta Y .
Figura 2.2: O círculo sem um ponto e a reta
Definição 6 Diz-se que dois conjuntos X e Y tem o mesmo número cardinal quando
se pode de�nir uma correspondência biunívoca f : X → Y .
Cada um dos quatro exemplos acima exibe um par de conjuntos X, Y com
o mesmo cardinal.
6
Unidade 2Números Cardinais
Exemplo 10Sejam X = {1} e Y = {1, 2}. Evidentemente não pode existir uma
correspondência biunívoca f : X → Y , portanto X e Y não têm o mesmo
número cardinal.
+ Para Saber Mais - A palavra �número� no dicionário - Clique para ler
2.4 Conjuntos Finitos
Dado n ∈ N, indiquemos com a notação In o conjunto dos números naturais
de 1 até n. Assim, I1 = {1}, I2 = {1, 2}, I3 = {1, 2, 3} e, mais geralmente,
um número natural k pertence a In se, e somente se, 1 ≤ k ≤ n.
Definição 7Seja X um conjunto. Diz-se que X é �nito, e que X tem n elementos
quando se pode estabelecer uma correspondência biunívoca f : In → X.
O número natural n chama-se então o número cardinal do conjunto X ou,
simplesmente, o número de elementos de X. A correspondência f : In → X
chama-se uma contagem dos elementos de X. Pondo f(1) = x1, f(2) =
x2, . . . , f(n) = xn, podemos escrever X = {x1, x2, . . . , xn}. Para todo n, o
conjunto In é �nito e seu número cardinal é n. Assim, todo número natural n
é o número cardinal de algum conjunto �nito.
A �m de evitar exceções, admite-se ainda incluir o conjunto vazio ∅ entre
os conjuntos �nitos e diz-se que ∅ tem zero elementos. Assim, por de�nição,
zero é o número cardinal do conjunto vazio.
Diz-se que um conjunto X é in�nito quando ele não é �nito. Isto quer
dizer que X não é vazio e que, não importa qual seja n ∈ N , não existe
correspondência biunívoca f : In → X.
No Exemplo 6 acima, temos X = I5 e f : X → Y é uma contagem
dos elementos de Y . Assim, Y é um conjunto �nito, com 5 elementos. O
conjunto N dos números naturais é in�nito. Com efeito, dada qualquer função
f : In → N , não importa qual n se �xou, pomos k = f(1) + f(2) + · · ·+ f(n)
e vemos que, para todo x ∈ In, tem-se f(x) < k, logo não existe x ∈ In tal
7
Unidade 2 Conjuntos Finitos
que f(x) = k. Assim, é impossível cumprir a condição de sobrejetividade na
de�nição de correspondência biunívoca.
O número cardinal de um conjunto�nito X, que indicaremos com a notação
n(X), goza de algumas propriedades básicas, entre as quais destacaremos as
seguintes:
1. O número de elementos de um conjunto �nito é o mesmo, seja qual for
a contagem que se adote. Isto signi�ca que se f : Im → X e g : In → X
são correspondências biunívocas então m = n.
2. Todo subconjunto Y de um conjunto �nito X é �nito e n(Y ) ≤ n(X).
Tem-se n(Y ) = n(X) somente quando Y = X.
3. Se X e Y são �nitos então X ∪Y é �nito e tem-se n(X ∪Y ) = n(X) +
n(Y )− n(X ∩ Y ) .
4. Sejam X, Y conjuntos �nitos. Se n(X) > n(Y ), nenhuma função f :
X → Y é injetiva e nenhuma função g : Y → X é sobrejetiva.
As demonstrações destes fatos se fazem por induçãoo ou por boa-ordenação.
(Veja, por exemplo, [Lima]: Curso de Análise, vol. 1, págs. 33-38.) A primeira
parte do item 4. acima é conhecida como o princípio das casas de pombos : se
há mais pombos do que casas num pombal, qualquer modo de alojar os pombos
deverá colocar pelo menos dois deles na mesma casa. As vezes, o mesmo fato
é chamado o princípio das gavetas : se m > n, qualquer maneira de distribuir
m objetos em n gavetas deverá por ao menos dois desses objetos na mesma
gaveta. (Na referência [Lima] citada, este é o Corolário 1 na página 35.)
O princípio das casas de pombos, com toda sua simplicidade, possui inte-
ressantes aplicações. Vejamos duas delas.
Exemplo 11 Tomemos um número natural de 1 a 9. Para �xar as ideias, seja 3 esse
número. Vamos provar que todo número natural m possui um múltiplo cuja
representação decimal contém apenas os algarismos 3 ou 0. Para isso, conside-
remos o conjunto X = {3, 33, . . . , 33 . . . 3}, cujos elementos são os m primeiros
números naturais representados somente por algarismos iguais a 3. Se algum
dos elementos de X for múltiplo de m, nosso trabalho acabou. Caso contrário,
8
Unidade 2Números Cardinais
formamos o conjunto Y = {1, 2, . . . ,m− 1} e de�nimos a função f : X → Y
pondo, para cada x ∈ X,
f(x) = resto da divisão de x por m.
Como X tem mais elementos do que Y , o princípio das casas de pombos
assegura que existem elementos x1 < x2 no conjunto X tais que f(x1) = f(x2).
Isto signi�ca que x1 e x2 , quando divididos por m, deixam o mesmo resto. Logo
x2−x1 é múltiplo de m. Mas é claro que se x1 tem p algarismos e x2 tem p+q
algarismos então a representação decimal de x2 − x1 consiste em q algarismos
iguais a 3 seguidos de p algarismos iguais a 0.
Exemplo 12Vamos usar o princípio das gavetas para provar que, numa reunião com n
pessoas (n ≥ 2), há sempre duas pessoas (pelo menos) que têm o mesmo nú-
mero de amigos naquele grupo. Para ver isto, imaginemos n caixas, numeradas
com 0, 1, . . . , n − 1. A cada uma das n pessoas entregamos um cartão que
pedimos para depositar na caixa correspondente ao número de amigos que ela
tem naquele grupo. As caixas de números 0 e n− 1 não podem ambas receber
cartões pois se houver alguém que não tem amigos ali, nenhum dos presentes
pode ser amigo de todos, e vice-versa. Portanto temos, na realidade, n cartões
para serem depositados em n−1 caixas. Pelo princípio das gavetas, pelo menos
uma das caixas vai receber dois ou mais cartões. Isto signi�ca que duas ou mais
pessoas ali têm o mesmo número de amigos entre os presentes.
+ Para Saber Mais - Sobre Conjuntos In�nitos - Clique para ler
+ Para Saber Mais - Fantasia Matemática - Clique para ler
+ Para Saber Mais - Cuidado! - Clique para ler
9
Unidade 2 Exercícios Recomendados
2.5 Exercícios Recomendados
1. Prove, por indução, que se X é um conjunto �nito com n elementos
então existem n! bijeções f : X → X.
2. Prove, por indução, que um conjunto com n elementos possui 2n subcon-
juntos.
3. Sejam X e Y dois conjuntos �nitos, com m e n elementos, respectiva-
mente. Mostre que existem nm funções f : X → Y . Você seria capaz
de resolver diretamente o Exercício 2, utilizando este resultado?
2.6 Exercícios Suplementares
1. De�na uma função sobrejetiva f : N → N tal que, para todo n ∈ N, a
equação f(x) = n possui uma in�nidade de raízes x ∈ N.
Sugestão: Todo número natural se escreve, de modo único sob a forma
2a · b, onde a, b ∈ N e b é ímpar.
2. Dados n (n > 2) objetos de pesos distintos, prove que é possível deter-
minar qual o mais leve e qual o mais pesado fazendo 2n − 3 pesagens
em uma balança de pratos. É esse o número mínimo de pesagens que
permitem determinar o mais leve e o mais pesado?
3. Prove que, dado um conjunto com n elementos, é possível fazer uma �la
com seus subconjuntos de tal modo que cada subconjunto da �la pode
ser obtido a partir do anterior pelo acréscimo ou pela supressão de um
único elemento.
4. Todos os quartos do Hotel Georg Cantor estão ocupados, quando chegam
os trens T1, T2, . . . , (em quantidade in�nita), cada um deles com in�nitos
passageiros. Que deve fazer o gerente para hospedar todos?
10
Referências Bibliográ�cas
[Lima] Lima, Elon Lages. Curso de Análise, Vol. 1. Projeto Euclides, IMPA,
Rio de Janeiro, 1976. 8, 15
11
Unidade 2 Textos Complementares
2.7 Textos Complementares
Para Saber Mais Recomendações
1. É importante ressaltar que f(x) é a imagem do elemento x ∈ X pela
função f , ou o valor da função f no ponto x ∈ X. Os livros antigos, bem
como alguns atuais, principalmente os de Cálculo, costumam dizer �a função
f(x)� quando deveriam dizer �a função f �. Algumas vezes essa linguagem
inexata torna a comunicação mais rápida e �ca difícil resistir à tentação de
usá-la. Mas é indispensável a cada momento ter a noção precisa do que se está
fazendo.
Na prática, há algumas funções com as quais é simples e natural lidar usando
a terminologia correta. Por exemplo, é fácil acostumar-se a escrever as funções
sen : R → R e log : R+ → R, guardando as notações senx e log x para os
números reais que são os valores destas funções num dado ponto x. Por outro
lado, quando se trata de uma função polinomial, o bom-senso nos leva a dizer
�a função x2 − 5x + 6�
em vez da forma mais correta e mais pedante �a função p : R→ R tal que
p(x) = x2 − 5x + 6
para todo x ∈ R� . Caso análogo se dá com a função exponencial ex, embora
recentemente se tenha tornado cada vez mais frequente escrever exp(x) = ex
e assim poder falar da função exp : R→ R.
2. Deve-se ainda recordar que uma função consta de três ingredientes: domínio,
contra-domínio e a lei de correspondência x 7→ f(x). Mesmo quando dizemos
simplesmente �a função f �, �cam subentendidos seu domínio X e seu contra-
domínio Y . Sem que eles sejam especi�cados, não existe a função. Assim
sendo, uma pergunta do tipo �Qual é o domínio da função f(x) = 1/x� ?,
estritamente falando, não faz sentido. A pergunta correta seria: �Qual é o
maior subconjunto X ⊂ R tal que a fórmula f(x) = 1/x de�ne uma função
f : X → R ?� Novamente, a pergunta incorreta é mais simples de formular.
Se for feita assim, é preciso saber seu signi�cado.
Segue-se do que foi dito acima que as funções f : X → Y e g : X ′ → Y ′
são iguais se, e somente se, X = X ′, Y = Y ′ e f(x) = g(x) para todo x ∈ X.
12
Unidade 2REFERÊNCIAS BIBLIOGRÁFICAS
Para Saber MaisRecomendação
3. Em muitos exemplos de funções f : X → Y , principalmente na Matemática
Elementar, X e Y são conjuntos numéricos e a regra x 7→ f(x) exprime o valor
f(x) por meio de uma fórmula que envolve x. Mas em geral não precisa ser
assim. A natureza da regra que ensina como obter f(x) quando é dado x é
inteiramente arbitrária, sendo sujeita apenas a duas condições:
a) Não deve haver exceções: a �m de que a função f tenha o conjunto X
como domínio, a regra deve fornecer f(x), seja qual for x ∈ X dado.
b) Não pode haver ambiguidades: a cada x ∈ X, a regra deve fazer corres-
ponder um único f(x) em Y . Os exemplos a seguir ilustram essas exigências.
13
Unidade 2 Textos Complementares
Para Saber Mais A palavra �número� no dicionário
As vezes se diz que os conjuntos X e Y são (numericamente) equivalentes
quando é possível estabelecer uma correspondência biunívoca f : X → Y , ou
seja, quando X e Y têm o mesmonúmero cardinal.
Isto explica (embora não justi�que) a de�nição dada no dicionário mais
vendido do país. Em algumas situações, ocorrem em Matemática de�nições
do tipo seguinte: um vetor é o conjunto de todos os segmentos de reta do
plano que são equipolentes a um segmento dado. (De�nição �por abstração�.)
Nessa mesma veia, poder-se-ia tentar dizer: �número cardinal de um conjunto
é o conjunto de todos os conjuntos equivalentes a esse conjunto.� No caso
do dicionário, há um conjunto de defeitos naquela de�nição, com um número
cardinal razoavelmente elevado. Os três mais graves são:
1. Um dicionário não é um compêndio de Matemática, e muito menos de Ló-
gica. Deve conter explicações acessíveis ao leigo (de preferência, corretas). As
primeiras acepções da palavra �número� num dicionário deveriam ser �quanti-
dade� e �resultado de uma contagem ou de uma medida�.
2. A de�nição em causa só se aplica a números cardinais, mas a ideia de número
deveria abranger os racionais e, pelo menos, os reais.
3. O �conjunto de todos os conjuntos equivalentes a um conjunto dado� é um
conceito matematicamente incorreto. A noção de conjunto não pode ser usada
indiscriminadamente, sem submeter-se a regras determinadas, sob pena de con-
duzir a paradoxos, ou contradições. Uma dessas regras proíbe que se forme
conjuntos a não ser que seus elementos pertençam a, ou sejam subconjuntos
de, um determinado conjunto-universo. Um exemplo de paradoxo que resulta
da desatenção a essa regra é �o conjunto X de todos os conjuntos que não
são elementos de si mesmos.� Pergunta-se: X é ou não é um elemento de si
mesmo? Qualquer que seja a resposta, chega-se a uma contradição.
14
Unidade 2REFERÊNCIAS BIBLIOGRÁFICAS
Para Saber MaisSobre Conjuntos In�nitos
Para encerrar estas considerações a respeito de números cardinais, faremos
alguns comentários sobre conjuntos in�nitos.
Em primeiro lugar, convém esclarecer que a maior contribuição de Cantor
não foi a adoção da linguagem e da notação dos conjuntos e sim suas desco-
bertas sobre os números cardinais de conjuntos in�nitos. Ele foi o primeiro a
descobrir que existem conjuntos in�nitos com diferentes cardinalidades ao pro-
var que não pode haver uma correspondência biunívoca entre N e o conjunto
R dos números reais e que nenhum conjunto X pode estar em correspondência
biunívoca com o conjunto P(X) cujos elementos são os subconjuntos de X.
Além disso, ele mostrou que a reta, o plano e o espaço tri-dimensional (ou
mesmo espaços com dimensão superior a três) têm o mesmo número cardinal.
Estes fatos, que atualmente são considerados corriqueiros entre os matemáticos,
causaram forte impacto na época (meados do século dezenove).
A segunda observação diz respeito a funções f : X → X de um conjunto em
si mesmo. Quando X é �nito, f é injetiva se, e somente se, é sobrejetiva (veja
a referência [Lima].) Mas isto não é verdadeiro para X in�nito. Por exemplo,
se de�nirmos a função f : N → N pondo, para cada n ∈ N, f(n) = número
de fatores primos distintos que ocorrem na decomposição de n, veremos que f
é sobrejetiva mas não é injetiva. (Para cada b ∈ N existe uma in�nidade de
números n tais que f(n) = b.) Além disso, as funções f : N→ N, g : N→ N,
h : N→ N e ϕ : N→ N, de�nidas por
f(n) = n + 1,
g(n) = n + 30,
h(n) = 2n e
ϕ(n) = 3n
(2.1)
são injetivas mas não são sobrejetivas. Estas quatro funções são protagonistas
da historinha seguinte que fecha a unidade.
15
Unidade 2 Textos Complementares
Para Saber Mais Fantasia Matemática
O Grande Hotel Georg Cantor tinha uma in�nidade de quartos, numera-
dos consecutivamente, um para cada número natural. Todos eram igualmente
confortáveis. Num �m-de-semana prolongado, o hotel estava com seus quartos
todos ocupados, quando chega um viajante. A recepcionista vai logo dizendo:
� Sinto muito, mas não há vagas.
Ouvindo isto, o gerente interveio:
� Podemos abrigar o cavalheiro, sim senhora.
E ordena:
� Trans�ra o hóspede do quarto 1 para o quarto 2, passe o do quarto 2
para o quarto 3 e assim em diante. Quem estiver no quarto n, mude para o
quarto n + 1. Isto manterá todos alojados e deixará disponível o quarto 1 para
o recém-chegado.
Logo depois chegou um ônibus com 30 passageiros, todos querendo hospe-
dagem. A recepcionista, tendo aprendido a lição, removeu o hóspede de cada
quarto n para o quarto n+ 30 e acolheu assim todos os passageiros do ônibus.
Mas �cou sem saber o que fazer quando, horas depois, chegou um trem com
uma in�nidade de passageiros. Desesperada, apelou para o gerente que pron-
tamente resolveu o problema dizendo:
� Passe cada hóspede do quarto n para o quarto 2n. Isto deixará vagos todos
os apartamentos de número ímpar, nos quais poremos os novos hóspedes.
� Pensando melhor: mude quem está no quarto n para o quarto 3n. Os novos
hóspedes, ponha-os nos quartos de número 3n+2. Deixaremos vagos os quartos
de número 3n + 1. Assim, sobrarão ainda in�nitos quartos vazios e eu poderei
ter sossego por algum tempo.
16
Unidade 2REFERÊNCIAS BIBLIOGRÁFICAS
Para Saber MaisCuidado!
Não confunda conjunto in�nito com aquele que tem um número muito grande
(porém �nito) de elementos. Quando, na linguagem comum, se diz algo como �-
Já ouvi isto uma in�nidade de vezes�, trata-se de uma mera força de expressão.
Não há distâncias in�nitas (mesmo entre duas galáxias bem afastadas) e até
o número de átomos do universo é �nito. (O físico Arthur Eddington estimou
o número de prótons do universo em 136 × 2256. O número de átomos é
certamente menor pois todo átomo contém ao menos um próton.) E importante
ter sempre em mente que nenhum número natural n é maior do que todos os
demais: tem-se sempre n < n + 1.
17
Unidade 2 Textos Complementares
18
3
1
O Princípio de Indução
Matemática
Sumário
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2
3.2 O Poder do Método de Indução . . . . . . . . . . . 2
3.3 Exercícios Recomendados . . . . . . . . . . . . . . . 12
3.4 Exercícios Suplementares . . . . . . . . . . . . . . . 13
3.5 Textos Complementares . . . . . . . . . . . . . . . . 14
Unidade 3 Introdução
3.1 Introdução
Nesta unidade e na próxima, mostraremos como utilizar o Axioma de Indução
para de�nir com rigor objetos matemáticos e também como utilizá-lo como
poderoso instrumento para demonstrar os mais variados resultados envolvendo
números naturais. Algumas das noções introduzidas nesta e na próxima unidade
serão retomadas de modo mais sistemático nas Unidades 5 a 8.
3.2 O Poder do Método de Indução
Comecemos com a pergunta:
O que signi�cam expressões do tipo 1 + 2 + · · ·+ n e 1 · 2 · · · · n?
Note que as operações de adição e de multiplicação nos números naturais (ou em
qualquer sistema numérico) são binárias, isto é, elas relacionam dois elementos
de cada vez. Apesar disso, temos uma ideia bastante intuitiva do signi�cado
das expressões acima, até mesmo no que diz respeito aos pontinhos que nelas
aparecem. Existe, contudo, um modo de tornar mais rigorosas de�nições desse
tipo por meio do Princípio de Indução Matemática, como veremos mais adiante.
Antes, porém, recordemos este princípio que demonstramos na Unidade 1.
Princípio de Indução Matemática Se P (n) é uma propriedade relativa ao
número natural n, tal que
i) P (1) é válida;
ii) Para todo n ∈ N, a validez de P (n) implica a validez de P (n+ 1).
Então P (n) é válida qualquer que seja o número natural n.
+ Para Saber Mais - Comentário - Clique para ler
+ Para Saber Mais - Indução Empírica vs Indução Matemática - Cli-
que para ler
2
Unidade 3O Princípio de Indução Matemática
Para de�nir uma expressão En, para todo número natural n, basta de�nirmos
E1 e mostrar, para todo n ∈ N, como obter sem ambiguidade En+1 a partir de
En.
Nesse caso, dizemos que En foi de�nido por recorrência.
Vejamos como intervém o Princípio de Indução Matemática para justi�car
este tipo de de�nição. Seja X o subconjunto de N, determinado pela condição:
n ∈ X ⇐⇒ En está de�nido.
Pela caracterização doconjunto X, temos que 1 ∈ X e, para todo n ∈ N,
n ∈ X ⇒ n+ 1 ∈ X. Portanto, X = N.
De�nições por recorrência podem ser utilizadas para dar um signi�cado a
expressões como no início da unidade.
Exemplo 1De�nimos S1 = 1. Em seguida, supondo Sn de�nido, pomos
Sn+1 = Sn + (n+ 1).
Damos assim, um sentido matemático preciso à expressão:
Sn = 1 + 2 + · · ·+ n.
Por outro lado, de�nindo 1! = 1 e pondo (n+1)! = n!(n+1), supondo que
n! esteja de�nido, damos também, neste caso, um sentido matemático para a
expressão:
n! = 1 · 2 · · ·n.
Para generalizar os exemplos acima, vamos introduzir a noção de sequência.
Teremos oportunidade de comprovar, ao longo do curso, o quanto é central este
conceito.
Definição 1Uma sequência de elementos de um conjunto A é uma função x : N→ A.
3
Unidade 3 O Poder do Método de Indução
Tendo em vista que uma função conhecida quando se sabe qual é a ima-
gem de todo elemento de seu domínio, uma sequência x : N → A pode ser
representada como
x(1), x(2), . . . , x(n), . . . ,
ou ainda, denotando x(n) por xn, podemos representá-la concisamente por
(xn).
Por motivo de economia, quando dissermos que um conjunto A possui uma
adição ou uma multiplicação satisfazendo às leis básicas da aritmética, esta-
remos supondo que em A estão de�nidas duas operações com propriedades
semelhantes às correspondentes operações nos naturais.
Seja agora (xn) uma sequência de elementos de um conjunto A que possui
duas operações, de adição e de multiplicação, satisfazendo às leis básicas da
aritmética.
Definição 2 De�nem-se Sn e Pn em A, como se segue: S1 = P1 = x1 e
Sn+1 = Sn + xn+1 e Pn+1 = Pn · xn+1.
Isto dá sentido às seguintes expressões:
Sn = x1 + x2 + · · ·+ xn e Pn = x1 · x2 · · ·xn.
Somas e produtos, como acima, serão também escritos com as notações de
somatórios e produtórios:
Sn =
n∑
i=1
xi e Pn =
n∏
i=1
xi,
que se leem como �somatório quando i varia de 1 até n de xi� e �produto
quando i varia de 1 até n de xi�, respectivamente.
Note que a partir de uma sequência dada (xn), pudemos de�nir de modo
natural duas outras sequências, a saber: (Sn) e (Pn).
Dada uma sequência constante, x(n) = a, para todo n ∈ N, onde a ∈ A,
os termos da sequência Pn a ela associada são por de�nição as potências de a.
Pela sua importância, destacamos essa de�nição a seguir.
4
Unidade 3O Princípio de Indução Matemática
Definição 3Seja a um elemento de um conjunto A munido de uma multiplicação sujeita
às leis básicas da aritmética. As potências an de a, com n ∈ N, são de�nidas
por recorrência como segue: a1 = a e an+1 = an · a.
Quando a 6= 0, convenciona-se de�nir a0 = 1. Isto será especialmente con-
veniente quando estendermos as potências para expoentes não necessariamente
números naturais. Isto se tornará bem mais claro na Unidade 13 de MA11.
Exemplo 2Neste exemplo, queremos determinar uma fórmula para a soma dos n pri-
meiros números naturais: Sn = 1 + 2 + · · ·+ n.
Conta-se a seguinte história sobre o matemático alemão Carl Friedrich Gauss
(1777-1855), considerado um dos maiores gênios da matemática de todos os
tempos, quando ainda garoto. Na escola, o professor, para aquietar a turma de
Gauss, mandou os alunos calcularem a soma de todos os números naturais de
1 a 100. Qual não foi a sua surpresa quando, instantes depois, o menino deu
a resposta: 5050. Indagado sobre como tinha descoberto tão rapidamente o
resultado, Gauss, então, descreveu o método a seguir.
Sendo
Sn = 1 + 2 + · · ·+ n,
o objetivo é encontrar uma fórmula fechada1 para Sn.
Somando a igualdade acima, membro a membro, com ela mesma, porém
com as parcelas do segundo membro em ordem invertida, temos que
Sn = 1 + 2 + · · · + n
Sn = n + (n− 1) + · · · + 1
2Sn = (n+ 1) + (n+ 1) + · · · + (n+ 1)
Daí segue-se que 2Sn = n(n+ 1) e, portanto,
Sn =
n(n+ 1)
2
.
1Uma fórmula fechada para Sn, a grosso modo, é uma função de n que permite calcular
diretamente os valores de Sn fazendo um pequeno número de cálculos.
5
Unidade 3 O Poder do Método de Indução
Vamos ser críticos com relação à prova acima. Para a maioria das pessoas,
essa prova parece impecável, mas se alguém nos perguntasse o que está escon-
dido atrás dos pontinhos, talvez nos sentíssemos embaraçados. Também, como
ter absoluta certeza de que nada acontece fora do nosso controle, exatamente
na imensa região coberta pelos pontinhos?
Para não pairar nenhuma dúvida sobre o nosso resultado, vamos provar a
fórmula utilizando o Princípio de Indução Matemática.
Considere a sentença sobre os naturais:
P (n) : 1 + 2 + · · ·+ n = n(n+ 1)
2
. (3.1)
Note que
P (1) : 1 =
1(1 + 1)
2
é verdadeira.
Observe também que
P (n+ 1): 1 + 2 + · · ·+ n+ (n+ 1) = (n+ 1)(n+ 2)
2
.
Agora, suponhamos que para algum n ∈ N, tenhamos P (n) verdadeira, isto
é, a fórmula (1.1) é válida para tal valor de n. Somando n+1 a ambos os lados
dessa igualdade, temos que é verdadeira a igualdade
1 + 2 + · · ·+ n+ (n+ 1) = n(n+ 1)
2
+ n+ 1 =
n(n+ 1) + 2(n+ 1)
2
=
(n+ 1)(n+ 2)
2
,
o que estabelece a veracidade de P (n+ 1).
Pelo Princípio de Indução, tem-se que a fórmula P (n) é verdadeira para
todo n ∈ N.
+ Na Sala de Aula - Considerações sobre o Rigor - Clique para ler
Exemplo 3 Queremos validar a fórmula
P (n) : 12 + 22 + · · ·+ n2 = n(n+ 1)(2n+ 1)
6
. (3.2)
6
Unidade 3O Princípio de Indução Matemática
Note que
P (1) : 12 =
1(1 + 1)(2 + 1)
6
é verdadeira.
Suponha que, para algum n ∈ N, se tenha que P (n) é verdadeira, isto é,
(1.2) é válida. Somando (n + 1)2 a ambos os lados da igualdade (1.2), temos
que
12 + 22 + · · ·+ n2 + (n+ 1)2 = n(n+ 1)(2n+ 1)
6
+ (n+ 1)2 =
n(n+ 1)(2n+ 1) + 6(n+ 1)2
6
=
(n+ 1)[n(2n+ 1) + 6(n+ 1)]
6
=
(n+ 1)[(n+ 1) + 1][2(n+ 1) + 1]
6
,
estabelecendo assim a veracidade de P (n+ 1).
Portanto, a fórmula é válida para todo n ∈ N.
Exemplo 4Vamos provar que é verdadeira, para todo n ∈ N, a fórmula:
P (n) :
1
1.2
+
1
2.3
+ · · ·+ 1
n(n+ 1)
=
n
n+ 1
. (3.3)
Observemos inicialmente que
P (1) :
1
1.2
=
1
1 + 1
é verdadeira.
Suponhamos que, para algum n, tem-se que P (n) é verdadeira, ou seja,
que a fórmula (1.3) seja verdadeira para esse valor de n. Somando a ambos os
lados dessa igualdade
1
(n+ 1)(n+ 2)
, temos que
1
1.2
+
1
2.3
+ · · ·+ 1
n(n+ 1)
+
1
(n+ 1)(n+ 2)
=
n
n+ 1
+
1
(n+ 1)(n+ 2)
=
n+ 1
n+ 2
,
mostrando, assim, que P (n+ 1) é verdadeira.
7
Unidade 3 O Poder do Método de Indução
Portanto, pelo Princípio de Indução Matemática, temos que a fórmula vale
para todo n ∈ N.
A seguir, vamos estabelecer, por meio de indução, as propriedades usuais
das potências.
Proposição 4 Sejam a, b ∈ A e m,n ∈ N. Então,
i) am · an = an+m.
ii) (am)n = amn.
iii) (a · b)n = an · bn.
Demonstração Provaremos (i), deixando o restante como exercício.
Fixemos a ∈ A e m ∈ N, arbitrariamente. Demonstremos a propriedade
por indução sobre n.
Para n = 1, a propriedade é válida, pois, pelas de�nições,
am · a1 = am · a = am+1.
Por outro lado, supondo que am · an = am+n, temos que
am · an+1 = am · (an · a) = (am · an) · a = am+n · a = am+n+1.
Isso, pelo Princípio de Indução Matemática, prova a nossa propriedade.
Exemplo 5 Utilizando a noção de potência e de suas propriedades, mostraremos que 3
divide 5n + 2 · 11n nos inteiros, para todo n ∈ N.
De fato, para n = 1, temos que 3 divide 51 + 2 · 111 = 27.
Suponha, agora, que, para algum n ≥ 1, saibamos que 3 divide 5n+2 ·11n.
Logo, existe um número inteiro a tal que
5n + 2 · 11n = 3a.
Mutiplicando por 5 ambos os lados da igualdade acima, temos
5 · 3a = 5n+1 + 5 · 2 · 11n = 5n+1 + 2 · 11 · 11n − 12 · 11n.
8
Unidade 3O Princípio de Indução Matemática
Daí segue-se a igualdade
5n+1 + 2 · 11n+1 = 5 · 3a+ 12 · 11n,
cujo segundo membro é divisível por 3, por ser igual a 3(5a+ 4 · 11n).
Assim, provamos que 3 divide 5n+1 + 2 · 11n+1, o que, pelo Princípio de
Indução Matemática, acarreta que 3 divide 5n + 2 · 11n, para todo número
natural n.
Pode ocorrer que uma determinada propriedade seja válida para todos os
números naturais a partirde um determinado valor a, mas não necessariamente
para valores menores. Como proceder nesses casos? Por exemplo, como provar
que a desigualdade 2n > n2 é verdadeira para todo valor de n natural maior ou
igual do que 5? Fazemos isso baseados na seguinte pequena generalização do
Princípio de Indução Matemática:
Teorema 1Seja P (n) uma sentença sobre N, e seja a ∈ N. Suponha que:
(i) P (a) é verdadeira, e
(ii) qualquer que seja n ∈ N, com n ≥ a, sempre que P (n) é verdadeira,
segue-se que P (n+ 1) é verdadeira.
Então, P (n) é verdadeira para todo número natural n ≥ a.
DemonstraçãoDe�na o conjunto
S = {m ∈ N; P (m+ a− 1) }.
Por (i) temos que 1 ∈ S. Por outro lado, se m ∈ S, temos que P (m + a −
1) é verdadeira. Logo, por (ii), P (m + 1 + a − 1) é verdadeira. Portanto,
m+ 1 ∈ S. Em vista do Princípio de Indução Matemática, temos que S = N.
Consequentemente, P (n) é verdadeira para todo n ≥ a.
Exemplo 6Vamos mostrar que a desigualdade na sentença P (n) : 2
n > n2 é verdadeira,
para todo número natural n ≥ 5.
9
Unidade 3 O Poder do Método de Indução
Note que P (1) : 21 > 12 é verdadeira, P (2) : 22 > 22 é falsa, P (3) : 23 > 32
é falsa e P (4) : 24 > 42 é falsa. Tudo isso não importa, pois queremos veri�car
a veracidade dessa desigualdade para n ≥ 5.
De fato, temos que P (5) : 25 > 52 é verdadeira. Seja n ≥ 5 tal que
2n > n2. Multiplicando ambos os lados da desigualdade acima por 2, obtemos
2n+1 > 2n2. Note que 2n2 > (n + 1)2, se n ≥ 3, pois tal desigualdade é
equivalente a n(n − 2) > 1. Daí, deduzimos que 2n+1 > (n + 1)2, o que
signi�ca que P (n + 1) é verdadeira, estabelecendo o resultado em vista do
Teorema 1.
Exemplo 7 Um banco tem um suprimento ilimitado de notas de 3 e de 5 (unidades de
moeda). Mostre que ele pode pagar qualquer quantia (de unidades de moeda)
maior do que 7.
Para isto, basta mostrar que a sentença:
P (n) : A equação 3x+ 5y = n tem solução em (N ∪ {0})× (N ∪ {0}),
é verdadeira para todo n ≥ 8.
De fato, ela é verdadeira para n = 8, pois a equação 3x+ 5y = 8 admite a
solução (x, y) = (1, 1).
Suponha agora que a equação 3x + 5y = n tenha uma solução (a, b) para
algum n ≥ 8; isto é, 3a + 5b = n. Note que, para qualquer solução (a, b),
devemos ter a ≥ 1 ou b ≥ 1.
Se b ≥ 1, observando que 3× 2− 5× 1 = 1, segue que
3(a+ 2) + 5(b− 1) = 3a+ 5b+ 3× 2− 5× 1 = 3a+ 5b+ 1 = n+ 1,
o que mostra que a equação 3x + 5y = n + 1 admite a solução (a + 2, b− 1)
em (N ∪ {0})× (N ∪ {0}).
Se, por acaso, b = 0, então, a ≥ 3; usando a igualdade −3× 3+5× 2 = 1,
temos
3(a− 3) + 5× 2 = 3a− 3× 3 + 5× 2 = 3a+ 5b+ 1 = n+ 1,
o que mostra que a equação 3x + 5y = n + 1 admite a solução (a− 3, b + 2)
em (N ∪ {0})× (N ∪ {0}).
10
Unidade 3O Princípio de Indução Matemática
Mostramos assim, que, em qualquer caso, a equação 3x+5y = n+1 admite
solução, sempre que a equação 3x+5y = n, para algum n ≥ 8, tenha solução.
Como o resultado vale para n = 8, segue a conclusão desejada pelo Teorema 1.
Note que n0 = 8 é o menor valor de n para o qual a equação tem solução
para todo n ≥ n0.
11
Unidade 3 Exercícios Recomendados
3.3 Exercícios Recomendados
1. Mostre, por indução, a validez das seguintes fórmulas:
(a) 1.20 + 2.21 + 3.22 + · · ·+ n.2n−1 = 1 + (n− 1)2n;
(b)
(
1 +
1
1
)(
1 +
1
2
)2
· · ·
(
1 +
1
n− 1
)n−1
=
nn−1
(n− 1)!
,
(c) 1.1! + 2.2! + 3.3! + · · ·+ n.n! = (n+ 1)!− 1.
2. Sejam a e b números reais distintos. Mostre que, para todo n ∈ N, vale
a igualdade:
bn + abn−1 + a2bn−2 + · · ·+ an−1b+ an = b
n+1 − an+1
b− a
.
3. Se senα 6= 0, mostre que, para todo n ∈ N, vale a igualdade:
cosα · cos 2α · cos 22α · · · cos 2nα = sen 2
n+1α
2n+1 senα
.
Sugestão: Use a fórmula sen 2β = 2 sen β cos β.
4. Para todo n ∈ N, mostre que, nos inteiros,
(a) 80 divide 34n − 1;
(b) 9 divide 4n + 6n− 1;
(c) 8 divide 32n + 7;
(d) 9 divide n4n+1 − (n+ 1)4n + 1.
5. Mostre que
(a) n! > 2n, se n ≥ 4;
(b) n! > 3n,se n ≥ 7;
(c) n! > 4n, se n ≥ 9.
6. Prove que, para todo n natural, vale a desigualdade:
1
2
· 3
4
· 5
6
· · · 2n− 1
2n
≤ 1√
3n+ 1
.
12
Unidade 3O Princípio de Indução Matemática
7. Mostre que o número de diagonais de um polígono convexo de n lados é
dado por
dn =
n(n− 3)
2
.
3.4 Exercícios Suplementares
1. Mostre que n0 = 32 é o menor valor para o qual a equação 5x+ 9y = n
possui solução em (N ∪ {0})2 para todo n ≥ n0.
2. Prove que, para qualquer número natural n:
a) n3 + (n+ 1)3 + (n+ 2)3 é divisível por 9;
b) 32n+2 + 8n− 9 é divisível por 16;
c) 4n + 15n− 1 é divisível por 9;
d) 11n+2 + 122n+1 é divisível por 133;
e) 23
n
+ 1 é divisível por 3n+1.
3. Prove que:
a) 2n > n, onde n é um número natural arbitrário;
b)
1 · 3 · 5 · · · (2n− 1)
2 · 4 · 6 · · · 2n
≤ 1√
2n+ 1
, para qualquer n ∈ N;
c)
1
n+ 1
+
1
n+ 2
+ · · ·+ 1
2n
>
13
24
, se n ∈ N e n ≥ 2.;
d) 2n > 1 + n
√
2n−1, se n ∈ N e n ≥ 2.
4. Suponha que x+ 1
x
seja um número natural. Prove que xn+ 1
xn
é também
um número natural, qualquer que seja o número natural n.
5. Mostre que o número 111 . . . 1 (formado por 3n algarismos iguais a 1) é
divisível por 3n.
Sugestão: Para o passo indutivo, divida o número escrito com 3n+1
algarismos iguais a 1 pelo número formado por 3n algarismos iguais a 1
e veri�que que o resultado é um número divisível por 3.
13
Unidade 3 Textos Complementares
3.5 Textos Complementares
Para Saber Mais Comentário
Note que, na argumentação acima, poderia parecer que estamos usando
o fato de P (n) ser verdadeira para deduzir que P (n + 1) é verdadeira para
em seguida concluir que P (n) é verdadeira. O que está ocorrendo? Estamos
usando a tese para provar o resultado?
A resposta é não! Preste bem atenção, pois essa é a parte mais delicada de
toda a trama.
Dado um número natural n, temos duas possibilidades:
(a) P (n) é verdadeira, ou (b) P (n) é falsa.
A hipótese (ii) do Princípio não exige em absoluto que assumamos P (n)
verdadeira para todo n ∈ N, podendo eventualmente ser falsa para algum valor
de n, ou mesmo para todos os valores de n. O que a hipótese (ii) exige é
que sempre que algum n pertença à categoria (a), acima, então n+1 também
pertença a essa mesma categoria; não exigindo nada quando n pertencer à
categoria (b).
Por exemplo, a sentença P (n) : n = n+1 satisfaz (por vacuidade) a hipótese
(ii) do Princípio, já que nenhum n ∈ N pertence à categoria (a). O que falha
para que o Princípio de Indução nos garanta que P (n) é verdadeira para todo
n é que a hipótese (i) não é veri�cada, pois P (1) : 1 = 2 é falsa!
14
Unidade 3O Princípio de Indução Matemática
Para Saber MaisIndução Empírica vs Indução Matemática
É preciso ter clareza que a Indução Matemática é diferente da indução
empírica das ciências naturais, em que é comum, após um certo número de
experimentos, necessariamente �nito, enunciar leis gerais que governam o fenô-
meno em estudo. Essas leis são tidas como verdades, até prova em contrário.
Na matemática, não há lugar para a�rmações �verdadeiras até prova em con-
trário�. A Prova por Indução Matemática trata de estabelecer que determinada
sentença sobre os naturais é sempre verdadeira.
A indução empírica foi batizada, de modo irônico, pelo matemático, �lósofo
e grande humanista inglês do século passado, Bertrand Russel (1872-1970), de
indução galinácea, com base no seguinte conto:
Havia uma galinha nova no quintal de uma velha senhora. Diariamente,
ao entardecer, a boa senhora levava milho às galinhas. No primeiro dia, a
galinha, descon�ada, esperou que a senhora se retirasse para se alimentar. No
segundo dia, a galinha, prudentemente, foi se alimentando enquanto a senhora
se retirava. No nonagésimo dia, a galinha, cheia de intimidade, já não fazia
caso da velha senhora. No centésimo dia, ao se aproximar a senhora, a galinha,
por indução, foi ao encontro dela para reclamar o seu milho. Qual não foi a
sua surpresa quando a senhora pegou-a pelo pescoço com a intenção de pô-la
na panela.
15
Unidade 3 Textos Complementares
Na Sala de Aula Considerações sobre o Rigor
Neste curso, o nossoobjetivo é mostrar como se pode estabelecer um maior
padrão de rigor no tratamento de problemas matemáticos que ocorrem no En-
sino Médio, mas isso não deve ser tomado ao pé da letra na sua prática docente.
Certos argumentos informais, quando acompanhados de um raciocínio correto,
são corriqueiramente aceitos. Por exemplo, o argumento utilizado por Gauss
para somar os n primeiros números naturais é perfeitamente aceitável. Por-
tanto, um conselho: use o formalismo para ajudar e não para atrapalhar e
nunca o deixe se sobrepor à criatividade, pois, via de regra, primeiro vem a
descoberta para depois vir a formalização. Procure estimular sempre os seus
alunos a serem criativos. Num primeiro momento, deixe as ideias �uirem, só
depois preocupe-se com a sua organização e formalização.
16
4
1
Aplicações do Princípio de
Indução Matemática
Sumário
4.1 Exercícios Recomendados . . . . . . . . . . . . . . . 9
4.2 Exercícios Suplementares . . . . . . . . . . . . . . . 9
4.3 Textos Complementares . . . . . . . . . . . . . . . . 11
Unidade 4
Apresentaremos nesta unidade algumas aplicações lúdicas do Princípio de
Indução Matemática ao mundo material.
Exemplo 1 [A Torre de Hanói]
Você provavelmente já conhece esse jogo bastante popular e que pode ser
facilmente fabricado ou ainda encontrado em lojas de brinquedos de madeira.
O jogo é formado por n discos de diâmetros distintos com um furo no
seu centro e uma base onde estão �ncadas três hastes. Numa das hastes,
estão en�ados os discos, de modo que nenhum disco esteja sobre um outro de
diâmetro menor (veja �gura abaixo).
�� ���� ���� ���� ��
�� ��
Figura 1
O jogo consiste em transferir a pilha de discos para uma outra haste, des-
locando um disco de cada vez, de modo que, a cada passo, a regra acima seja
observada.
As perguntas naturais que surgem são as seguintes:
1. O jogo tem solução para cada n ∈ N?
2. Em caso a�rmativo, qual é o número mínimo jn de movimentos para
resolver o problema com n discos?
Usando Indução Matemática, vamos ver que a resposta à primeira pergunta
é a�rmativa, qualquer que seja o valor de n. Em seguida, deduziremos uma
fórmula que nos fornecerá o número jn.
Considere a sentença
P (n) : O jogo com n discos tem solução.
2
Unidade 4Aplicações do Princípio de Indução Matemática
Obviamente, P (1) é verdade. Suponha que P (n) seja verdadeiro, para
algum n; ou seja, que o jogo com n discos tem solução. Vamos provar que o
jogo com n+ 1 discos tem solução.
Para ver isso, resolva inicialmente o problema para os n discos superiores da
pilha, transferindo-os para uma das hastes livre (isso é possível, pois estamos
admitindo que o problema com n discos possua solução):
�� �� �� ���� ���� ���� ��
�� ��
Figura 2
Em seguida, trans�ra o disco que restou na pilha original (o maior dos
discos) para a haste vazia:
�� �� �� ���� ���� ���� ��
�� ��
Figura 3
Feito isto, resolva novamente o problema para os n discos que estão juntos,
transferindo-os para a haste que contém o maior dos discos:
�� ���� ���� ���� ��
�� ���� ��
Figura 4
Isso mostra que o problema com n + 1 discos também possui solução, e,
portanto, por Indução Matemática, que P (n) é verdadeira para todo n ∈ N.
3
Unidade 4
Para determinar uma fórmula para jn, veja que, para resolver o problema
para n + 1 discos com o menor número de passos, temos, necessariamente,
que passar duas vezes pela solução mínima do problema com n discos. Temos,
então, que
jn+1 = 2jn + 1.
Obtemos, assim, uma sequência (jn) de�nida recorrentemente. Pode-se
mostrar, sem di�culdade, por indução, que seu termo geral é dado por
jn = 2
n − 1.
(Este tipo de sequências, as recorrências, será estudado de modo sistemático
nas Unidades U7 e U8.)
+ Para Saber Mais - Origem da Torre de Hanói - Clique para ler
Exemplo 2 [Os Coelhos de Fibonacci]
Trata-se do seguinte problema proposto e resolvido pelo matemático italiano
Leonardo de Pisa em seu livro Liber Abacci, de 1202:
Quot paria coniculorum in uno anno ex uno pario germinentur.
Como não se ensina mais latim nas escolas, aí vai uma tradução:
Quantos casais de coelhos descendem de um casal em um ano.
Leonardo passa a explicar o seu problema e a sua solução, como segue (com
adaptação nossa):
Um casal de coelhos recém-nascidos foi posto num lugar cercado. Deter-
minar quantos casais de coelhos ter-se-ão após um ano, supondo que, a cada
mês, um casal de coelhos produz outro casal e que um casal começa a procriar
dois meses após o seu nascimento.
Vamos organizar a nossa contagem na tabela a seguir.
4
Unidade 4Aplicações do Princípio de Indução Matemática
mês
número de casais
do mês anterior
número de casais
recém-nascidos
total
1o 0 1 1
2o 1 0 1
3o 1 1 2
4o 2 1 3
5o 3 2 5
6o 5 3 8
7o 8 5 13
8o 13 8 21
9o 21 13 34
10o 34 21 55
11o 55 34 89
12o 89 55 144
Portanto, o número de casais de coelhos em um determinado mês é igual ao
número total de casais do mês anterior acrescido do número de casais nascidos
no mês em curso, que é igual ao número total de casais do mês anterior ao
anterior.
Se denotarmos o número de coelhos existentes no n-ésimo mês por un,
temos, então, que
un = un−1 + un−2, u1 = u2 = 1.
Essas relações de�nem, por recorrência, uma sequência de números naturais,
chamada de sequência de Fibonacci, cujos elementos, chamados de números de
Fibonacci, possuem propriedades aritméticas notáveis, que ainda hoje são objeto
de investigação.
+ Para Saber Mais - O que é uma Recorrência? - Clique para ler
+ Para Saber Mais - Leonardo de Pisa - Fibonacci - Clique para ler
5
Unidade 4
Exemplo 3 [O Enigma do Cavalo de Alexandre]
Num mosaico romano, Bucéfalo, o cavalo de Alexandre, o Grande, é repre-
sentado como um fogoso corcel cor de bronze. Nesse exemplo, vamos �provar�
que isso é uma falácia (uma grande mentira).
Inicialmente, �provaremos� que todos os cavalos têm mesma cor. De fato,
considere a sentença:
P (n) : Num conjunto com n cavalos, todos têm a mesma cor.
Note que P (1) é obviamente verdadeira. Agora, suponha o resultado válido
para conjuntos contendo n cavalos. Considere um conjunto
C = {C1, C2, . . . , Cn, Cn+1}
com n+ 1 cavalos. Decompomos o conjunto C numa união de dois conjuntos:
C = C ′ ∪ C ′′ = {C1, . . . , Cn} ∪ {C2, . . . , Cn+1},
cada um dos quais contém n cavalos.
Pela hipótese indutiva, segue-se que os cavalos em C ′ têm mesma cor, ocor-
rendo o mesmo para os cavalos em C ′′. Como
C2 ∈ C ′ ∩ C ′′,
segue-se que os cavalos de C ′ têm a mesma cor dos cavalos de C ′′, permitindo
assim concluir que todos os cavalos em C têm a mesma cor.
Assim, a nossa �demonstração� por indução está terminada, provando que
P (n) é verdadeira para todo n ∈ N.
Agora, todo mundo sabe (você sabia?) que Marengo, o famoso cavalo de
Napoleão, era branco. Logo, Bucéfalo deveria ser branco.
Onde está o erro nessa prova?
Sugestão: Para achá-lo, sugerimos que você tente provar que, se P (1) é
verdadeira, então P (2) é verdadeira.
Esse problema foi inventado pelo matemático húngaro George Polya (1887-
1985).
6
Unidade 4Aplicações do Princípio de Indução Matemática
Exemplo 4[Descobrindo a Moeda Falsa]
Têm-se 3n moedas de ouro, sendo uma delas falsa, com peso menor do
que as demais. Dispõe-se de uma balança de dois pratos, sem nenhum peso.
Vamos mostrar, por indução sobre n, que é possível achar a moeda falsa com
n pesagens.
Para n = 1, isso é fácil de ver, pois, dadas as três moedas, basta pôr uma
moeda em cada prato da balança e descobre-se imediatamente qual é a moeda
falsa.
Suponha, agora, que o resultado seja válido para algum valor de n e que se
tenha que achar a moeda falsa dentre 3n+1 moedas dadas. Separemos as 3n+1
moedas em 3 grupos de 3n moedas cada. Coloca-se um grupo de 3n moedas
em cada prato da balança. Assim, poderemos descobrir em que grupo de 3n
moedas encontra-se a moeda falsa. Agora, pela hipótese de indução, descobre-
se a moeda falsa com n pesagens, que, junto com a pesagem já efetuada,
perfazem o total de n+ 1 pesagens.Exemplo 5[A Pizza de Steiner]
O grande geômetra alemão Jacob Steiner (1796-1863) propôs e resolveu,
em 1826, o seguinte problema:
Qual é o maior número de partes em que se pode dividir o plano com n
cortes retos?
Pensando o plano como se fosse uma grande pizza, temos uma explicação
para o nome do problema.
Denotando o número máximo de pedaços com n cortes por pn, vamos provar
por indução a fórmula:
pn =
n(n+ 1)
2
+ 1.
Para n = 1, ou seja, com apenas um corte, é claro que só podemos obter
dois pedaços. Portanto, a fórmula está correta, pois
p1 =
1(1 + 1)
2
+ 1 = 2.
Admitamos agora que, para algum valor de n, a fórmula para pn esteja
correta. Vamos mostrar que a fórmula para pn+1 também está correta.
7
Unidade 4
Suponhamos que, com n cortes, obtivemos o número máximo n(n+1)/2+1
de pedaços e queremos fazer mais um corte, de modo a obter o maior número
possível de pedaços.
Vamos conseguir isso se o (n + 1)-ésimo corte encontrar cada um dos n
cortes anteriores em pontos que não são de interseção de dois cortes (faça um
desenho para se convencer disso).
Por outro lado, se o (n+1)-ésimo corte encontra todos os n cortes anteriores,
ele produz n + 1 novos pedaços: o corte começa em um determinado pedaço
e, ao encontrar o primeiro corte, ele separa em dois o pedaço em que está,
entrando em outro pedaço. Ao encontar o segundo corte, ele separa em dois o
pedaço em que está, entrando em outro pedaço, e assim sucessivamente, até
encontrar o n-ésimo corte separando o último pedaço em que entrar em dois.
Assim, são obtidos n+ 1 pedaços a mais dos que já existiam; logo,
pn+1 = pn + n+ 1 =
n(n+ 1)
2
+ 1 + n+ 1 =
(n+ 1)(n+ 2)
2
+ 1,
mostrando que a fórmula está correta para n + 1 cortes. O resultado segue
então do Princípio de Indução Matemática.
8
Unidade 4Aplicações do Princípio de Indução Matemática
4.1 Exercícios Recomendados
1. Prove que, qualquer que seja o número natural n maior do que 3, existe
um polígono convexo com n lados e exatamente 3 ângulos agudos.
2. Um plano está dividido em regiões por várias retas. Prove que é pos-
sível colorir essas regiões com duas cores de modo que quaiquer duas
regiões adjacentes tenham cores diferentes (dizemos que duas regiões são
adjacentes se elas tiverem pelo menos um segmento de reta em comum).
3. A sequência (an) é de�nida pelos dados: a1 = 1, a2 = 2, an+1 = an−an−1
se n > 2. Prove que an+6 = an para todos os números naturais n.
Descreva todos os termos dessa sequência.
4. A sequência a1, a2, . . . , an, . . . de números é tal que a1 = 3, a2 = 5 e
an+1 = 3an − 2an−1 para n > 2. Prove que an = 2n + 1 para todos os
números naturais n.
4.2 Exercícios Suplementares
1. Ache o erro na �prova� do seguinte
�Teorema� Todos os números naturais são iguais.
Vamos provar o resultado mostrando que, para todo n ∈ N, é verdadeira
a sentença
P (n) : : dado n ∈ N, todos os número naturais menores ou iguais do
que n são iguais.
(i) P (1) é claramente verdadeira.
(ii) Suponha que P (n) seja verdadeira, logo n − 1 = n. Somando 1 a
ambos os lados dessa igualdade, obtemos n = n + 1. Como n era igual
a todos os naturais anteriores, segue que P (n+ 1) é verdadeira.
Portanto, P (n) 'e vedadeira para todo n ∈ N .
2. (O queijo de Steiner) Para fazer a sua pizza, Steiner teve que cortar,
primeiro, o queijo. Imaginando que o espaço é um enorme queijo, você
9
Unidade 4 Exercícios Suplementares
seria capaz de achar uma fórmula para o número máximo de pedaços que
poderíamos obter ao cortá-lo por n planos?
3. Mostre que a sequência de Fibonacci satisfaz às seguintes identidades:
(a) u1 + u2 + · · ·+ un = un+2 − 1.
(b) u1 + u3 + · · ·+ u2n−1 = u2n.
(c) u2 + u4 + · · ·+ u2n = u2n+1 − 1.
(d) u21 + u
2
2 + · · ·+ u2n = unun+1.
4. Sabendo que q =
1 +
√
5
2
é raiz da equação x2 = x + 1, mostre que
qn = unq + un−1.
5. Prove que
u3 + u6 + u9 + · · ·+ u3n =
u3n+2 − 1
2
.
6. Dada a recorrência an+2 = 2an+1 + an, com a1 = 1 e a2 = 3, ache uma
fórmula para an.
10
Unidade 4Aplicações do Princípio de Indução Matemática
4.3 Textos Complementares
Para Saber MaisOrigem da Torre de Hanói
Esse jogo foi idealizado e publicado pelo matemático francês Edouard Lucas,
em 1882, que, para dar mais sabor à sua criação, inventou a seguinte �lenda�:
Na origem do tempo, num templo oriental, uma Divindade colocou 64 discos
perfurados de ouro puro ao redor de uma de três colunas de diamante e ordenou
a um grupo de sacerdotes que movessem os discos de uma coluna para outra,
respeitando as regras acima explicadas. A Divindade sentenciou que, quando
todos os 64 discos fossem transferidos para uma outra coluna, o mundo acabaria.
Você não deve se preocupar com a iminência do �m do mundo, pois, se,
a cada segundo, um sacerdote movesse um disco, o tempo mínimo para que
ocorresse a fatalidade seria de 264− 1 segundos e isto daria, aproximadamente,
um bilhão de séculos!
11
Unidade 4 Textos Complementares
Para Saber Mais O que é uma Recorrência?
Uma recorrência é uma fórmula que de�ne um elemento de uma sequência
a partir de termos anteriores.
Uma recorrência do tipo:
xn = xn−1 + xn−2, (4.1)
só permite determinar o elemento xn se conhecermos os elementos anteriores
xn−1 e xn−2, que, para serem calculados, necessitam do conhecimento dos dois
elementos anteriores, e assim por diante. Fica, portanto, univocamente de�nida
a sequência quando são dados x1 e x2. A sequência de Fibonacci corresponde
à recorrência (4.1), onde x1 = x2 = 1.
Quando é dada uma recorrência, um problema importante é determinar uma
fórmula fechada para o termo geral da sequência, isto é, uma fórmula que não
recorre aos termos anteriores. No caso da sequência de Fibonacci, existe uma
tal fórmula, chamada fórmula de Binet, que apresentamos a seguir e que será
demonstrada em um contexto mais geral na Unidade 8.
Para todo n ∈ N, tem-se que
un =
(
1+
√
5
2
)n
−
(
1−
√
5
2
)n
√
5
É notável que seja necessário recorrer a fórmulas envolvendo números ir-
racionais para representar os elementos da sequência de Fibonacci, que são
números naturais. Mais notável, ainda, é que o número ϕ =
1 +
√
5
2
seja a
proporção áurea que aparece nas artes, e que
1−
√
5
2
= −ϕ−1 seja o simétrico
de seu inverso. Intrigante essa inesperada relação entre criar coelhos e a divina
proporção, não?
12
Unidade 4Aplicações do Princípio de Indução Matemática
Para Saber MaisLeonardo de Pisa - Fibonacci
Leonardo de Pisa (1170-1250), �lho de Bonacci, e por isso apelidado Fi-
bonacci, teve um papel fundamental no desenvolvimento da Matemática no
Ocidente. Em 1202, publicou o livro Liber Abacci, que continha grande parte
do conhecimento sobre números e álgebra da época. Esta obra foi responsável
pela introdução na Europa do sistema de numeração indo-arábico e pelo pos-
terior desenvolvimento da álgebra e da aritmética no mundo ocidental.
13
Unidade 4 Textos Complementares
14
5
1
Progressões Aritméticas
Sumário
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2
5.2 Primeiros Exemplos . . . . . . . . . . . . . . . . . . 2
5.3 Soma dos Termos de uma PA . . . . . . . . . . . . 6
5.4 Somas Polinomiais . . . . . . . . . . . . . . . . . . . 9
5.5 Exercícios Recomendados . . . . . . . . . . . . . . . 14
5.6 Exercícios Suplementares . . . . . . . . . . . . . . . 16
5.7 Textos Complementares . . . . . . . . . . . . . . . . 20
Unidade 5 Introdução
5.1 Introdução
As Progressões Aritméticas (PA) constituem-se na família mais simples de
sequências de�nidas recorrentemente. Elas são comuns na vida real e sempre
aparecem quando se apresentam grandezas que sofrem variações iguais em in-
tervalos de tempos iguais como, por exemplo, no cálculo de juros simples, ou
desvalorização de um bem ao longo do tempo.
Nessa unidade, você encontrará também a fórmula que fornece a soma dos
n primeiros termos de uma PA, fórmula que generaliza a que foi descoberta por
Gauss, quando menino, conforme vimos na Unidade 3.
Em seguida, são de�nidas generalizações do