Teoria dos números

Prévia do material em texto

GOD’S SOVEREIGN 
 1 Prof. Rubens Vilhena 
 
 
 
GOD’S SOVEREIGN 
 2 Prof. Rubens Vilhena 
 
 
 
 
 
 
 
 
 
Índice para catálogo sistemático 
 1. Teoria dos Números, 2ª ed: 511.68 
 
BELÉM – PARÁ – BRASIL 
- 2017 – 
 
Dados internacionais de Catalogação-na-Publicação (CIP) 
 
 
F676t Fonseca, Rubens Vilhena. 
 Teoria dos Números / Rubens Vilhena Fonseca — Belém: UEPA/ 
Centro de Ciências Sociais e de Educação, 2017. 
 
 ISBN:978 – 85 – 88375 – 66 – 6 
 
 1. Teoria dos Números, 2ª ed. I. Universidade do Estado do 
Pará. II. Título. 
 
 CDU: 511.68 
 CDD: 512.7 
GOD’S SOVEREIGN 
 3 Prof. Rubens Vilhena 
ÍNDICE 
1. OS INTEIROS ............................................................................................................................. 
1.1. Números e Sequências ................................................................................................................. 
1.2. Somatórios e Produtórios ........................................................................................................... 
1.3. Indução Matemática ................................................................................................................... 
1.4. Números de Fibonacci ................................................................................................................. 
1.5. Divisibilidade ............................................................................................................................... 
2. NÚMEROS PRIMOS ................................................................................................................. 
2.1. Números Primos .......................................................................................................................... 
2.2. A Distribuição de Números Primos ........................................................................................... 
2.3. O Máximo Divisor Comum e suas Propriedades ..................................................................... 
2.4. O Algoritmo de Euclides ............................................................................................................. 
2.5. O Teorema Fundamental da Álgebra ........................................................................................ 
2.6. Equações Diophantinas Lineares .............................................................................. .............. 
 
 
 
 
 
 
 
 
 
 
 
 
GOD’S SOVEREIGN 
 4 Prof. Rubens Vilhena 
 
1. OS INTEIROS 
 
 
 
A Teoria dos Números nasceu cerca de 600 anos antes de Cristo quando Pitágoras e 
os seus discípulos começaram a estudar as propriedades dos números inteiros. Os pitagóricos 
rendiam verdadeiro culto místico ao conceito de número, considerando-o como essência das 
coisas. Acreditavam que tudo no universo estava relacionado com números inteiros ou razões 
de números inteiros (em linguagem atual, números racionais). Aliás, na antiguidade a 
designação número aplicava-se só aos inteiros maiores do que um. 
O conceito de número tomou forma num longo desenvolvimento histórico. A origem 
e formulação deste conceito ocorreu simultaneamente com o despontar, entenda-se 
nascimento, e desenvolvimento da Matemática. As atividades práticas do homem, por um 
lado, e as exigências internas da Matemática por outro determinaram o desenvolvimento do 
conceito de número. A necessidade de contar objetos levou ao aparecimento do conceito de 
número Natural. 
Todas as nações que desenvolveram formas de escrita introduziram o conceito de 
número Natural e desenvolveram um sistema de contagem. O desenvolvimento subsequente 
do conceito de número prosseguiu principalmente devido ao próprio desenvolvimento da 
Matemática. Os números negativos aparecem pela primeira vez na China antiga. Os chineses 
estavam acostumados a calcular com duas coleções de barras - vermelha para os números 
positivos e pretos para os números negativos. No entanto, não aceitavam a ideia de um 
número negativo poder ser solução de uma equação. Os Matemáticos indianos descobriram os 
números negativos quando tentavam formular um algoritmo para a resolução de equações 
quadráticas. São exemplo disso as contribuições de Bramaghupta, pois a aritmética 
sistematizada dos números negativos encontra-se pela primeira vez na sua obra. As regras 
sobre grandezas eram já conhecidas através dos teoremas gregos sobre subtração, como por 
exemplo (a – b)(c – d) = ac + bd – ad – bc, mas os hindus converteram-nas em regras 
numéricas sobre números negativos e positivos. 
GOD’S SOVEREIGN 
 5 Prof. Rubens Vilhena 
Diofanto (Séc. III) operou facilmente com os números negativos. Eles apareciam 
constantemente em cálculos intermédios em muitos problemas do seu "Aritmetika", no 
entanto havia certos problemas para o qual as soluções eram valores inteiros negativos como 
por exemplo: 
4 20 4x  
 ou 23 18 5x x  
Nestas situações Diofanto limitava-se a classificar o problema de absurdo. Nos 
séculos XVI e XVII, muitos matemáticos europeus não apreciavam os números negativos e, 
se esses números apareciam nos seus cálculos, eles consideravam-nos falsos ou impossíveis. 
Exemplo deste fato seria Michael Stifel (1487- 1567) que se recusou a admitir números 
negativos como raízes de uma equação, chamando-lhes de "numeri absurdi". Cardano usou os 
números negativos embora chamando-os de "numeri ficti". A situação mudou a partir do 
(Séc.XVIII) quando foi descoberta uma interpretação geométrica dos números positivos e 
negativos como sendo segmentos de direções opostas. 
 
 
1.1. Números e Sequências 
 
Os números inteiros ou apenas os inteiros são: 
..., -3, -2, -1, 0, 1, 2, 3,... 
O conjunto representa-se pela letra Z, isto é: 
Z = {..., -3, -2, -1, 0, 1, 2, 3,...} 
Definição. Seja A um conjunto de inteiros. Chama-se elemento mínimo de A um elemento 
a A
 tal que 
a x
 para todo 
x A
. 
Representa-se pela notação “min A”, que se lê: “mínimo de A”. Portanto, 
simbolicamente: 
min A = a 

 (
a A
 e (
x A 
) (
a x
)) 
GOD’S SOVEREIGN 
 6 Prof. Rubens Vilhena 
O elemento mínimo de A, se existe, denomina-se também primeiro elemento de A ou 
menor elemento de A. 
Exemplo 1.1. O conjunto N = {1, 2, 3,...} dos inteiros positivos tem o elemento mínimo, que 
é 1 (min N = 1), porque 
1 N
 e 
1 n
 para todo 
n N
. 
Exemplo 1.2. O conjunto 𝐴 = {𝑥 ∈ ℤ | 𝑥 > 12} tem o elemento mínimo, que é 13 (min A = 
13), porque 
13 A
 e 
13 x
 para todo 
x A
. 
Exemplo 1.3. O conjunto 
-Z ={0 , -1, -2, -3, ...}
 dos inteiros não positivos não tem o 
elemento mínimo, porque não existe 
-Za
 tal que 
a x
 para todo 
-Zx
. 
Exemplo 1.4. O conjunto 𝐴 = {𝑥 ∈ ℤ | 3 𝑑𝑖𝑣𝑖𝑑𝑒 𝑥2} tem o elemento mínimo 
 3 min 3A 
, 
porque 
 3 3 divide 9A
 e 
3 x
 para todo 
 1 e 2x A A A  
. 
 
Princípio da Boa Ordenação (PBO) 
 
Definição. Todo conjunto não vazio A de inteiros não negativos possui o elemento mínimo. 
Em outros termos, todo subconjunto não vazio A do conjunto 
+Z ={0 ,1, 2, 3, ...}
 
dos inteiros não negativos (
+A Z  
) é bem ordenado, isto é, simbolicamente: 
(
,A Z A   
) 

 
min A
 
Exemplo 1.5. O conjunto A = {1,3, 5, 7,.. } dos inteiros positivos ímpares é um subconjunto 
não vazio de 
+Z
 (
+A Z  
). 
Logo, pelo “Princípio da boa ordenação”, A possui o elemento mínimo (min A = 1). 
Exemplo 1.6. O conjunto 
 2,3,5,7,11,...P 
dos inteiros primos é um subconjunto não vazio 
de 
 P  
. Logo, pelo PBO, P é bem ordenado (min P = 2). 
GOD’S SOVEREIGN 
 7 Prof. Rubens Vilhena 
Teorema 1.1. (de Arquimedes): Se a e b são dois inteiros positivos quaisquer, então existe 
um inteiro positivo n tal que 
na b
. 
Prova. Suponha que a afirmação do teorema não é verdadeira, de modo que para algum par a 
e b, na < b para todo inteiro positivo n. Então o conjunto 
S = {b - na | n um inteiro positivo} 
possui apenas inteiros positivos. Pelo Princípio da Boa Ordenação, S possuirá um elemento 
mínimo, digamos, b – ma. Observe que b - (m + l) a também está em S, pois S contém todos 
os inteiros dessa forma. Além disso, temos 
b - (m + l) a = (b - ma) - a < b - ma 
o que contraria a escolha de b – ma como o menor inteiro em S. Esta contradição surgiu de 
nossa suposição de que a propriedade Arquimedeana não é válida; por isso essa propriedade é 
verdadeira. ∎ 
Assim, por exemplo: 
i) se a = 2 e b = 11, então n = 6, porque 6.2 > 11; 
ii) se a = 9 e b = 5, então n =1, porque 1.9 > 5. 
 
Definição. O número real r é racional se existem inteiros p e q≠ 0 , tal que 𝑟 =
𝑝 
𝑞 
. Se r não é 
racional, dizemos que é irracional. 
Observe que todo inteiro n é um número racional, porque 𝑛 =
𝑛
1
. Exemplos de 
valores irracionais são 𝑒, √2 e 𝜋. Podemos usar o princípio da boa ordenação do conjunto 
de Inteiros para mostrar que √2 é irracional. A prova que mostramos a seguir, embora muito 
inteligente, não é a prova mais simples de que √2 é irracional. No desenvolvimento dos 
conceitos de Congruências pode-se fazer outra demonstração. A prova de que e é irracional é 
deixado como Divertimento 40. Quanto a difícil prova de que 𝜋 é irracional indicamos o 
livro dos matemáticos G. H. Hardy e E.M. Wright, An Introduction to the Theory of 
Numbers, 5th ed., Oxford University Press, Oxford, 1979. 
 
GOD’S SOVEREIGN 
 8 Prof. Rubens Vilhena 
Teorema 1.2. √2 é irracional. 
Prova. Suponhamos que √2 seja racional. Então existiriam inteiros positivos a e b tais que, 
√2 =
𝑎
𝑏
. Consequentemente, o conjunto S = {k √2; k e k √2 são inteiros positivos} é um 
conjunto não vazio de inteiros positivos ( não é vazio porque a = b√2 é um elemento de S). 
Portanto, pela propriedade da boa ordenação, S tem um elemento mínimo, digamos s = t√2, 
t um inteiro positivo. Logo, s√2 = 2t é um inteiro positivo também. 
Temos s√2 - s = s√2 - t√2 = (s - t)√2. Como s√2 e s são ambos inteiros, então 
(s - t)√2 também é um número inteiro. Além disso, (s - t)√2 é positivo, pois 
s√2 - s = s (√2 -1) e √2 > 1. Mas, s(√2 -1) é menor do que o elemento mínimo s, pois 
√2 < 2 então, √2 − 1 < 1. Esta contradição foi devida a escolha de s como o menor inteiro 
positivo em S. Segue que √2 é irracional. ∎ 
O conjunto dos inteiros, inteiros positivos, números racionais, e números reais são 
tradicionalmente denotados por 𝒁, 𝑵, 𝑸 e 𝑹. 
 
Definição. Um número 𝛼 é algébrico se for raiz de um polinômio com coeficientes inteiros; 
isto é, 𝛼 é algébrico se existem inteiros a0, a1, ..., an tal que 𝑎𝑛𝛼
𝑛 + 𝑎𝑛−1𝛼
𝑛−1 +⋯+ 𝑎0 =
0. O número 𝛼 é chamado transcendente se não é algébrico. 
Todos os números racionais são algébricos. Alguns números irracionais também são 
algébricos. Mas nem todos os reais são algébricos – como exemplo temos 𝜋 e e. 
Exemplo 1.7. O número irracional √2 é algébrico, porque é raiz do polinômio x2-2. 
 
Piso e Teto de um Número Real 
É fácil perceber que qualquer número real está sempre entre dois números inteiros, 
um inteiro menor que o dado número real e um inteiro maior que esse número real. Por 
exemplo, o número real
5
, está entre os inteiros 2 e 3 (
2 5 3 
) e também está entre os 
inteiros 1 e 4, 0 e 5, etc.; o número real 
3
2


, está entre os inteiros -5 e -4 (
3
5 4
2

    
) 
e também está entre os inteiros -6 e -3, -7 e -2, etc.. Veremos a seguir que o maior inteiro à 
GOD’S SOVEREIGN 
 9 Prof. Rubens Vilhena 
esquerda será chamado de Piso (floor) e o menor inteiro à direita será chamado de Teto 
(ceiling). 
Definição. Chamam-se partes inteiras de um número real r, os inteiros n e n+1 que verificam 
às condições: 
𝑛 ≤ 𝑟 ≤ 𝑛 + 1 
A todo número real r podemos associar dois números inteiros chamados piso e teto. 
Keneth Iverson introduziu esses nomes, assim como a notação que será usada, no início da 
década de 1960. 
Definição. Chama-se piso de um número real r, ao maior número inteiro menor ou igual a r. 
Definição. Chama-se teto de um número real r, ao menor número inteiro maior ou igual a r. 
Definição. Chama-se nint de um número real r, o valor inteiro mais próximo de r. Para evitar 
ambiguidades, no caso de valores de r iguais à metade de um inteiro, convenciona-se adotar o 
valor de nint sempre para o inteiro par. 
Definição. A parte fracionada (não inteira) de um número real r, é a diferença entre r e o 
piso de r. 
Notação: Usaremos as seguintes notações: 
 
r  
 piso de r 
 
r  
 teto de r 
 
 r
 nint de r 
 { r } parte fracionada de r. 
Observação: Infelizmente, não há acordo universal sobre o significado de {x} para x < 0 e 
existem duas definições comuns. Na linguagem Wolfram {x} é definida como 
{𝑥} = {
𝑥 − ⌊𝑥⌋, 𝑥 ≥ 0
𝑥 − ⌈𝑥⌉, 𝑥 < 0
 
Graham, Knuth e Patashnik (1994, p. 70), e talvez a maioria dos outros matemáticos, usam 
uma definição diferente 
{𝑥} = 𝑥 − ⌊𝑥⌋. 
GOD’S SOVEREIGN 
 10 Prof. Rubens Vilhena 
Neste texto usaremos esta última definição. 
Exemplos 1.8. Piso e teto de r. 
a) 
2 1 e 2 2    
   
 
b) 
1 1
0 e 1
3 3
   
    
   
 
c) 
3 e 4        
 
d) 
1 1
1 e 0
2 2
   
       
   
 
c) 
3 3
2 e 1
2 2
   
        
   
 
f) 
7 7 e 7 7           
 
Exemplos 1.9. Nint e parte fracionada de r. 
a) 
 2,3 2
 e 
 2,7 3
 
b) 
 3,5 4
 e 
 4,5 4  
 
c) 
1
0
3
 
 
 
 e 
23
4
6
 
 
 
 
d) 
1
0
2
 
 
 
 e 
 1,5 2  
 
e) 
  3 
 e 
  3e 
 
f) 
 3, 4 3
, 
 3,7 4  
 
g) 
{2,3} 2,3 2,3 2,3 2 0,3      
 
h) 
5 5 5 5 1
( 3) 0,5
2 2 2 2 2
   
             
   
 
O piso e o teto de um número real r são os inteiros definidos pelas desigualdades: 
GOD’S SOVEREIGN 
 11 Prof. Rubens Vilhena 
1r r r        
 
1 1r r r r r           
 
Em linguagem da Teoria dos Conjuntos: 
max{ | } e min{ | }r n n r r n n r           
 
Observe que 
r r r       
 se, e somente se, r é um número inteiro, e que todo 
número real r pode ser escrito sob a forma: 
{ } r r r   
, onde 
0 { } 1r 
 
e 
 
1 { }r r r    
, onde 
0 { } 1r 
 
 
Aproximações Diophantinas 
 
A teoria de aproximações diofantinas tem um problema básico que é o estudo de 
melhores aproximações de números reais por números racionais. (O adjetivo diophantina vem 
do matemático grego Diophantus). Aqui vamos enunciar e demonstrar um importante teorema 
devido aDirichlet relacionado a esta questão. A prova depende do famoso princípio das 
gavetas de Dirichlet ou somente princípio de Dirichlet, introduzido pelo matemático alemão 
Dirichlet em 1834. Informalmente, este princípio nos diz se temos mais objetos do que 
gavetas, quando esses objetos são colocados nas gavetas, pelo menos dois devem ser 
colocados na mesma gaveta. Apesar de parecer uma ideia particularmente simples, ela acaba 
por ser extremamente útil em Teoria do Números e combinatória. Iremos estabelecer e provar 
este fato importante, que também é conhecido como princípio das casas dos pombos , 
porque se você tiver mais pombos do que as casas onde eles se instalam, pelo menos dois 
pombos devem estar na mesma casa. 
GOD’S SOVEREIGN 
 12 Prof. Rubens Vilhena 
 
O princípio da casa do pombo é um exemplo de um argumento de cálculo que pode 
ser aplicado em muitos problemas formais, incluíndo aqueles que envolvem um conjunto 
infinito. 
 
Teorema 1.3. Princípio das gavetas de Dirichelet. Se k+1 ou mais objetos são colocados 
em k gavetas, então pelo menos uma gaveta irá conter dois o mais objetos. 
Prova: Se nenhuma das k gavetas contiver mais de um objeto, o número total de objetos será 
no máximo k. Esta contradição mostra que uma das caixas contém pelo menos dois ou mais 
dos objetos. 
Exemplo 1.10. Vejamos quantas pessoas, no mínimo, são necessárias para se ter certeza que 
haverá pelo menos duas delas façam aniversário no mesmo mês. 
Solução: Pelo princípio da casa dos pombos se houver no mínimo 13 pessoas, e como o total 
de meses é 12, é certo que pelos menos duas pessoas terão nascido no mesmo mês. 
Embora o princípio da casa dos pombos seja uma observação trivial, pode ser usado 
para demonstrar resultados possivelmente inesperados. 
Exemplo 1.11. Em toda grande cidade, digamos com mais de 1 milhão de habitantes existem 
pessoas com o mesmo número de fios de cabelo. 
Prova. Os cientistas afirmam que em média, uma pessoa tem cerca de 150 mil fios de cabelos 
,(http://www.ifsc.usp.br/~rpereira/FCM0101/links_files/aula1.pdf). É razoavel supor que 
ninguém tem mais de 10
6
 de fios de cabelo em sua cabeça. Se há mais habitantes do que o 
número máximo de fios de cabelo, necessariamente pelo menos duas pessoas terão 
exatamente o mesmo número de fios de cabelo. 
Antes de enunciar e demonstrar o teorema de Dirichlet, vejamos um exemplo: O 
leitor deve saber que √2 ≈ 1,41 =
141
100
 . Será que podemos encontrar uma aproximação 
melhor? A aproximação √2 ≈
17
12
 =1,41 é um pouquinho melhor, apesar de ter um 
GOD’S SOVEREIGN 
 13 Prof. Rubens Vilhena 
denominador menor. Mas se quisermos aproximações 𝜋 ≈
𝑝
𝑞
 melhores, devemos aumentar o 
denominador q. Mas, o quanto devemos aumentar? Será que podemos garantir a existência de 
uma aproximação boa com denominador pequeno? Para isso, provaremos o teorema de 
Dirichlet. 
Teorema 1.4. Teorema de Dirichlet. Se 𝛼 é um número irracional, então existem infinitos 
racionais 
𝑝
𝑞
 , q> 0, tais que 
|𝛼 −
𝑝
𝑞
| < 
𝑝
𝑞2
 
Prova. Observe que 
|𝛼 −
𝑝
𝑞
| < 
𝑝
𝑞2
 ⟺ |𝑞𝛼 − 𝑝| < 
1
𝑞
 
Assim, queremos provar que, para todo irracional 𝑞𝛼, a desigualdade |𝑞𝛼 − 𝑝| < 
1
𝑞
 
tem infinitas soluções inteiras p. 
Seja n um inteiro positivo. Divida o intervalo [0; 1] em n intervalos: [0; 1/n[, [1/n; 
2/n[, . . . , [(n − 1)/n; 1[. Considere os n + 1 números 
{𝛼 }, {2𝛼 }, ..., { (n+1) 𝛼}. 
Pelo Princípio de Dirichlet, dentre esses n + 1 números, há pelo menos dois, digamos 
{k 𝛼} e {j 𝛼 }, pertencentes ao mesmo intervalo. Logo 
|{k 𝛼} - {j 𝛼 }| < 
1
𝑛
 ⟺ =| (k 𝛼 -⌊𝑘𝛼⌋) - (j 𝛼 -⌊𝛼⌋) < |
1
𝑛
 ⟺ 
⟺| (k - j) 𝛼 - (⌊𝑘𝛼⌋ -⌊𝑗𝛼⌋) |<
1
𝑛
. 
Observe que 𝑘 − 𝑗 ≤ 𝑛. Assim, sendo q = i – j e 𝑝 = ⌊𝑘⌋ − ⌊𝑗⌋, 
|𝑞𝛼 − 𝑝| < 
1
𝑛
< 
1
𝑞
 ∎ 
Vamos ilustrar este teorema com uma questão da prova de seleção Cone Sul 2003: 
Sendo a e b positivos, prove que |𝑎√2 − 𝑏| >
1
2𝑎+𝑏
 . 
Solução. Como √2 é irracional, 2𝑎2 ≠ 𝑏2. Logo 
|2𝑎2 − 𝑏2| ≥ 1 ⟺ |(𝑎√2 − 𝑏)(𝑎√2 + 𝑏)| ≥ 1 ⟺ |𝑎√2 − 𝑏| ≥
1
𝑎√2 + 𝑏
 >
1
2𝑎 + 𝑏
 
GOD’S SOVEREIGN 
 14 Prof. Rubens Vilhena 
Outro resultado importante na teoria das aproximações diophnatinas é o Teorema da 
Aproximação de Dirichlet: “Se 𝛼 é um número real e n um inteiro positivo, então existem 
inteiros a e b com 1 ≤ 𝑎 ≤ 𝑛, tais que |𝑎𝛼 − 𝑏| < 
1
𝑛
 “. O exemplo a seguir, ilustra este 
teorema. 
 
Exemplo 1.12. Suponha que 𝛼 = √2 𝑒 𝑛 = 6. Obtemos 1.√2 ≈ 1,414, 2. √2 ≈ 2,828,
3. √2 ≈ 4,243, 4. √2 ≈ 5,657, 5. √2 ≈ 7,071, 𝑒 6. √2 ≈ 8,485. Dentre esses números, 5. √2 
é o que tem a menor parte fracionada. Veja que |5. √2 − 7| ≈ |7,071 − 7| = 0,071 ≤
1
6
. 
Segue que, se 𝛼 = √2 𝑒 𝑛 = 6, podemos tomar a=5 e b=7 para fazer 
1
| |a b
n
  
. Isto é, a 
distância entre 5. √2 e 7 é menor que 
1
6
. 
 
 
 
Sequências 
 
Uma sequência {an} é uma lista de números a1, a2, a3, ..., que verificam uma dada 
propriedade ou regra. Vamos considerar muitas sequências particulares de inteiros em nosso 
estudo da teoria dos números. Apresentamos várias sequências úteis nos exemplos seguintes. 
Exemplo 1.13. A sequência {an}, onde an = n
2
, começa com os termos 1, 4, 9, 16, 25, 36, 49, 
64, .... Esta é a sequência dos quadrados dos inteiros. A sequência {bn}, onde bn = 2
n
, 
começa com os termos 2, 4, 8, 16, 32, 64, 128, 256, .... Esta é a sequência das potências de 2. 
A sequência {cn}, onde cn = 0 se n é ímpar e cn = 1 se n é par, começa com os termos 0, 1, 0, 
1, 0, 1, 0, 1,. . . . 
 Existem muitas sequências nas quais cada termo sucessivo é obtido a partir do termo 
anterior multiplicado por um fator comum. Por exemplo, cada termo da sequência de 
potências de 2 é 2 vezes o termo anterior. Isso leva a seguinte definição. 
Definição. Uma progressão geométrica ér uma sequência da forma a, ar, ar
2
, ar
3
, ...,ar
k
, ..., 
onde a, o termo inicial, e r, uma razão comum, são números reais. 
GOD’S SOVEREIGN 
 15 Prof. Rubens Vilhena 
Exemplo 1.14. A seqüência {an}, onde an = 3.5
n
, n = 0, 1, 2, ..., é uma sequência geométrica 
com o termo inicial 3 e a razão comum 5. (Note que começamos a sequência com o termo a0. 
Podemos iniciar o índice dos termos de uma seqüência com 0 ou qualquer outro Inteiro que 
escolhermos.) 
Um problema comum na teoria dos números é encontrar uma fórmula ou regra para 
construir os termos de uma seqüência, mesmo quando apenas alguns termos são conhecidos 
(como tentar encontrar uma fórmula para o n-ésimo número triangular 1 + 2 + 3 + · · · + n). 
Mesmo que os termos iniciais de uma sequência não determinem a sequência, conhecer os 
primeiros termos pode nos levar a conjecturar uma fórmula ou regra para os termos. 
Considere os exemplos a seguir. 
Exemplo 1.15. Conjecture uma fórmula para an, onde os primeiros oito termos de {an} são 4, 
1 1, 18, 25, 32, 39, 46, 53. Notamos que cada termo, começando com o segundo, é obtido 
Adicionando 7 ao termo anterior. Conseqüentemente, o n-ésimo termo poderia ser o termo 
inicial mais 7(n - 1). Uma conjectura razoável é que an = 4 + 7 (n - 1) = 7n - 3. 
 A sequência proposta no Exemplo 1.15 é uma progressão aritmética, isto é, uma 
sequência da forma a, a + d, a + 2d, ..., a +nd, .... A sequência em particular do Exemplo 1.15 
tem a = 4 e d = 7. 
Exemplo 1.16. Conjecturar uma fórmula para an, onde os primeiros oito termos da sequência 
{an} são 5, 11, 29, 83, 245, 731, 2189, 6563. Observamos que cada termo é aproximadamente 
3 vezes o termo anterior, sugerindo uma fórmula para an em termos de 3n
. Os números inteiros 
3
n
 para n = 1, 2, 3, ... são 3, 9, 27, 81, 243, 729, 2187, 6561. Olhando estas duas sequências, 
verificamos que a fórmula an = 3
n
 + 2 produz aqueles termos. 
Exemplo 1.17. Conjecture uma fórmula para an, onde os primeiros dez termos da seqüência 
{an} são 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Depois de examinar esta sequência de perspectivas 
diferentes, notamos que cada termo desta seqüência, após os dois primeiros termos, é a soma 
dos dois termos precedentes. Ou seja, vemos que an = an-1 + an-2 para 3 ≤ 𝑛 ≤ 10. Este é um 
exemplo de uma definição recursiva de uma sequência, discutida na Seção 1.3. Os termos 
listados neste exemplo são os termos iniciais da sequência de Fibonacci, que é discutida na 
Seção 1.4. 
GOD’S SOVEREIGN 
 16 Prof. Rubens Vilhena 
As seqüências de números inteiros surgem em muitos contextos na teoria dos 
números. Podemos citar os números de Fibonacci, os números primos e os números perfeitos. 
As sequências de números inteiros aparecem em uma incrível variedade de assuntos além da 
teoria dos números. Neil Sloane acumulou uma coleção fantasticamente diversa de mais de 
170 000 sequências inteiras (no início de 2010) em sua On-Line Encyclopedia of Integer 
Sequences. Esta coleção está disponível na internet. (No início de 2010, a Fundação OEIS 
assumiu a manutenção desta coleção.) Este site fornece um programa para encontrar 
sequências que correspondem aos termos iniciais fornecidos como entrada. É um recurso 
valioso no estudo da teoria dos números (bem como outros assuntos). 
Agora definimos o que significa dizer que um conjunto é enumerável ( ou contável) e 
mostremos que um conjunto é contável se e somente se seus elementos podem ser listados 
como termos de uma sequência. 
Definição. Um conjunto finito ou infinto é enumerável (ou contável) se existir uma relação 
biunívoca entre o conjunto dos inteiros positivos e o conjunto. Um conjunto que não é 
enumerável é dito incontável. 
Um conjunto infinito é enumerável se e somente se seus elementos podem ser listados 
como os termos de uma sequência indexada pelo conjunto dos inteiros positivos. Para ver 
isso, basta observar que uma correspondência biunívoca f do conjunto de inteiros positivos 
para um conjunto S é exatamente o mesmo que listar os elementos do conjunto em uma 
seqüência a1, a2, ...,an, ..., onde ai = f (i) . 
Exemplo 1.18. O conjunto dos inteiros é enumerável, porque os inteiros podem ser listados 
começando com 0, seguido por 1 e -1, seguido por 2 e -2 e assim por diante. Isso produz a 
seqüência 0, 1, -1, 2, -2, 3, -3, ..., onde a1 = 0, a2n = n, e a2n+1 = -n para n = 1, 2, ... . 
O conjunto dos números racionais é enumerável? A primeira vista, pode parecer 
improvável que haja uma bijeção entre o conjunto os inteiros positivos e o conjunto de todos 
os números racionais. No entanto, Georg Cantor (1845 – 1918), o mesmo que segundo David 
Hilbert criu um paraíso matemático, surpreendeu o mundo matemático ao provar que havia 
tal correspondência. Com os recursos da Análise Real, essa é uma prova muito simples. 
Vejamos como sem esses recursos, George Cantor usou um elegante processo para conseguir 
uma prova. O processo ficou conhecido como método da diagonal de Cantor. Vamos utilizar 
o método da diagonal de Cantor para enumerar o conjunto N×N. 
GOD’S SOVEREIGN 
 17 Prof. Rubens Vilhena 
O produto cartesiano N×N é o conjunto representado por (x; y), onde x e y ∈N. 
Queremos então provar que o conjunto N×N é enumerável. 
Podemos separar os elementos em grupo e diferenciar os grupos do seguinte modo: Se 
(x; y) e (x’ ; y’) pertencem a um mesmo grupo, então x + y = x’ + y’. 
 [(1; 1)] pertence ao grupo onde x + y = 2 
[(1; 2)(2; 1)(3; 0)] pertence ao grupo onde x + y = 3 
[(1; 3)(2; 2)(3; 1)] pertence ao grupo onde x + y = 4 
[(1;4), (2;3), (3;2), (4;1)] pertence ao grupo onde x + y = 5 
Como cada um dos grupos possui um número finito de elementos, basta 
organizarmos os elemento na ordem crescente das somas correspondentes e enumerar os pares 
(x; y) na ordem em que aparecem. 
(1; 1)(1; 2)(2; 1)(3; 1)(2; 2)(1,3) ... 
Logo, N×N é enumerável. 
Na Figura 1.1 abaixo, temos uma ilustração da demonstração de que N×N é 
enumerável. 
Figura 1.1. N×N é enumerável 
Estamos em condições de provar o teorema seguinte. 
Teorema 1.5. O conjunto dos números racionais é enumerável. 
GOD’S SOVEREIGN 
 18 Prof. Rubens Vilhena 
Prova. Podemos trabalhar apenas com o conjunto Q+ dos racionais positivos, pois sendo esse 
conjunto enumerável, ele poderá ser posto em correspondência com o conjunto dos números 
naturais pares, enquanto o conjunto dos racionais negativos 𝑸−, poderá ser posto em 
correspondência com o conjunto dos números naturais ímpares, resultando assim que o 
conjunto Q fique em correspondência com o conjunto N. 
A enumerabilidade de Q é demonstrada usando o argumento diagonal de Cantor 
(Figura 1.2). A figura mostra um caminho a ser percorrido em Q+ o que mostra uma 
ordenação dos elementos. Cada elemento (x, y) ∈ N×N é associado a fração 
𝑥
𝑦
 ∈ 𝑸∗
+. Basta 
contar as frações irredutíveis 
 
Figura 1.2: 𝑄∗
+ é enumerável 
Mostramos que o conjunto de números racionais é contável, mas não demos um 
exemplo de um conjunto incontável. Esse exemplo é fornecido pelo conjunto dos números 
reais, veja o Divertimento 41. 
 
 
 
 
 
GOD’S SOVEREIGN 
 19 Prof. Rubens Vilhena 
 
DIVERTIMENTOS ARITMÉTICOS 1.1 
 
1. Demonstre que se a é elemento mínimo de A, então esse elemento é único. 
2. Determine se cada um dos seguintes conjuntos é bem ordenado. 
a) O conjunto dos inteiros maiores que 3. 
b) O conjunto dos inteiros positivos pares. 
c) O conjunto dos números racionais positivos. 
d) O conjunto dos números racionais positivos da forma 
2
a
, onde a é um inteiro 
positivo. 
e) O conjunto dos números racionais não negativos. 
 
3. Mostre que se a e b são inteiros positivos, então existe um menor inteiro positivo da 
forma a – bk, 
k 
. 
 
4. Seja Q = 1! + 2! + 3! + ... + n!. Para quantos valores de n tem-se Q quadrado perfeito? 
 
5. Mostre que tanto a soma quanto o produto de racionais são racionais. 
 
6. Prove ou desprove cada uma das seguintes afirmações: 
a) A soma de um irracional com um racional é irracional. 
b) A soma de dois irracionais é irracional. 
c) O produto de um racional com um irracional é um irracional. 
d) O produto de dois irracionais é irracional. 
 
7. Use o PBO para provar que: 
a) 
3
 é irracional. 
b) Não existe um natural n tal que 1 < m < 2. 
c) O conjunto S = {n; n ∈ Z e P(n) sempre falsa } é um conjunto vazio 
d) O conjunto S = {m ∈ Z : 8 < m < 9} é vazio. 
GOD’S SOVEREIGN 
 20 Prof. Rubens Vilhena 
 
8. Mostre que todo conjunto não vazio de inteiros negativos tem um maior elemento. 
 
9. Determine o piso. 
𝑎) ⌊
1
4
⌋ 𝑏) ⌊
−3
4
⌋ 𝑐) ⌊
22
7
⌋ 𝑑)⌊−2⌋ 𝑒) ⌊⌊
1
2
⌋ + ⌊
1
2
⌋⌋ 𝑓) ⌊−3 + ⌊
1
2
⌋⌋ 
𝑔) ⌊
−1
4
⌋ ℎ) ⌊
−22
7
⌋ 𝑖) ⌊
5
4
⌋ 𝑗) ⌊⌊
1
2
⌋⌋ 𝑘) ⌊⌊
3
2
⌋ + ⌊
−3
2
⌋⌋ 𝑙) ⌊3 − ⌊
1
2
⌋⌋ 
 
10. Determine a parte fracionada. 
𝑎)
8
5
 𝑏) 
1
7
 𝑐) 
−11
4
 𝑑) 7 𝑒)
−8
5
 𝑓) 
22
7
 𝑔) − 1 ℎ) 
−1
3
 
 
11. Qual é o valor de 
x x       
, onde x é um número real. 
 
12. Mostre que 
1
2
2
x x x
 
          
, para qualquer número real x. 
 
13. Mostre que 
x y x y            
, para qualquer número real x e y. 
 
14. Mostre que 
2 2x y x y x y                     
, para qualquer número real x e y. 
 
15. Mostre que se x e y são números reais positivos, então 
xy x y          
. Qual é a 
situação quando x e y são negativos? O que acontece quando um dos números é 
positivo e o outro negativo? 
 
16. Mostre que 
x   
 é o teto do número real x. 
 
17. Mostre que 
1
2
x
 
  
 é o inteiro mais próximo de x (quando há dois inteiros 
equidistantes de x, ele é o mais distante dos dois). 
 
GOD’S SOVEREIGN 
 21 Prof. Rubens Vilhena 
18. Mostre que se m e n são inteiros, então x nx n
m m
            
 para qualquer número 
real x. 
 
19. Mostre que 
x x        
 para qualquer número real não negativo. 
 
20. Mostre que se m é um inteiro positivo, então 
1 2 3 1
...
m
mx x x x x x
m m m m
                                     
 
 
21. Conjecture uma fórmula para o n-ésimo termo da sequência {an}, onde os dez 
primeiros termos são dados. 
 
a) 3, 11, 19, 27, 35, 43, 51, 59, 67, 75 
b) 5, 7, 11, 19, 35, 67, 131, 259, 515, 1027 
c) 1, 0, 0, 1, 0, 0, 0, 0, 1, 0 
d) 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 
e) 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366 
f) 1,1,0,1,1,0,1,1,0,1 
g) 1,2,3,5,7,10,13,17,21,26 
h) 3,5,11,21,43,85,171,341,683,1365 
 
22. Determine três diferentes fórmulas ou regras para a sequência {an}, onde seus três 
primeiros termos são 2, 3, 4. 
 
23. Mostre que o conjunto de todos os inteiros maiores que -100, é contável. 
 
24. Mostre que o conjunto de todos os números racionais da forma 
5
n
, onde n é um 
inteiro, é contável. 
 
GOD’S SOVEREIGN 
 22 Prof. Rubens Vilhena 
25. Mostre que o conjunto de todos os números racionais da forma 
2a b
, onde a e b 
são inteiros, é contável. 
 
26. Mostre que a união de dois conjuntos contáveis é contável. 
 
27. Mostre que a união de um número contável de conjuntos contáveis é contável. 
 
28. Prove o Teorema da Aproximação de Dirichelet. 
 
29. Use uma calculadora, se necessário, para encontrar inteiros a e b tal que 
1 8a 
 e 
1
| |
8
a b  
, onde os valores de 

 são: 
a)
2
 b) 
3 2
 c) 

 d) 
e
 
 
30. Use uma calculadora, se necessário, para encontrar inteiros a e b tal que 
1 10a 
 e 
1
| |
10
a b  
, onde os valores de 

 são: 
a)
3
 b)
3 3
 c) 
2
 d) 
2e
 
 
31. Prove a versão forte do Teorema da Aproximação de Dirichlet. Se 𝛼 é um número real 
e n é um inteiro positivo, então existem inteiros a e b com 
1 a n 
 tal que 
1
| |
1
a b
n
  

. 
 
32. Mostre que se 𝛼 é um número real e n é um inteiro positivo, então existe um inteiro 
k tal que 
1
| |
2
n
k k
  
. 
 
33. Encontre quatro números racionais 
p
q
 com 
2
1
| 2 |
p
q q
 
. 
 
34. Encontre cinco números racionais 
p
q
 com 
3
2
1
| 5 |
p
q q
 
. 
GOD’S SOVEREIGN 
 23 Prof. Rubens Vilhena 
35. Mostre que se 𝛼 =
𝑎
𝑏
 é um número racional, então existem infinitos números racionais 
p
q
 tal que 
2
1
| |
p a
q b q
 
. 
 
36. A sequência espectral de um número real 𝛼 é a sequência que tem 
n  
 como seus e-
nésimos termos. Encontre os dez primeiros termos da sequência espectral de cada um 
dos seguintes números. 
a) 2 b) 
2
 c) 
2 2
 d) e e) 
1 5
2

 f) 3 g) 
3
 h) 
3 3
2

 i) 

 
 
37. Prove que se 
 
,então a sequência espectral de 

 é diferente da sequência 
espectral de 

. 
 
38. Mostre que para todo inteiro positivo ocorre exatamente uma das sequências espectrais 
de 

 ou de 

 se e, somente se, 

 e 

 são números irracionais positivos tal que 
1 1
1
 
 
. 
Os Números de Ulam correspondem a uma sequência {un}, n=1,2,3,... definida 
inicialmente por u1 = 1 e u2 = 2. Para cada sucessivo inteiro m>2, o inteiro é um número de 
Ulam se, e somente se, puder ser escrito como o menor inteiro que pode ser expresso 
unicamente como a soma de dois termos distintos já determinados dessa sequência. Encontre 
os dez primeiros números de Ulam. 
 
39. Mostre que existem infinitos números de Ulam. 
 
40. Prove que e é irracional.(Sugestão: Use o fato de que 𝑒 = 1 +
1
1!
+
1
2!
+
1
3!
+⋯) 
 
41. Mostre que o conjunto dos números reais é incontável. 
 
42. (Conjectura de Collatz ) Considere a função definida por 
T (n) = {
3𝑛+1
2
 𝑝𝑎𝑟𝑎 𝑛 í𝑚𝑝𝑎𝑟
𝑛
2
 𝑝𝑎𝑟𝑎 𝑛 𝑝𝑎𝑟 
 
GOD’S SOVEREIGN 
 24 Prof. Rubens Vilhena 
A conjectura 3n + 1 é a afirmação de que a partir de qualquer inteiro n> 1, a seqüência de 
iterações T(n), T(T(n)), T(T(T(n))),. . . , finalmente atinge o inteiro 1 e posteriormente, 
passa pelos valores 1 e 2. Isso foi verificado para todos os n < 10
16
. Confirme a conjectura 
nos casos n = 21 e n = 23. 
 
A sequência de Collatz para n = 25. 
 
43. Prove a desigualdade de Bernoulli: Se 1 + a > 0, então 
(1 + a)
n
 ≥ 1 + na 
Para todos n ≥ 1. 
44. Se os números an são definidos por a1 = 11, a2 = 21 e an = 3 an-1 – 2 an-2 para n ≥ 3, 
provar que 
an =5.2
n
 + 1, n ≥ 1. 
45. Uma ferramente algébrica na Álgebra Abstrata e Teoria dos Números é um conceito 
chamdo Ideal. 
Um ideal de 𝒁 é um subconjunto não vazio 𝑰 ⊆ 𝒁, satisfazendo as seguintes condições: 
(1) 𝑥 + 𝑦 ∈ 𝐼 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑥 𝑒 𝑦 ∈ 𝐼; 
(2) 𝑎𝑥 ∈ 𝐼 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎 ∈ 𝒁 𝑒 𝑡𝑜𝑑𝑜 𝑥 ∈ 𝐼. 
Mostre que todo ideal de 𝒁 contém 0. 
 
46. Mostre que: 
a) Se I é um ideal de 𝒁 e x ∈ I, então x2 ∈ I, e em geral xn ∈ I, para todo número natural 
n. 
b) Se I é um idela de Z e 1 ∈ I então, 𝑰 = 𝒁. 
c) Se I é um ideal de Z que contém x e (x + 1)2 então, 𝑰 = 𝒁. 
d) {0} e Z são ideais de Z e que {0} é o único ideal com número finito de elementos. 
e) A interseção de dois ideais é um ideal. (Em geral a união de dois ideais não nulos é um 
ideal) 
 
GOD’S SOVEREIGN 
 25 Prof. Rubens Vilhena 
 
1.2. Somatórios e Produtórios 
 
Como as somas e os produtos surgem tão frequentemente no estudo da teoria dos 
números, introduzimos agora notação para somas e produtos. Sejam os n > 1 inteiros. Para 
indicar, de modo abreviado, a soma desses n inteiros usa-se a notação: 
∑𝑎𝑖
𝑛
𝑖=1
 
 que se lê: “somatório de 1 a n”. 
Em particular, para n = 2, 3,..., temos: 
2
i 1 2
i 1
a a a

 
, 3
i 1 2 3
i 1
a a a a

  
, ... 
A letra i chama-se o índice do somatório e pode ser substituída por qualquer outra 
diferente de a e de n – é um índice mudo. E os inteiros 1 e n que figuram abaixo e acima da 
letra grega maiúscula (sigma) chamam-se respectivamente limite inferior e limite superior do 
índice i. 
O número de parcelas de um somatório é sempre igual à diferença entre os limites 
superior e inferior do seu índice mais uma unidade. 
Se m e n são dois inteiros, com, então, por definição: 
n
i m m 1 m 2 n
i m
a a a a ...a 

   
 
 
GOD’S SOVEREIGN 
 26 Prof. Rubens Vilhena 
Exemplo 1.19. Podemos ver que 
∑5𝑖 = 5.1 + 5.2 + 5.3 + 5.4 + 5.5 + 5.6 + 5.7 = 5 + 10 + 15 + 20 + 25 + 30 + 35 = 140
7
𝑖=1
 
∑(8𝑗 − 3) = (8.1 − 3) + (8.2 − 3) + (8.3 − 3) + (8.4 − 3) = 5 + 13 + 21 + 29 = 68
4
𝑗=1
 
∑𝑘.2𝑘
8
𝑘=3
= 3. 23 + 4. 24 + 5. 25 + 6. 26 + 7. 27 + 8. 28 == 24 + 64 + 160 + 384 + 896 + 2048 == 3576 
Observamostambém que, na notação de soma, o índice do somatório pode variar 
entre dois números inteiros, desde que o limite inferior não exceda o limite superior. Por 
exemplo, temos 
∑𝑘2
5
𝑘=3
= 32 + 42 + 52 = 50, 
∑3𝑘
2
𝑘=0
= 30 + 31 + 32 = 13, 
 ∑ 𝑘3
1
𝑘=−2
= (−2)3 + (−1)3 + (0)3 + 13 = −8. 
. 
Muitas vezes precisamos considerar somas em que o índice do somatório varia sobre 
todos aqueles inteiros que possuem uma propriedade particular. Podemos usar a notação de 
somatório para especificar uma propriedade particular ou propriedades que o índice deve ter 
para um termo com esse índice a ser incluído na soma. Este uso da notação é ilustrado no 
exemplo a seguir. 
 
Exemplo 1.20. Vemos que 
∑
1
𝑗 + 1
=
1
1
+
1
2
+
1
5
+
1
10
=
9
5
 𝑗 ≤ 10
𝑗∈{𝑛2|𝑛∈𝑍} 
 
porque os termos na soma são todos aqueles para os quais o inteiro j é um quadrado perfeito 
não superior a 10. Isto é, j=0, 1,4 e 9. 
As três propriedades seguintes para somatórios são frequentemente úteis. Deixamos 
suas provas nos Divertimentos. 
GOD’S SOVEREIGN 
 27 Prof. Rubens Vilhena 
 (1.1) n n n
i i i i
i 1 i 1 i 1
(a b ) a b
  
    
. 
(1.2) n n
i i
i 1 i 1
ka k a
 
 
. 
Por exemplo, calcular 
20
i 1
(5i 2)


. De acordo com as propriedades anteriores, 
 
(1.3)∑∑𝑎𝑖𝑏𝑗 = (∑ 𝑎𝑖
𝑛
𝑖=𝑚
)(∑𝑏𝑖
𝑞
𝑗=𝑝
)
𝑞
𝑗=𝑝
𝑛
𝑖=𝑚
=∑∑𝑏𝑗𝑎𝑖
𝑛
𝑖=𝑚
𝑞
𝑗=𝑝
 
Por exemplo, calcular 
∑∑2𝑖3𝑗
3
𝑗=2
2
𝑖=1
. 
De acordo com a propriedade anterior, 
∑∑2𝑖3𝑗
4
𝑗=2
3
𝑖=1
= (∑2𝑖
3
𝑖=1
)(∑3𝑗
4
𝑗=2
) = (2 + 22 + 23)(32 + 33 + 34) = 1638. 
∑∑3𝑗2𝑖
3
𝑖=1
4
𝑗=2
= (∑3𝑗
4
𝑗=2
)(∑2𝑖
3
𝑖=1
) = (32 + 33 + 34)(2 + 22 + 23) = 1638. 
 
Em seguida, desenvolvemos várias fórmulas úteis de somatórios. Muitas vezes 
precisamos avaliar somas de termos consecutivos de uma série geométrica. O exemplo a 
seguir mostra como uma fórmula para tais somas pode ser derivada. 
 
Exemplo 1.21. Avalie 
𝑆 =∑𝑎𝑟𝑗
𝑛
𝑗=0
 
20 20 20 20
i 1 i 1 i 1 i 1
(5i 2) 5i 2 5 i 20.2 5(1 2 ... 20) 40
   
             
 
1
5. (1 20)20 40 5.210 40 1090
2
     
 
GOD’S SOVEREIGN 
 28 Prof. Rubens Vilhena 
a soma dos primeiros n + 1 termos das séries geométricas a, ar, ar
2
,..., ar
k
,..., multiplicamos 
ambos os lados por 𝑟 ≠ 1 e manipulamos a soma resultante para encontrar: 
𝑟𝑆 = 𝑟∑𝑎𝑟𝑗
𝑛
𝑗=0
=∑𝑎𝑟𝑗+1
𝑛
𝑗=0
= 
 
=∑𝑎𝑟𝑘 
𝑛+1
𝑘=1
(deslocando o índice de soma, tomando k = j + 1) 
=∑𝑎𝑟𝑘
𝑛
𝑘=0
+ (𝑎𝑟𝑛+1 − 𝑎) (adicionando o termo com k = n + 1 e removendo o termo k = 0) 
=S + (𝑎𝑟𝑛+1 − 𝑎). 
Segue que 
𝑟𝑆 − 𝑆 = (𝑎𝑟𝑛+1 − 𝑎). 
Resolvendo para S, temos para 𝑟 ≠ 1, 
𝑆 =
𝑎𝑟𝑛+1−𝑎
𝑟−1
. 
Observe que para r = 1, temos 
∑𝑎𝑟𝑗
𝑛
𝑗=0
=∑𝑎 =
𝑛
𝑗=0
(𝑛 + 1)𝑎. 
 Exemplo 1.22. Fazendo a = 3, r = -5, e n = 6 na fórmula do Exemplo 1.21, temos que 
∑
3(−5)7 − 3
−5 − 1
𝑛
𝑖=0
= 39 063. 
O exemplo seguinte mostra que a soma das primeiras n potências consecutivas de 2 é 
1 menos que a próxima potência de 2. 
Exemplo 1.23. Seja n um inteiro positivo. Para encontrar a soma 
∑2𝑘
𝑛
𝑘=0
= 1 + 2 + 22 +⋯+ 2𝑛, 
Usamos o Exemplo 1.21. com a = 1 e r = 2, para obter 
1 + 2 + 22 +⋯+ 2𝑛 =
2𝑛+1 − 1
2 − 1
= 2𝑛+1 − 1. 
GOD’S SOVEREIGN 
 29 Prof. Rubens Vilhena 
Um somatório da forma 
∑ (𝑎𝑖
𝑛
𝑖=1
− 𝑎𝑖−1), 
onde a0, a1, ...an é uma sequência de números, é chamada de telescópica. Somas telescópicas 
são facilmente calculadas por que 
∑(𝑎𝑖
𝑛
𝑖=1
− 𝑎𝑖−1) = (𝑎1 − 𝑎0) + (𝑎2 − 𝑎1) + ⋯+ (𝑎𝑛 − 𝑎𝑛−1) = (𝑎𝑛 − 𝑎0) 
 
Os gregos antigos estavam interessados em sequências de números que podem ser 
representadas por arranjos regulares de pontos igualmente espaçados. O exemplo seguinte 
ilustra uma tal sequência de números. 
Exemplo 1.24. Os números triangulares t1, t2, t3,...,tk,... formam uma sequência onde tk é o 
número de pontos na matriz triangular de k linhas com j pontos na j-ésima linha. 
A Figura 1.2.1 abaixo ilustra que tk conta os pontos em triângulos regulares sucessivamente 
maiores para k = 1, 2, 3, 4 e 5. 
 
Figura 1.2.1. Números Triangulares 
Em seguida, determinaremos uma fórmula explícita para o n-ésimo número triangular tn. 
GOD’S SOVEREIGN 
 30 Prof. Rubens Vilhena 
 
Exemplo 1.25. Como podemos encontrar uma fórmula para o n-ésimo número triangular? 
Uma abordagem é usar a identidade (k + 1)
2
 – k2 = 2k + 1. Quando isolamos o fator k do lado 
esquerdo, encontramos 𝑘 =
(𝑘+1)2−𝑘2
2
−
1
2
 . quando somamos esta expressão para k = 1, 2, 
..., n, obtemos 
𝑡𝑛 = ∑𝑘
𝑛
𝑘=1
 
(∑
(𝑘 + 1)2 − 𝑘2
2
𝑛
𝑘=1
) −∑
1
2
𝑛
𝑘=1
 
 (substituindo k por 
(𝑘+1)2−𝑘2
2
−
1
2
 ) 
=(
(𝑛+1)2
2
−
1
2
) −
𝑛
2
 
= 
(𝑛2+2𝑛)
2
−
𝑛
2
 
= 
(𝑛2+𝑛)
2
=
𝑛(𝑛+1)
2
. 
 Concluímos que o n-ésimo número triangular é dado por tn =
𝑛(𝑛+1)
2
. 
Também definimos uma notação para os produtos, análoga àquela para as somas. O 
produto dos números a1, a2, ..., an é denotado por 
∏𝑎𝑗 = 𝑎1𝑎2…𝑎𝑛
𝑛
𝑗=1
. 
Exemplo 1.26. Para ilustrar a notação de produtório, temos 
 
A função fatorial surge em toda a teoria dos números. 
           
       
6
1
4
1
3 3.1 3.2 3.3 3.4 3.5 3.6
 =3.6.9.12.15.18=524880
5 3 5.1 3 5.2 3 5.3 3 5.4 3
 =2.7.12.17 2856
i
j
i
j


 
      


 
GOD’S SOVEREIGN 
 31 Prof. Rubens Vilhena 
Definição: Seja n um inteiro positivo. Então n! (lê-se "n fatorial") é o produto dos inteiros 1, 
2,. . . , n. Também especificamos que 0! = 1. Em termos de notação de produtório, temos 
𝑛! =∏𝑗
𝑛
𝑗=1
 
. 
 
 
DIVERTIMENTOS ARITMÉTICOS 1.2 
 
1. Encontre cada uma das seguintes somas. 
𝑎) ∑ 𝑗25𝑗=1 b) ∑ (−3)
5
𝑗=1 c) ∑
1
𝑗+1
5
𝑗=1 d) ∑ 3
4
𝑗=0 e) ∑ (𝑗 − 3)
4
𝑗=0 
f) ∑
𝑗+1
𝑗+2
4
𝑗=0 g) ∑ 2
𝑗8
𝑗=1 h) ∑ 5(−3)
𝑗5
𝑗=1 i) ∑ 3(−
1
2
)𝑗5𝑗=1 j) ∑ 8.3
𝑗10
𝑗=0 
k) ∑ (−2)𝑗+110𝑗=0 l) ∑ (
1
3
)𝑗10𝑗=0 
 
2. Encontre e prove uma fórmula para ∑ ⌊√𝑘⌋𝑛𝑘=1 em termos de n e ⌊√𝑘⌋. (Sugestão: 
Use a fórmula ∑ 𝑘2 =
𝑡(𝑡+1)(2𝑡+1)
6
𝑡
𝑘=1 ). 
 
3. Juntando dois arranjos triangulares, um com n linhas e o outro com n-1 linhas, forma-
se um quadrado (como ilustrado para n = 4), mostre que tn-1+tn=n
2
, onde tn é o n-
ésimo número triangular. 
 
 
GOD’S SOVEREIGN 
 32 Prof. Rubens Vilhena 
4. Juntando dois arranjos triangulares, cada um com n linhas forma-se um retângulo de 
tamanho n por n+1 ( como ilustrado para n = 4), mostre que 2tn-1 = n(n+1). Daí, 
conclua que tn =n(n+1)/2. 
 
 
 
5. Mostre que 3tn+tn-1=t2n , onde tn é o enésimo número triangular. 
 
6. Mostre que 𝑡𝑛+1
2 − 𝑡𝑛
2 = (𝑛 + 1)3, onde tn é o enésimo número triangular. 
 
7. Os números pentagonais são uma sequência de números que se podem representar sob 
a forma de pentágonos. Fazem parte dos chamados números poligonais. 
 
 
8. Mostre que 𝑝1 = 1e 𝑝𝑘= 𝑝𝑘−1 + (3𝑘 − 2) para 𝑘 ≥ 2. Conclua que 𝑝𝑛 =
∑ (3𝑘 − 2)𝑛𝑘=1 e calcule a soma para determinar uma fórmula para 𝑝𝑛. 
 
9. Prove que a soma dos (n – 1) números triangularescom o enésimo número quadrado 
é igual ao enésimo número pentagonal. 
10. a) Defina os números hexagonais hn para n=1, 2, 3... de maneira análoga as definições 
de número triangular, quadrado e pentagonal. 
 b)Determine uma fórmula para os números hexagonais. 
 
GOD’S SOVEREIGN 
 33 Prof. Rubens Vilhena 
11. a) Defina os números heptagonais de maneira análoga as definições de número 
triangular, quadrado e pentagonal. 
 b) Determine uma fórmula para os números heptagonais. 
 
12. Mostre que ℎ𝑛 = 𝑡2𝑛−1 para todo inteiro positivo n onde hn é o enésimo número 
hexagonal, definido no exercício 10, e t2n-1 é o (2n-1) número triangular. 
 
13. Mostre que 𝑝𝑛 = 𝑡3𝑛−1/3 onde pn é o enésimo número pentagonal , definido no 
exercício 11, e t3n-1 é o (3n-1) número triangular. 
 
Os números tetraédricos T1, T2, T3, ..., Tk, ... são definidos como o número de pontos 
necessários para construir uma sequência de tetraedros, tendo em conta que as bases da 
pirâmide são triangulares e, portanto constituídas por números triangulares. 
 
14. Mostre que o enésimo número tetraédrico é a soma dos n primeiros números 
triangulares. 
 
15. Determine uma fórmula para o enésimo número tetraédrico. 
 
16. Encontre n! para os 10 primeiros inteiros positivos n. 
 
17. Liste os inteiros 100!, 100100, 2100 e (50!)2 em ordem decrescente. Justifique sua 
resposta. 
 
18. Expresse cada um dos seguintes produtos em termos de ∏ 𝑎𝑖
𝑛
𝑖=1 , onde k é uma 
constante. 
a) ∏ 𝑘𝑎𝑖
𝑛
𝑖=1 b) ∏ 𝑖𝑎𝑖
𝑛
𝑖=1 c) ∏ 𝑎𝑖
𝑘𝑛
𝑖=1 
GOD’S SOVEREIGN 
 34 Prof. Rubens Vilhena 
19. Use a identidade 
1
𝑘(𝑘+1)
 = 
1
𝑘
−
1
𝑘+1
 para calcular ∑
1
𝑘(𝑘+1)
𝑛
𝑘=1 . 
 
20. Use a identidade 
1
𝑘2−1
 = 
1
2
(
1
𝑘−1
−
1
𝑘+1
) para calcular ∑
1
 𝑘2+1
𝑛
𝑘=2 . 
 
21. Encontre uma fórmula para ∑ 𝑘𝑛𝑘=1
2
 usando uma técnica análoga ao do exercício 19 e 
a fórmula dada. 
 
22. Encontre uma fórmula para ∑ 𝑘𝑛𝑘=1
3
 usando os resultados do exercício 19. 
 
23. Sem multiplicar todos os termos, verifique as igualdades. 
 a) 10! = 6! 7! b) 10!=7! 5! 3! c) 16! = 14! 5! 2! d) 9! = 7! 3! 3! 2! 
 
24. Sejam a1, a2, ..., na inteiros positivos. Seja b = (a1!a2!...an!)-1 e c = a1!a2!...an!. 
Mostre que c = a1!a2!...an!b!. 
 
25. Encontre todos os inteiros positivos x, y e z tais que x! + y! = z! 
 
26. Encontre o valor dos seguintes produtos. 
a) ∏ 1 − 
1
𝑗
𝑛
𝑗=2 b) ∏ 1 − 
1
𝑗2
𝑛
𝑗=2 
 
27. Prove as seguintes propriedades 
(1.1) 
n n n
i i i i
i 1 i 1 i 1
(a b ) a b
  
    
 
(1.2) 
n n
i i
i 1 i 1
ka k a
 
 
 
(1.3) ∑ ∑ = (∑ 𝑎𝑖
𝑛
𝑖=𝑚 )(∑ 𝑏𝑖
𝑞
𝑗=𝑝 )
𝑞
𝑗=𝑝
𝑛
𝑖=𝑚 = ∑ ∑ 𝑎𝑖𝑏𝑗
𝑛
𝑖=𝑚
𝑞
𝑗=𝑝 
 
 
GOD’S SOVEREIGN 
 35 Prof. Rubens Vilhena 
 
1.3. Indução Matemática 
 
As ciências naturais utilizam o método chamado indução empírica para formular leis 
que devem reger determinados fenômenos a partir de um grande número de observações 
particulares, selecionadas adequadamente. Esse tipo de procedimento, embora não seja uma 
demonstração de que um dado fato é logicamente verdadeiro, é frequentemente satisfatório. 
Por exemplo: ninguém duvidaria de que quando um corpo é liberado ao seu próprio peso, no 
vácuo, na superfície da terra, ele cai segundo a vertical do local. 
A validade de um teorema matemático se estabelece de forma totalmente diferente. 
Verificar que certa afirmação é verdadeira num grande número de casos particulares não nos 
permitirá concluir que ela é válida. 
Para demonstrar a verdade de uma sequência infinita de proposições, uma para cada 
inteiro positivo, introduziremos o chamado método de recorrência ou indução matemática. 
Examinando as somas dos primeiros n primeiros números ímpares para pequenos valores de 
n, podemos conjecturar uma fórmula para esta soma. Temos 
1
 
= 1 = 1
2
 
1+ 3
 
= 4 = 2
2
 
1+ 3+ 5
 
= 9 = 3
2
 
1+ 3+ 5+ 7
 
= 16 = 4
2
 
1+ 3+ 5+ 7+9
 
= 25 = 5
2
 
A partir destes valores, conjecturamos que ∑ (2𝑘 − 1)
𝑛
𝑘=1
 = 1 + 3 + · · · + 2n-1= n
2
 
para cada inteiro positivo n. 
Para podemos provar que essa fórmula é válida para todos os inteiros positivos n, 
faremos uso da indução matemática. Quando uma proposição é enunciada em termos de 
números naturais, o Princípio de indução matemática constitui um eficiente instrumento para 
demonstrar a proposição no caso geral. 
Na prática, o método pode ser entendido por um artifício muito simples. Vamos 
supor que temos uma série de dominós idênticos colocados em fila, que começa por um deles 
e prossegue indefinidamente. 
GOD’S SOVEREIGN 
 36 Prof. Rubens Vilhena 
 
Nosso objetivo é - empurrando apenas um dominó - garantir que todos caiam. Como 
derrubar todos os dominós? Para isso, basta nos assegurarmos de que: 
1) O primeiro dominó cai; 
 
 
2) Os dominós estão dispostos de tal modo que qualquer um deles - toda vez que cai -, 
automaticamente, empurra o dominó seguinte e o faz cair também. 
 
Assim, mesmo que a fila se estenda indefinidamente, podemos afirmar que todos os 
dominós cairão. 
 
Vamos estabelecer matematicamente esses procedimentos. 
Teorema 1.6. Primeiro Princípio da Indução Matemática. Seja S um subconjunto do 
conjunto N dos inteiros positivos (
S N
) que satisfaz as duas seguintes condições: 
i) 1 pertence a S (
1 S
); 
ii) para todo inteiro k, se 
k S
, então 
( 1)k S 
. 
Nestas condições, S é o conjunto N dos inteiros positivo: S = N. 
GOD’S SOVEREIGN 
 37 Prof. Rubens Vilhena 
Prova. Suponhamos, por absurdo, que S não é o conjunto N dos inteiros positivos (
S N
) e 
seja X o conjunto de todos os inteiros positivos que não pertencem a S, isto é: 
X = {x | 
x N
 e 
x S
} = N – S 
Então, X é um subconjunto não vazio de N (
X N  
) e, pelo “Princípio da boa 
ordenação”, existe o elemento mínimo 
0x
 de X (min X = 
0x
). 
Pela primeira condição, 
1 S
, de modo que 
0x
 > 1 e, portanto, 
0x
 - 1 é um inteiro 
positivo que não pertence a X. Logo, (
0x
 - 1) 
S
 e, pela segunda condição, segue-se que (
0x
 
- 1) + 1 = 
0x
 
S
, o que é uma contradição, pois, 
0x X N S  
, isto é, 
0x S
. Assim 
sendo, 
X 
 e S = N. ∎ 
Consoante este “Princípio de indução finita”, o único subconjunto de N que satisfaz 
às duas condições é o próprio N. 
Na “demonstração por indução matemática” de uma dada proposição P(n) é 
obrigatório verificar que as condições i e ii são ambas satisfeitas. A verificação da condição i 
é geralmente muito fácil, mas a verificação da condição ii implica em demonstrar o teorema 
auxiliar cuja hipótese é: 
H: proposição P(k) é verdadeira, 
k N
. 
denominada “hipótese de indução”, e cuja tese ou conclusão é: 
T: proposição P(k + 1) é verdadeira. 
 Os problemas iniciais de indução geralmente são propostos de 4 maneiras: envolvendo 
adições, multiplicações, divisões e inequações. 
1. Indução envolvendo adições. 
Provaremos por indução matemática que ∑ (2𝑘 − 1)
𝑛
𝑘=1
 = n
2
, para todo inteiro 
positivo n. (A propósito, se nossa conjectura para o valor desta soma for incorreta, a 
indução matemática irá falhar em produzir uma prova!) 
 Verificando a primeira condição, 
∑(2𝑘 − 1) = 2 − 1 = 1 = 12
1
𝑘=1
 
GOD’S SOVEREIGN 
 38 Prof. Rubens Vilhena 
Para o passo indutivo, assumimos a hipótese indutiva de que a fórmula é válida para n; 
isto é, assumimos que ∑ (2𝑘− 1)
𝑛
𝑘=1
 = n
2
. Usando a hipótese indutiva, temos 
∑ (2𝑘 − 1)
𝑛+1
𝑘=1
 = ∑ (2𝑘 − 1)
𝑛
𝑘=1
+ (2(𝑛 + 1) − 1) (separando o termo com k = n + 1) 
 =n
2
+2(n+1)-1 (usando a hipótese de indução) 
 =n
2
+2n+1 
 =(n+1)
2
. 
O que prova a validade da conjectura. 
2. Indução envolvendo multiplicações. 
Podemos mostrar por indução matemática que para todo n > 0: 
𝑃(𝑛): (1 +
1
1
) (1 +
1
2
) (1 +
1
3
)…+ (1 +
1
𝑛
) = (𝑛 + 1) 
Para n = 1, a proposição é verdadeira: 
(1 +
1
1
) = (1 + 1) 
Assumimos que P(k) é verdadeira: 
𝑃(𝑘): (1 +
1
1
) (1 +
1
2
) (1 +
1
3
)… (1 +
1
𝑘
) = (𝑘 + 1) (I) 
Queremos provar que P(k+1) é verdadeira: 
(1 +
1
1
) (1 +
1
2
) (1 +
1
3
)…(1 +
1
(𝑘 + 1)
) = ((𝑘 + 1) + 1) 
Então. 
(1 +
1
1
) (1 +
1
2
) (1 +
1
3
)…(1 +
1
(𝑘 + 1)
) = 
= (1 +
1
1
) (1 +
1
2
) (1 +
1
3
)…(1 +
1
𝑘
) (1 +
1
(𝑘 + 1)
) 
Usando ( I ) 
= (𝑘 + 1) (1 +
1
(𝑘 + 1)
) 
= (𝑘 + 1) (
(𝑘 + 1) + 1
(𝑘 + 1)
) 
GOD’S SOVEREIGN 
 39 Prof. Rubens Vilhena 
= (𝑘 + 1) (
𝑘 + 2
(𝑘 + 1)
) 
= (𝑘 + 2) 
 
3. Indução envolvendo divisão. 
Provemos que 15 divide os números da forma 2
4n
 – 1, onde n >0. 
 
Seja P(n): 15|2
4n
 – 1.Vemos que para n = 1, 15|24 – 1 é verdadeira. 
Assumimos por hipótese que P(k): 24𝑘 − 1 = 15𝑡 é verdadeira, com t >0. 
Desenvolvendo 
24(𝑘+1) − 1 = 24𝑘+4 − 1 = 24𝑘24 − 1 − 24 + 24 = 24(24𝑘 − 1) − 1 + 24 = 
= 24. 15𝑡 + 15 = 15𝑞 
4. Indução envolvendo desigualdades 
Podemos mostrar por indução matemática que 𝑛! ≤ 𝑛𝑛 para cada inteiro positivo n. O 
passo base, ou seja, o caso em que n = l, é válido porque 1! = 1≤ 12 = 1. Agora, assumimos 
que k! ≤ 𝑘k . Esta é a hipótese de indução. Para completar a prova, devemos mostrar, sob o 
pressuposto de que a hipótese indutiva é verdadeira, que (k + 1)! ≤ (k + l)k+1. Usando a 
hipótese indutiva, temos 
 (k +1)! = (k+1). k! ≤ (k + 1k)kk < (k+1) (k +1)k ≤ (k +1)k+1 
Hipótese indutiva 
Uma ligeira variante do princípio da indução matemática também é por vezes muito 
útil em provas. 
Teorema 1.7 Segundo Princípio da Indução Matemática. Seja P(n) uma proposição 
associada a cada inteiro positivo n e que satisfaz às duas seguintes condições: 
i) P(1) é verdadeira; 
ii) para todo inteiro positivo k, se P(1), P(2), ..., P(k) são todas verdadeiras, então P(k + 1) 
também é verdadeira. 
Nestas condições, a proposição P(n) é verdadeira para todo inteiro positivo n. 
Prova. Seja S o conjunto de todos os inteiros positivos n para os quais a proposição P(n) é 
verdadeira, isto é: 
GOD’S SOVEREIGN 
 40 Prof. Rubens Vilhena 
S = {
n N
 | P(n) é verdadeira} 
Suponhamos por absurdo, que S≠ N e seja X o conjunto de todos os inteiros positivos que na 
pertencem a S, isto é: 
X = {x | 
x N
 e 
x S
} = N – S 
Então, X é um subconjunto não vazio de N e, pelo “Princípio da boa ordenação”, existe o 
elemento mínimo j de X (min X = j). 
Pela primeira condição, 1∈ 𝑆 , de modo que j > 1, e como j é o menor inteiro positivo 
que não pertence a S, segue-se que as proposições P(1), P(2),..., P(j – 1) são todas verdadeiras. 
Então, pela segunda condição, a proposição P(j) é verdadeira e j∈ 𝑆 , o que é uma 
contradição, pois j∈ 𝑋 , isto é, j∉ 𝑆 . Assim sendo, S = N e a proposição P(n) é verdadeira 
para todo inteiro positivo n.∎ 
O segundo princípio da indução matemática é às vezes chamado de indução forte 
para distingui-lo do primeiro princípio da indução matemática, que também é chamado 
Indução fraca. 
Exemplo 1.29. Numa brincadeira com selos, prove que cada quantidade de postagem de 12 
centavos ou mais pode ser formada usando apenas usando selos de 4 e 5 centavos. 
Prova por indução forte: Seja P (n) a proposição de que uma postagem de n≥ 12, pode ser 
obtida usando apenas selos de 4 centavos e 5 centavos. 
Passo inicial. Por exame direto, concluímos que P (12) = 3x4, P (13) = 2x4 + 5, P (14) = 2x5 
+ 4 e P (15) = 3x5, são verdadeiros. 
Etapa de indução. Suponha que P (k) é verdadeira para 12 ≤ k ≤ j, onde j é um inteiro com 
j≥ 15. Precisamos mostrar que P (k + 1) é verdadeira. 
Observe que k + 1 = k - 3 + 4 e k – 3 ≥ 12. Usando a hipótese indutiva, P (k - 3) é 
verdadeira (ou seja, a postagem de k - 3 centavos pode ser obtida usando selos de 4 centavos 
e de 5 centavos). Portanto, para formar uma postagem de k + 1 centavos, precisamos apenas 
adicionar outro selo de 4 centavos aos selos que usamos para formar a postagem de k - 3 
centavos. Isto completa o passo indutivo. 
Concluímos que P (n) é verdadeira para todo n≥ 12. 
 
GOD’S SOVEREIGN 
 41 Prof. Rubens Vilhena 
Definições Recursivas 
 
O princípio da indução matemática fornece um método para definir os valores de 
funções nos números inteiros positivos. Em vez de especificar explicitamente o valor da 
função em n, damos o valor da função em 1 e damos uma regra para encontrar, para cada 
inteiro positivo n, o valor da função em n + 1 a partir do valor da função em n. 
Definição. Dizemos que a função f é definida recursivamente se o valor de f em 1 é 
especificado e se para cada inteiro positivo n é fornecida uma regra para determinar f (n + 1) a 
partir de f (n). 
O princípio da indução matemática pode ser usado para mostrar que uma função que 
é definida recursivamente é definida unicamente em cada inteiro positivo (veja o 
Divertimento 25). Ilustramos como definir uma função recursivamente de acordo com 
definição. 
Exemplo 1.30. Definiremos recursivamente a função fatorial f (n) = n!. Primeiro 
especificaremos que 
f (1) = 1. 
Então obteremos uma regra para encontrar f (n + 1) a partir de f (n) para cada inteiro positivo, 
ou seja, 
f (n + 1) = (n + 1) · f (n). 
Essas duas declarações definem unicamente n! para o conjunto de inteiros positivos. 
Para encontrar o valor de f (6) = 6! A partir da definição recursiva, use a segunda 
declaração sucessivamente, da seguinte forma: 
f (6) = 6. f (5) = 6. 5. f (4) = 6. 5. 4. f (3) = 6. 5. 4. 3. f (2) = 6. 5. 4 3. 2. f (1). 
Em seguida, use a primeira declaração da definição para substituir f (1) pelo seu valor 
declarado 1, para concluir que 
6! = 6. 5. 4. 3. 2. 1 = 720. 
O segundo princípio da indução matemática também serve como base para 
definições recursivas. Podemos definir uma função cujo domínio é o conjunto de inteiros 
GOD’S SOVEREIGN 
 42 Prof. Rubens Vilhena 
positivos, especificando seu valor em 1 e dando uma regra, para cada inteiro positivo n, para 
encontrar f (n) a partir dos valores f (j) para cada inteiro j com 1≤ j≤ n - 1. Esta será a 
base para a definição da sequência dos números de Fibonacci discutida na próxima seção. 
 
 Nota histórica 
 
Era ideia assente na comunidade matemática do século XIX, que a indução era obra 
do matemático francês Blaise Pascal, tendo em conta diversas demonstrações que apresenta 
no seu Traité du Triangle Arithmétique. 
Essa situação seria integralmente modificada, vinte anos após a formulação moderna 
de indução matemática fixada por Giuseppe Peano , quando Giovanni Vacca , em 1909, num 
artigo de três páginas publicado no Bulletin of American Mathematical Society, vem defender 
que o italiano Francesco Maurolico , pelos trabalhos que desenvolveu no primeiro livro de 
aritmética incluído na sua Opuscula Mathematica, escrita em 1557 e publicado em Veneza no 
ano de 1575, como "the first discoverer of the principle of mathematical induction". 
O artigo de Vacca encontrou eco, aindaque eventualmente sem verificação posterior, 
em autores importantes como Moritz Cantor ou Siegmund Günther . M. Cantor, por exemplo, 
que atribuiu inicialmente a Pascal a principal origem do método de indução completa (em 
Vorlesungen uber Geschichte der Mathematik, vol. 2, p. 749), viria a transferir esse atributo 
para Maurolico (em Zeichrift fur Mathematischen und Naturwissenschaftlichen Unterricht, 
vol 33, 1902, p. 536), segundo conta devido a uma informação oral que lhe foi prestada pelo 
próprio Vacca. 
Passar-se-iam mais de quarenta anos sem que o artigo de Vacca fosse alvo de 
qualquer crítica. Até que Hans Freudenthal (em Zur Geschichte der vollständigen Induktion, 
Archive Internationale d'Histoire des Sciences 6 (1953) 17-37) depois de um exame detalhado 
dos trabalhos de Maurolico, vem sustentar que em apenas três pontos conseguiu reconhecer 
uma certa forma de indução matemática: uma forma arcaica, contudo, ao contrário do que 
observou em Pascal, onde a indução é formulada pela primeira vez de uma maneira abstrata. 
 
 
 
GOD’S SOVEREIGN 
 43 Prof. Rubens Vilhena 
 
DIVERTIMENTOS ARITMÉTICOS 1.3 
 
1. Use a indução matemática para provar que 
2nn 
, para qualquer inteiro positivo n. 
 
2. Conjecture uma fórmula para a soma dos n primeiro inteiros positivos pares. Prove seu 
resultado usando a indução matemática. 
 
3. Use a indução matemática para provar que 
2
1
1 1
2
n
k k n
 
, para qualquer inteiro 
positivo n. 
 
4. Conjecture uma fórmula para 
1
1
( 1)
n
k k k 

 a partir da soma dos primeiros valores de n. 
Prove que sua conjectura está correta usando a indução matemática. (Compare com o 
exercício 15 do item anterior). 
 
5. Conjecture uma fórmula para An onde 1 1
0 1
A
 
  
 
. Prove sua conjectura usando a 
indução matemática. 
6. Use a indução matemática para provar que 
1
( 1)
2
n
j
n n
j



, para todo inteiro positivo 
n. 
 
7. Use a indução matemática para provar que 
2
1
( 1)(2 1)
6
n
j
n n n
j

 

, para todo inteiro 
positivo n. 
 
8. Use a indução matemática para provar que 2
3
1
( 1)
2
n
j
n n
j

 
  
 

, para todo inteiro 
positivo n. 
GOD’S SOVEREIGN 
 44 Prof. Rubens Vilhena 
 
9. Use a indução matemática para provar que 
1
( 1)( 2)
( 1)
3
n
j
n n n
j j

 
 
, para todo 
inteiro positivo n. 
 
10. Use a indução matemática para provar que 
1 2 1
1
( 1)
( 1) ( 1)
2
n
j n
j
n n
j 


  
, para todo 
inteiro positivo n. 
 
11. Encontre uma fórmula para 
1
2
n
j
j

. 
 
12. Mostre que 
1
. ! ( 1)! 1
n
j
j j n

  
 para todo inteiro positivo n. 
 
13. Mostre que qualquer quantidade de selos para um número inteiro de centavos maior 
que 11 centavos pode ser formado usando apenas selos de 4 e 5 centavos. 
 
14. Mostre que qualquer quantidade de selos para um número inteiro de centavos maior 
que 53 centavos pode ser formado usando apenas selos de 7 e 10 centavos. 
Seja 
nH
 a n-ésima soma parcial da série harmônica, tal que 
1
1n
n
j
H
j

. 
15. Use a indução matemática para mostrar que 
2
1
2
n
n
H  
. 
 
16. Use a indução matemática para mostrar que 
2
1nH n 
. 
 
17. Mostre por indução matemática que se n é um inteiro positivo, então 
2 2(2 )! 2 ( !)nn n
. 
 
18. Mostre por indução matemática que x – y é um fator de xn – yn , onde x e y são 
variáveis. 
 
GOD’S SOVEREIGN 
 45 Prof. Rubens Vilhena 
19. Use a indução matemática para provar que o conjunto dos inteiros que contém o 
inteiro k, de tal forma que esse conjunto contém n+1 sempre que ele conter n, contém 
o conjunto dos inteiros que são maiores que ou iguais a k. 
 
20. Use a indução matemática para mostrar que 
2 !n n
 para 
4n 
. 
 
21. Use a indução matemática para mostrar que 
2 !n n
 para 
4n 
. 
 
22. Use a indução matemática para mostrar que se 
1h  
, então 
1 (1 )nnh h  
, para 
todo inteiro n não-negativo. 
 
23. Um quebra-cabeça é resolvido colocando suas peças juntas da maneira correta. Mostre 
que exatamente n - 1 movimentos são necessários para resolver um quebra - cabeça 
com n peças, onde um movimento consiste em juntar dois blocos de peças, com um 
bloco composto por uma ou mais peças montadas. (Sugestão: use o segundo princípio 
da indução) 
 
 
24. Explique o que está errado com a seguinte prova por indução matemática de que todos 
os cavalos são da mesma cor: Claramente todos os cavalos em qualquer conjunto de 1 
cavalo são todos da mesma cor. Isso completa o passo inicial. Agora suponha que 
todos os cavalos em qualquer conjunto de n cavalos são da mesma cor. Considere um 
conjunto de n + 1 cavalos, marcados com os inteiros 1, 2, ..., n + 1. Pela hipótese de 
indução, os cavalos 1, 2, ..., n são todos da mesma cor, como os cavalos 2 , 3, ..., n, n + 
1. Uma vez que estes dois conjuntos de cavalos têm elementos comuns, denominados, 
cavalos 2, 3, 4, ..., n, todos n+1 os cavalos devem ser da mesma cor. Isso completa o 
argumento de indução. 
 
GOD’S SOVEREIGN 
 46 Prof. Rubens Vilhena 
25. Use o princípio da indução matemática para mostrar que o valor em cada inteiro 
positivo de uma função definida recursivamente é determinado de forma única. 
 
26. Qual função f (n) é definida recursivamente por f (1) = 2 e f (n + 1) = 2f (n) para n≥ 
1? Prove sua resposta usando a indução matemática. 
 
27. Se g é definido recursivamente por g (l) = 2 e g (n) = 2g(n-1) para n ≥ 2, qual o valor de 
g (4)? 
 
28. Use o segundo princípio da indução matemática para mostrar que se f(1) é 
especificado e uma regra para encontrar f (n + 1) a partir dos valores de f nos 
primeiros n inteiros positivos é dada, então f (n) é unicament determinada para cada 
inteiro positivo n. 
 
29. Definimos uma função recursivamente para todos os inteiros positivos n por f (l) = 1, 
f (2) = 5 e para n ≥ 2, f (n + 1) = f (n) + 2 f ( n - 1). Mostre que f (n) = 2n + (-l)n, 
usando o segundo princípio da indução matemática. 
 
30. Mostre que 2n > n2 , para n > 4. 
 
31. Suponha que a0 = 1, a1 = 3, a2 = 9, e an = an-1 + an-2 + an-3 para n ≥ 3. Mostre que an 
≤ 3n para cada inteiro não negativo n. 
 
32. A torre de Hanoi era um enigma popular do final do século XIX. O enigma inclui três 
pinos e oito anéis de diferentes tamanhos colocados em ordem de tamanho, com o 
maior no fundo, em um dos pinos. O objetivo do quebra-cabeça é mover todos os 
anéis, um de cada vez, sem nunca colocar um anel maior sobre um anel menor, do 
primeiro pino ao segundo, usando o terceiro como um pino auxiliar. 
GOD’S SOVEREIGN 
 47 Prof. Rubens Vilhena 
 
a) Use a indução matemática para mostrar que o número mínimo de movimentos para 
transferir n anéis de um pino para outra, com as regras que descrevemos, é 2
n
 - 1. 
b) Uma antiga lenda conta dos monges com uma torre com 64 anéis de ouro e 3 pinos 
de diamante. Eles começaram a mover os anéis, 1 movimento por segundo, quando o 
mundo foi criado. Quando eles terminarem de transferir os anéis para o segundo pino, 
o mundo vai acabar. Quanto tempo ainda resta a humanidade? 
 
33. A média aritmética e a média geométrica dos números reais positivos a0, a1, ..., an são 
A = 
𝑎0+𝑎1+⋯+𝑎𝑛
𝑛
 e G = √𝑎0𝑎1…𝑎𝑛
𝑛 , respectivamente. Use a indução matemática para 
provar que A ≥ G para cada sequência finita de números reais positivos. Quando a 
igualdade éválida? 
 
34. Use a indução matemática para mostrar que um tabuleiro de xadrez 2n x 2n com um 
quadrado em falta pode ser coberto com pedaços em forma de L, onde cada peça em 
forma de L cobre três quadrados. 
 
Um exemplo 2
3
 x 2
3
 
35. Uma fração unitária é uma fração da forma 1 / n, em que n é um inteiro positivo. 
Como os antigos egípcios representavam frações como somas de frações unitárias 
distintas, tais somas são chamadas frações egípcias. Mostre que todo o número 
GOD’S SOVEREIGN 
 48 Prof. Rubens Vilhena 
racional p / q, onde p e q são inteiros com 0 <p < q, pode ser escrito como uma soma 
de frações unitárias distintas, isto é, como uma fração egípcia. (Dica: Use indução 
forte no numerador p para mostrar um algoritmo voraz que adiciona a maior fração 
unitária possível em cada estágio sempre termina. Por exemplo, executando este 
algoritmo mostra que 5/7 = 1/2 + 1/5 + 1 / 70.) 
 
36. Usando o algoritmo no Exercício 35, escreva cada um dos números como frações 
egípcias. 
a) 2/3 b) 5/8 c) 1 1/1 7 d) 44/101 
37. Determine uma fórmula para a soma dos n termos 7, 77,777, 7777,... com n 7’s. 
Prove por indução que a fórmula vale para todos os inteiros positivos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
GOD’S SOVEREIGN 
 49 Prof. Rubens Vilhena 
 
1.4. Números de Fibonacci 
 
 
Em seu livro Liber Abaci, escrito em 1202, o matemático Leonardo Fibonacci (1170 
– 1250) colocou um problema relativo ao crescimento do número de coelhos em uma 
determinada área. 
Este problema pode ser formulado da seguinte forma: Um casal de coelhos, é 
colocado em uma ilha. Supondo que os coelhos não se reproduzam até os dois meses de idade 
e depois de terem dois meses, cada par de coelhos produz outro par a cada mês, quantos pares 
há depois de n meses? 
Seja fn o número de pares de coelhos após n meses. Temos f1 = 1 porque Somente o 
par original está na ilha após um mês. Como este par não se reproduz até o segundo mês, f2 
= 1. Para encontrar o número de pares após n meses, adicione o número de coelhos na ilha no 
mês anterior, fn+1, ao número de pares recém-nascidos, o que equivale a fn+2, porque cada par 
recém-nascido vem de um par com pelo menos dois meses de idade. Isto leva à seguinte 
definição. 
Definição. A sequências de Fibonacci é definida recursivamente por f1 = 1, f2 = 1, e fn = 
fn-1 + fn-2 para 𝑛 ≥ 3. Os termos dessa sequência são chamados de números de Fibonacci. 
O matemático Edouard Lucas nomeou esta sequência de Fibonacci no século XIX, 
quando ele estabeleceu muitas de suas propriedades. A resposta à pergunta de Fibonacci é que 
existem fn coelhos na ilha depois de n meses. 
Examinar os termos iniciais da sequência de Fibonacci será útil à medida que 
estudamos suas propriedades. 
Exemplo 1.31. Calculamos os primeiros dez números de Fibonacci da seguinte forma: 
GOD’S SOVEREIGN 
 50 Prof. Rubens Vilhena 
f3 = f2 + f1 = 1 + 1 = 2 
f4 = f3 + f2= 2 + 1 = 3 
f5 = f4 + f3 = 3 + 2 = 5 
f6 = f5 + f4 = 5 + 3 = 8 
f7 = f6 + f5 = 8 + 5 = 13 
f8 = f7 + f6 = 13 + 8 = 21 
f9 = f8 + f7 = 21 + 13 = 34 
f10 = f9 + f8 = 34 + 21 = 55 
Podemos definir o valor de f0 = 0, de modo que f2 = f1 + f0. Podemos também definir 
fn onde n é um número negativo para que a igualdade na definição recursiva seja satisfeita 
(veja o Divertimento 37). 
Os números de Fibonacci ocorrem em uma incrível variedade de aplicações. Por 
exemplo, na botânica o número de espirais em plantas com um padrão conhecido como 
phyllotaxis (“arranjo de folhas”, são os padrões de distribuição das folhas ao longo do caule 
das plantas), é sempre um número de Fibonacci ( ver Figura 1.3). 
 
Figura 1.4.1 
Os números de Fibonacci também satisfazem um número extremamente grande de 
identidades. Por exemplo, podemos facilmente encontrar uma identidade para a soma dos 
primeiros n números consecutivos de Fibonacci. 
GOD’S SOVEREIGN 
 51 Prof. Rubens Vilhena 
Exemplo 1.32. A soma dos primeiros n números de Fibonacci para 3≤ n ≤ 8 é igual a 1,2, 4, 
7, 12, 20, 33 e 54. Olhando para estes números, vemos que eles são todos apenas 1 menos do 
que o número Fibonacci fn+2. Isso nos leva à conjecturar que 
∑𝑓𝑘
𝑛
𝑘=1
= 𝑓𝑛+2 − 1. 
Podemos provar essa identidade para todos os inteiros positivos n? 
Vamos mostrar, de duas maneiras diferentes, que essa identidade é válida para todos 
os inteiros n. Nós fornecemos duas demonstrações diferentes, para mostrar que há 
frequentemente mais de uma maneira de provar que uma identidade é verdadeira. 
Primeiro usamos o fato de que fn = fn-1 + fn-2 para n = 2, 3, ... e vemos que fk = 
fk+2 – fk+1 para k = 1,2,3,.... Isto significa que 
∑𝑓𝑘
𝑛
𝑘=1
=∑(𝑓𝑘+2 − 𝑓𝑘+1)
𝑛
𝑘=1
. 
Podemos facilmente avaliar esta soma porque é telescópica. Usando a fórmula para a soma 
telescópica dada na Seção 1.2, temos 
∑𝑓𝑘
𝑛
𝑘=1
= 𝑓𝑛+2 − 𝑓2 = 𝑓𝑛+2 − 1. 
O que prova o resultado. ∎ 
Podemos também provar essa identidade através da indução matemática. O passo 
inicial é válido porque ∑ 𝑓𝑘
1
𝑘=1 = 1 e isto é igual a f1+1= f3 – 1= 2 -1 = 1. A hipótese indutiva 
é 
∑𝑓𝑘
𝑛
𝑘=1
= 𝑓𝑛+2 − 1. 
Devemos mostrar que, sob esta suposição, 
∑𝑓𝑘
𝑛
𝑘=1
= 𝑓𝑛+3 − 1. 
Para provar isso, note que pela hipótese indutiva temos 
∑𝑓𝑘
𝑛+1
𝑘=1
= (∑𝑓𝑘
𝑛
𝑘=1
) + 𝑓𝑛+1 
=(fn+2 -1) + fn+1 
GOD’S SOVEREIGN 
 52 Prof. Rubens Vilhena 
=(fn+1 + fn+2) – 1 
 = fn+3 - 1∎ 
 
Quão rápido os números de Fibonacci crescem? 
A desigualdade a seguir, mostra que os números de Fibonacci crescem mais rápido 
do que a séries geométrica de razão 𝛼 =
1+√5
2
. 
Exemplo 1.33. Podemos usar o segundo princípio da indução matemática para provar que 
𝑓𝑛 > 𝛼
𝑛−2 para n ≥ 3 onde 𝛼 =
1+√5
2
. O passo inicial consiste em verificar essa desigualdade 
para n = 3 e n = 4. Temos 𝛼 <2 = f3, portanto o teorema é verdadeiro para n = 3. Como 
𝛼2 =
3+√5
2
 < 3 = f4, o teorema é verdadeiro para n = 4. 
A hipótese indutiva consiste em assumir que 𝛼𝑘−2 < 𝑓𝑘 para todos os inteiros k com 
k≤ n. Dado que 𝛼 =
1+√5
2
 é uma solução de x
2
 - x - 1 = 0, temos 𝛼2 = 𝛼 + 1. Portanto, 
𝛼𝑛−1 = 𝛼2𝛼𝑛−3 = (𝛼 + 1). 𝛼𝑛−3 = 𝛼𝑛−2 + 𝛼𝑛−3. 
Pela hipótese indutiva, temos as desigualdades 
𝛼𝑛−2 < 𝑓𝑛, 𝛼
𝑛−3 < 𝑓𝑛−1. 
Ao adicionar estas duas desigualdades, concluímos que 
𝛼𝑛−1 < 𝑓𝑛 + 𝑓𝑛−1 = 𝑓𝑛+1. 
 Isto termina a prova. ∎ 
Teorema 1.8. Seja n um inteiro positivo e seja 𝛼 = 
1+√5
2
 e 𝛽 = 
1−√5
2
. Então, o n-
ésimo número de Fibonacci fn é dado por 
𝑓𝑛 = 
1
√5
 (𝛼𝑛 − 𝛽𝑛). 
 
 
 
GOD’S SOVEREIGN 
 53 Prof. Rubens Vilhena 
 
DIVERTIMENTOS ARITMÉTICOS 1.4 
 
1. Encontre os seguintes números de Fibonacci. 
a) 𝑓10 c) 𝑓15 e) 𝑓20 
b) 𝑓13 d) 𝑓18 f) 𝑓25 
 
2. Encontre cada um dos seguintes números de Fibonacci. 
a) 𝑓12 c) 𝑓24 e) 𝑓32 
b) 𝑓16 d) 𝑓30 f) 𝑓36 
 
3. Prove que 𝑓𝑛+3 + 𝑓𝑛 = 2𝑓𝑛+2, onde 𝑛 é um inteiro positivo. 
 
4. Prove que 𝑓𝑛+3 − 𝑓𝑛 = 2𝑓𝑛+1, onde 𝑛 é um inteiro positivo. 
 
5. Prove que 𝑓2𝑛 = 𝑓𝑛
2 + 2𝑓𝑛−1𝑓𝑛, onde 𝑛 é um inteiro positivo. (Lembre-se que 𝑓0 = 0.) 
 
6. Prove que 𝑓𝑛−2 + 𝑓𝑛+2 = 3𝑓𝑛, onde 𝑛 é um inteiro com 𝑛 ≥ 2. (Lembre-se que 
𝑓0 = 0.) 
 
7. Encontre e prove uma fórmula simples para a soma dos 𝑛 primeiros números de 
Fibonacci com índices ímpares quando 𝑛 é um inteiro positivo. Ou seja, encontrar uma 
fórmula simples