Matemática para Ensino Superior MA12 - Atualizado 2014

Prévia do material em texto

MA 12 - Matemática Discreta Edição 2012 
Atualizado até Junho de 2014 
Marcos
Nota
MigrationConfirmed definida por Marcos
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 depreferê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
MA12 - Unidade 1
Números Naturais
Paulo Cezar Pinto Carvalho
PROFMAT - SBM
January 27, 2014
Os Números Naturais
Números Naturais: modelo abstrato para contagem.
N = {1, 2, 3, ...}
Uma descrição precisa e concisa de N é dada pelos Axiomas
de Peano.
Noção fundamental: a de sucessor de um número natural (ou
seja, o número que, intuitivamente, vem logo depois dele).
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 2/8
Os Axiomas de Peano
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 śı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.
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 3/8
O Axioma da Indução
O último dos axiomas de Peano é conhecido como Axioma da
Indução e é a base para um método de demonstração para
propriedades relativas aos números naturais (demonstrações
por indução).
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′ (ou n + 1) é o sucessor de n.
Então P(n) é válida qualquer que seja o número natural n.
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 4/8
Exemplo: uma demonstração por indução
Provar a validez, para todo número natural n, da igualdade
P(n) : 1 + 3 + 5 + . . . + (2n − 1) = n2
Para n = 1, P(1) se resume a afirmar 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,
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.
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 5/8
As Duas Operações: Adição e Multiplicação
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.
Quanto ao produto, põe-se n · 1 = n por definição e, quando
p 6= 1, np é a soma de p parcelas iguais a n.
Estas operações podem ser formalizadas usando indução.
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 6/8
Usando indução para definir as operações
Adição:
n + 1 = sucessor de n
n + (p + 1) = (n + p) + 1 .
Multiplicação:
n · 1 = n
n(p + 1) = np + n.
As propriedades destas operações (comutativa, associativa,
etc) podem ser demonstradas por indução.
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 7/8
A Ordenação nos Números Naturais
Dados m, n ∈ N, diz-se que m é menor do que n, e escreve-se
m < n, para significar que existe algum p ∈ N tal que
n = m + p.
Propriedades:
a) Se m < n e n < p então m < p.
b) Dados m, n ∈ N, vale uma, e somente uma, das alternativas:
m = n, m < n ou n < m.
c) Se m < n então, para qualquer p ∈ N, tem-se m + p < n + p e
mp < np.
d) (Propriedade da Boa Ordenação) Todo subconjunto não-vazio
X ⊂ N possui um menor elemento. Isto significa que existe um
elemento n0 ∈ X que é menor do que todos os demais
elementos de X .
PROFMAT - SBM MA12 - Unidade 1 , Números Naturais slide 8/8
Lista de Exerćıcios
Unidade 1
1. O diagrama abaixo, em que a seta indica o sucessor de cada elemento,
representa a estrutura dos números naturais imposta pelos axiomas de
Peano.
1 2 3 4 5 6 7 ...
Em cada um dos diagramas a seguir, exatamente um dos axiomas de
Peano é violado. Diga qual é ele.
a)
1 2 3 4 5 6 7 ...
b)
1 2 3 4 5 6 7 ...
c)
1 2 3 4 5 6 7 ...
d)
1 2 3 4 5 6 7 ...
2. Prove, por indução, que
1 + 22 + 32 + · · ·+ n2 = n(n + 1)(2n + 1)
6
.
3. Diga onde está o erro da seguinte demonstração da afirmativa
1 + 2 + 4 + 8 + . . . + 2n = 2n+1.
A propriedade é trivialmente válida para n = 1. Suponhamos que seja
válida para n, ou seja 1+2+4+8+. . .+2n = 2n+1. Então 1+2+4+8+
1
. . .+2n +2n+1 = 2n+1 +2n+1 = 2.2n+1 = 2n+2. Portanto, a propriedade
também é válida para n + 1. Logo, pelo Prinćıpio da Indução Finita,
1 + 2 + 4 + 8 + . . . + 2n = 2n+1 para todo n ∈.
4. Usando indução e a propriedade associativa da adição, demonstre a lei
do corte: ”Se m,n e p são números naturais tais que m + p = n + p,
então m = n. [Sugestão: use indução em p, notando que o caso base
da indução é o segundo axioma de Peano. ]
5. Demonstre a propriedade transitiva da ordem: Se m, n e p são números
naturais tais que m < n e n < p, então m < p.
2
Soluções da Lista de Exerćıcios
Unidade 1
1. a) O quarto axioma é violado. O subconjunto {1, 2, 5, 6, . . .} contém 1
e o sucessor de cada elemento, mas não é igual a N.
b) O terceiro axioma é violado. O elemento 2 também não é sucessor
de um natural.
c) O segundo e terceiro axiomas são violados. O número 3 é sucessor
de dois números diferentes e, além disso, 2 também não é sucessor de
nenhum natural.
d) O segundo axioma é violado. O número 2 é sucessor de dois números
diferentes (1 e 7).
2. A fórmula vale para n = 1, já que 12 = 1.2.3
6
.
Suponhamos que ela valha para um certo n, ou seja, 12 +22 +32 + · · ·+
n2 = n(n+1)(2n+1)
6
. Somando (n + 1)2 a ambos os lados da igualdade,
obtemos:
12 + 22 + 32 + · · ·+ n2 + (n + 1)2 = n(n+1)(2n+1)
6
+ (n + 1)2 =
(n+1)(2n2+n+6n+6)
6
= (n+1)(2n
2+7n+6)
6
= (n+1)(n+2)(2n+3)
6
Logo, a fórmula também é válida para n + 1. Portanto, pelo Prinćıpio
da Indução, a fórmula é válida para todo n natural.
3. Na verdade, a propriedade não vale para n = 1, já que 1 + 21 6= 21+1.
4. Para p = 1, a afirmativa vale pelo segundo axioma de Peano: se os
sucessores m + 1 e n + 1 de m e n são iguais, então m = n.
Suponhamos agora que a propriedade valha para algum natural p. Isto
é, m + p = n + p implique m = n. Suponhamos que m + (p + 1) =
n + (p + 1). Pela propriedade associativa da adição, a igualdade é
equivalente a (m+ 1) + p = (n+ 1) + p. Mas pela hipótese de indução,
isto implica m + 1 = n + 1, que por sua vez implica m = n (pelo caso
em que p = 1). Logo, se a propriedade vale para p então vale também
para p + 1.
1
Portanto, pelo Prinćıpio da Indução, a lei do corte vale para todo p
natural.
5. Suponhamos que m < n e n < p. Então, pela definição da ordem,
existem naturais r e s tais que m + r = n e n + s = p. Substituindo
a expressão de n fornecida pela primeira igualdade na segunda, temos
(m + r) + s = p, que é equivalente a m + (r + s) = p. Logo, m < p.
2
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 conjuntodos 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 objetosna 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
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 mesmo nú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íbeque 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
MA12 - Unidade 2
Números Cardinais
Paulo Cezar Pinto Carvalho
PROFMAT - SBM
February 17, 2014
Números cardinais
A importância dos números naturais provém do fato de que
eles constituem o modelo matemático que torna posśıvel o
processo de contagem.
Contar um conjunto X significa estabelecer uma
correspondência biuńıvoca entre os elementos de X e os de
um subconjunto de N da forma
In = {x ∈ N|x ≤ n} = {1, 2, . . . , n}.
Quando é posśıvel estabelecer tal correspondência biuńıvoca,
dizemos que X é um conjunto finito e que n é o número
cardinal ou número de elementos de X .
PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 2/7
Propriedades
a) O resultado da contagem (ou seja, o número cardinal de X ) é
sempre o mesmo, não importando a contagem que seja feita.
b) Todo subconjunto Y de um conjunto finito X é finito e
n(Y ) ≤ n(X ). Tem-se n(Y ) = n(X ) somente quando Y = X .
Observação: A fim de evitar exceções, o conjunto vazio ∅ é
inclúıdo entre os conjuntos finitos e diz-se que ∅ tem zero
elementos.
PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 3/7
Conjuntos Infinitos
Diz-se que um conjunto X é infinito quando ele não é finito.
Isto quer dizer que X não é vazio e que, não importa qual seja
n ∈ N , não existe correspondência biuńıvoca f : In → X .
Exemplo: o conjunto N dos números naturais é infinito.
Dada qualquer função f : In → N , não importa qual seja n ,
tomamos k = f (1) + f (2) + · · ·+ f (n).
Para todo x ∈ In, tem-se f (x) < k ; logo não existe x ∈ In tal
que f (x) = k .
Assim, f não pode ser uma correspondência biuńıvoca.
PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 4/7
Comparando conjuntos infinitos
Dois conjuntos X e Y têm a mesma cardinalidade quando é
posśıvel estabelecer uma correspondência biuńıvoca entre X e
Y (isto é, existe uma função bijetiva f : X → Y ).
Exemplo: os conjuntos N dos números naturais e
P = {2n|n ∈ N} dos números pares têm a mesma
cardinalidade.
A bijeção já está dada na definição de P: a função f : N→ P
definida por f (n) = 2n é uma bijeção de N em P.
Os conjuntos N e N× N dos pares de números naturais
também têm a mesma cardinalidade.
PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 5/7
Conjuntos enumeráveis
Um conjunto é enumerável quando é finito ou tem a mesma
cardinalidade de N.
Por exemplo, os conjuntos {2, 5}, N e N×N são enumeráveis.
PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 6/7
Um exemplo de conjunto não enumerável
Um conjunto infinito é necessariamente enumerável? NÃO!
O conjunto de todas as sequências em que os termos são 0 ou
1 não é enumerável.
Prova: o método da diagonal de Cantor.
Trocando o n-ésimo termo da n-ésima sequência produz-se
uma nova sequência que não está na enumeração proposta!
PROFMAT - SBM MA12 - Unidade 2 ,Números Cardinais slide 7/7
Lista de Exerćıcios
Unidade 2
1. Prove, por indução, que se X é um conjunto finito com n elementos,
esses elementos podem ser ordenados de n! modos.
2. Prove, por indução, que um conjunto com n elementos possui 2n sub-
conjuntos.
3. Dados 3n objetos de pesos iguais, exceto um, mais pesado que os de-
mais, mostre que é posśıvel determinar este objeto com n pesagens em
uma balança de pratos. Mostre também que este é o número mı́nimo de
pesagens que permitem, com certeza, determinar o objeto mais pesado.
4. Prove que, dado um conjunto com n elementos, é posśıvel fazer uma
fila com seus subconjuntos de tal modo que cada subconjunto da fila
pode ser obtido a partir do anteriorpelo acréscimo ou pela supressão
de um único elemento. [Sugestão: para passar de n para n + 1, liste
primeiro os subconjuntos que não têm um dado elemento.]
5. Diga onde está o erro na seguinte demonstração da afirmativa ”Todas
as bolas de bilhar têm a mesma cor”.
Seja P (n) a propriedade ”todas as bolas em um conjunto com n bolas
têm a mesma cor”. A propriedade é trivialmente verdadeira para n = 1.
Suponhamos agora que ela seja verdadeira para n e consideremos um
conjunto com n + 1 bolas B = {b1, b2, . . . , bn, bn+1}. Os subconjuntos
{b1, b2, . . . , bn, } e {b2, . . . , bn, bn+1} de B têm n elementos cada; logo,
pela hipótese de indução, todas as bolas em cada um deles têm a mesma
cor. Mas os elementos b2, . . . , bk são comuns a esses dois subconjuntos.
Dáı, conclúımos que todos os n + 1 elementos de B têm a mesma cor,
o que mostra que a propriedade vale para n + 1. Logo, pelo Prinćıpio
da Indução, em uma coleção com n bolas todas têm a mesma cor, para
todo n ∈ N.
6. Diga se cada conjunto abaixo é finito ou infinito, justificando:
• o conjunto de todas as pessoas que já viveram na Terra.
1
• o conjunto de todos os múltiplos de 7 cuja representação decimal
termina com 3578.
• o conjunto de todos os números naturais cuja representação de-
cimal tenha apenas algarismos diferentes de zero, cuja soma seja
menor que 1000.
• o conjunto de todos os números racionais que podem ser escritos
como fração com denominador menor que 1000.
• o conjunto de todos os números primos.
7. Sejam X e Y dois conjuntos infinitos enumeráveis. Isto significa que
existem sequências (x1, x2, x3, . . .) e (y1, y2, y3, . . .) incluindo todos os
elementos de X e Y , respectivamente. Explique como construir uma
sequência incluindo todos os elementos de X ∪Y , mostrando assim que
X ∪ Y também é enumerável.
8. Considere o conjunto N2 de todos os pares ordenados de números na-
turais. Encontre uma sequência que inclua todos os elementos de N2,
mostrando assim que N2 é enumerável. Isto mostra que o conjunto dos
números racionais também é enumerável. Por quê?
9. Mostre que o conjunto de todos os subconjuntos de N é não enumerável.
[Sugestão: associe cada subconjunto de N a uma sequência em que os
termos são iguais a 0 ou 1.]
2
Soluções da Lista de Exerćıcios
Unidade 2
1. Um conjunto com 1 elemento só pode ser ordenado de 1 = 1! modo,
o que mostra que a propriedade vale para n = 1. Suponhamos que ela
valha para n e consideremos um conjunto {a1, a2, . . . , an, an+1} com n+
1 elementos. As posśıveis ordenações desse conjunto podem ser obtidas
tomando cada uma das n! ordenações de {a1, a2, . . . , an} e inserindo
an+1 em uma das n + 1 posições posśıveis, gerando assim n!(n + 1) =
(n + 1)! posśıveis ordenações. Logo, a propriedade também vale para
n + 1. Portanto, pelo Prinćıpio da Indução, vale para todo n natural.
2. Neste caso, convém começar de n = 0, para o qual a propriedade
vale, já que o conjunto vazio possui 1 = 20 subconjunto. Suponha-
mos que a propriedade valha para n e consideremos um conjunto A =
{a1, a2, . . . , an, an+1} com n + 1 elementos. Cada subconjunto de A ou
é um subconjunto {a1, a2, . . . , an} ou é a união de um tal subconjunto
com an+1. Ou seja, cada subconjunto de {a1, a2, . . . , an} dá origem a 2
subconjuntos de A, que tem, assim, 2.2n = 2n+1 subconjuntos. Logo,
a propriedade também vale para n + 1. Portanto, pelo Prinćıpio da
Indução, vale para todo n ≥ 0.
3. Para n = 1, basta de fato uma pesagem, feita com dois dos objetos: se
ela indicar um objeto mais pesado do que o outro, ele é o procurado; se
os objetos tiverem pesos iguais, o objeto que ficou de fora na pesagem
é o mais pesado. Suponhamos agora que seja posśıvel determinar qual
é mais pesado dentre 3n objetos com n pesagens e consideremos um
conjunto com 3n+1 objetos. Dividimos estes objetos em três grupos
com 3n objetos cada e comparamos o peso de dois deles. Se um deles
for mais pesado, o objeto procurado está nele; senão, está no grupo
que ficou de fora da pesagem. De qualquer modo, pela hipótese de
indução, ele pode ser encontrado em n pesagens adicionais, para um
total de n+1 pesagens. Logo, a propriedade vale para conjuntos de 3n+1
objetos e, pelo Prinćıpio da Indução, para conjuntos com 3n objetos,
qualquer que seja n.
1
4. Finito, infinito, finito, finito, infinito
5. A sequência {x1, y1, x2, y2, x3, y3, . . .} inclui todos os elementos de X ∪
Y , que é, portanto, enumerável.
6. Um modo de construir tal sequência é ordenar os pares ordenados de
números naturais de acordo com a soma das coordenadas: primeiro, os
que têm soma 2, depois 3, e assim por diante, dando origem à sequência
{(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), . . .}, o que mostra que N × N é
enumerável. Cada par (m,n) corresponde aos números racionais −m
n
e m
n
. Logo, a partir dessa sequência podemos construir uma outra
sequência que inclui todos os números racionais, o que mostra que o
conjunto dos racionais também é enumerável.
7. Cada subconjunto X de N corresponde a uma sequência (xn) em que
xn = 1 se n ∈ X e xn = 0 caso contrário. Como o conjunto de tais
sequências é não enumerável, o conjunto de todos os subconjuntos de
N também é não enumerável.
2
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 do conjunto 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 partir de 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) qualquerque 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 nosso objetivo é 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.