MA12 - Matemática Discreta 2014 - LIVRO

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 figuras 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 definição matemática, pois faz uso de idéias (como grandeza,
unidade, discreta, contínua) e processos (como comparação) de significado 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 definiçã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 definiçã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 Definições e axiomas - Cli-
que para ler
Unidade 1
Números Naturais
+ Na Sala de Aula - Reflexõ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 significar �três vezes� como �muito�
ou �extremamente�.
As necessidades provocadas por um sistema social cada vez mais complexo
e as longas reflexçõ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 significa 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
definição. O termo primitivo �sucessor� não é definido 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 afirmaçõ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 eficiente 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 1
Nú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 definidas 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 definiçã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 significados
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 definidas 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á definida 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 significar que existe algum p ∈ N tal que n = m + p. (Isto querdizer
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 significa que existe um elementom0 ∈ 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 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,
6
Unidade 1
Nú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 afirmar 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 1
Nú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 quem+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 Reflexõ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: �infinito é um número muito
grande�. Para outro exemplo, vide RPM 29, págs. 13-19.
2. Não insistir em detalhes formais para justificar afirmaçõ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 1
Nú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 afins 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çãoNã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áficas) 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 definições:
�Unidade é aquilo pelo qual cada objeto é um. Número é uma multitude de
unidades�.
12
Unidade 1
Números Naturais
Para Saber MaisComentários sobre Definições e axiomas
Uma definiçã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
definições, como exemplo.
• Ângulo é a figura 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 definiçõ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 definições de ângulo e de números primos entre si, dadas acima, bem
como as definiçõ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 definiçõ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 definição faz uso de termos
específicos, os quais foram definidos usando outros termos, e assim sucessiva-
mente. Este processo iterativo leva a três possibilidades:
a) Continua indefinidamente, cada definição dependendo de outras anteriores,
sem nunca chegar ao fim.
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 definidas, 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 definiçã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 definem,
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 definidas e as
afirmaçõ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 1
Nú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 ficar 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 significado.
Cada um desses objetos (um número natural) possui apenas um lugar determi-
nado nesta sequência. Nenhuma outra propriedade lhe serve de definiçã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 1
Nú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 suficiente-
mente a operação de tomar o sucessor de um número. Ele está presente (pelo
menos de forma implícita) sempre que, ao afirmarmos a veracidade de uma pro-
posição referente aos números naturais, verificamos 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 final destecapí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, definida 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, fizermos corresponder o
número real f(t) = área do triângulo t, obteremos uma função f : X → R.
2
Unidade 2
Números Cardinais
Exemplo 2
Sejam 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) define uma função g : S → ∆.
Exemplo 3
A correspondência que associa a cada número natural n seu sucessor n+ 1
define 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 definir 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
define 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 define uma função f : X → Y
porque é ambígua: dado o número x > 0, existe uma infinidade 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 2
Números Cardinais
Exemplo 6
Sejam X = {1, 2, 3, 4, 5} e Y = {2, 4, 6, 8, 10}. Definindo 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 7
Um 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 8
Sejam 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 . Defina 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 definir 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 2
Números Cardinais
Exemplo 10
Sejam 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 é finito, 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. Pondof(1) = x1, f(2) =
x2, . . . , f(n) = xn, podemos escrever X = {x1, x2, . . . , xn}. Para todo n, o
conjunto In é finito e seu número cardinal é n. Assim, todo número natural n
é o número cardinal de algum conjunto finito.
A fim de evitar exceções, admite-se ainda incluir o conjunto vazio ∅ entre
os conjuntos finitos e diz-se que ∅ tem zero elementos. Assim, por definição,
zero é o número cardinal do conjunto vazio.
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 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 finito, com 5 elementos. O
conjunto N dos números naturais é infinito. Com efeito, dada qualquer função
f : In → N , não importa qual n se fixou, 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
definição de correspondência biunívoca.
O número cardinal de um conjunto finito 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 finito é o mesmo, seja qual for
a contagem que se adote. Isto significa 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 finito X é finito e n(Y ) ≤ n(X).
Tem-se n(Y ) = n(X) somente quando Y = X.
3. Se X e Y são finitos então X ∪Y é finito e tem-se n(X ∪Y ) = n(X) +
n(Y )− n(X ∩ Y ) .
4. Sejam X, Y conjuntos finitos. 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 fixar 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 osm 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 2
Números Cardinais
formamos o conjunto Y = {1, 2, . . . ,m− 1} e definimos 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 conjuntoX tais que f(x1) = f(x2).
Isto significa que x1 e x2 , quando divididos porm, 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 12
Vamos 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 significa que duas ou mais
pessoas ali têm o mesmo número de amigos entre os presentes.
+ Para Saber Mais - Sobre Conjuntos Infinitos - 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 finito 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 finitos, 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. Defina uma função sobrejetiva f : N → N tal que, para todo n ∈ N, a
equação f(x) = n possui uma infinidade 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 fila
com seus subconjuntos de tal modo que cada subconjunto da fila 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 infinita), cada um deles com infinitos
passageiros. Que deve fazer o gerente para hospedar todos?
10
Referências Bibliográficas
[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 fica 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 �, ficam subentendidos seu domínio X e seu contra-
domínio Y . Sem que eles sejam especificados, 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 define uma função
f : X → R ?� Novamente, a pergunta incorreta é mais simples de formular.
Se for feita assim, é preciso saber seu significado.
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 2
REFERÊ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 fim 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 justifique) a definição dada no dicionário mais
vendido do país. Em algumas situações, ocorrem em Matemática definições
do tipo seguinte: um vetor é o conjunto de todos os segmentos de reta do
plano que são equipolentes a um segmento dado. (Definiçã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 definiçã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 definiçã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 2
REFERÊNCIAS BIBLIOGRÁFICAS
Para Saber MaisSobre Conjuntos Infinitos
Para encerrar estas considerações a respeito de números cardinais, faremos
alguns comentários sobre conjuntos infinitos.
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 infinitos. Ele foi o primeiro a
descobrir que existem conjuntos infinitos 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 é finito, f é injetiva se, e somente se, é sobrejetiva (veja
a referência [Lima].) Mas isto não é verdadeiro para X infinito. Por exemplo,
se definirmos 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 infinidade 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, definidas 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 infinidade de quartos, numera-
dos consecutivamente, um para cada número natural. Todos eram igualmente
confortáveis. Num fim-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:
� Transfira 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 ficou sem saber o que fazer quando, horas depois, chegou um trem com
uma infinidade 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 infinitos quartos vazios e eu poderei
ter sossego por algum tempo.
16
Unidade 2
REFERÊNCIAS BIBLIOGRÁFICAS
Para Saber MaisCuidado!
Não confunda conjunto infinito com aquele que tem um número muito grande
(porém finito) de elementos. Quando, na linguagem comum, se diz algo como �-
Já ouvi isto uma infinidade de vezes�, trata-se de uma mera força de expressão.
Não há distâncias infinitas (mesmo entre duas galáxias bem afastadas) e até
o número de átomos do universo é finito. (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 definir com rigor objetos matemáticos e também como utilizá-lo como
poderoso instrumento para demonstrar os mais variados resultados envolvendonú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 significam 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 significado
das expressões acima, até mesmo no que diz respeito aos pontinhos que nelas
aparecem. Existe, contudo, um modo de tornar mais rigorosas definiçõ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 3
O Princípio de Indução Matemática
Para definir uma expressão En, para todo número natural n, basta definirmos
E1 e mostrar, para todo n ∈ N, como obter sem ambiguidade En+1 a partir de
En.
Nesse caso, dizemos que En foi definido por recorrência.
Vejamos como intervém o Princípio de Indução Matemática para justificar
este tipo de definição. Seja X o subconjunto de N, determinado pela condição:
n ∈ X ⇐⇒ En está definido.
Pela caracterização do conjunto X, temos que 1 ∈ X e, para todo n ∈ N,
n ∈ X ⇒ n+ 1 ∈ X. Portanto, X = N.
Definições por recorrência podem ser utilizadas para dar um significado a
expressões como no início da unidade.
Exemplo 1
Definimos S1 = 1. Em seguida, supondo Sn definido, pomos
Sn+1 = Sn + (n+ 1).
Damos assim, um sentido matemático preciso à expressão:
Sn = 1 + 2 + · · ·+ n.
Por outro lado, definindo 1! = 1 e pondo (n+1)! = n!(n+1), supondo que
n! esteja definido, 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 definidas 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 Definem-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 definir 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 definição as potências de a.
Pela sua importância, destacamos essa definição a seguir.
4
Unidade 3
O 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 definidas
por recorrência como segue: a1 = a e an+1 = an · a.
Quando a 6= 0, convenciona-se definir 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 2
Neste 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 fechada
1
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
.
1
Uma 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 3
O 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 4
Vamos 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 queP (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 definiçõ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 3
O 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 1
Seja 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ção
Defina 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 6
Vamos mostrar que a desigualdade na sentença P (n) : 2n > 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 verificar
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
significa 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 3
O 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 3
O 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 verifique 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 é verificada, pois P (1) : 1 = 2 é falsa!
14
Unidade 3
O 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 finito, 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 afirmaçõ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, filó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, desconfiada, 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. 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 fluirem, 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 fincadas três hastes. Numa das hastes,
estão enfiados os discos, de modo que nenhum disco esteja sobre um outro de
diâmetro menor (veja figura abaixo).
�� ���� ���� ���� ��
�� ��
Figura 1
O jogo consiste em transferir a pilha de discos para uma outra haste, deslo-
cando 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 afirmativo, 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
é afirmativa, 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, transfira 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) definida recorrentemente. Pode-se
mostrar, sem dificuldade, 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 definem, 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) é definida 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 fim 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 define um elemento de uma sequência
a