98020793 Fundamentos de lgebra UFMG Dan Avritzer e Outros

Prévia do material em texto

FUNDAMENTOS DE ÁLGEBRA
Dan Avritzer
Hamilton Prado Bueno
Marília Costa de Faria
Ângela Maria Vidigal Fernandes
Maria Cristina Costa Ferreira
Eliana Farias e Soares
Universidade Federal de Minas Gerais
Departamento de Matemática
À Eliana,
inesquecível colega, amiga, companheira.
APRESENTAÇÃO
Este livro teve a sua origem em 1976, quando Dan Avritzer ministrou uma primeira
disciplina em Álgebra para os alunos do curso de Matemática da UFMG. Nessa época
os textos elementares disponíveis em português, de fácil acesso e boa qualidade, eram
o do curso que Said Sidki ministrou no 10o Colóquio Brasileiro de Matemática e
uma tradução de um livro curto de Serge Lang, denominado "Estruturas Algébricas".
Os demais eram, em sua grande maioria, publicados em inglês ou francês. As
peculiaridades de então do curso de licenciatura em Matemática motivaram Dan a
trabalhar um primeiro texto, no qual o método axiomático e o rigor fossem introduzidos
em situações simples. Esse foi testado por ele e por outros professores, no período
1976/1977. Houve um hiato de alguns anos até que no início da década de 80
vários docentes retornaram de programas de doutorado e a proposta de se examinar
cuidadosamente os conteúdos e os enfoques da disciplina "Fundamentos de Álgebra"
foi retomada e, ao longo dos anos, várias versões de um texto circularam e foram
adotadas nessa disciplina, culminando neste.
O livro introduz alguns conceitos e métodos básicos, essenciais à formação quer
de um professor de Matemática, quer de um Matemático. O rigor e a axiomática
são utilizados no contexto de números inteiros e transplantados, verbatim, para o
contexto de polinômios em uma variável. O mínimo essencial para o estudo dos
inteiros é percorrido de maneira suave, terminando com um breve estudo da noção de
congruência, motivadora primordial do conceito de estrutura quociente. Os polinômios
em uma variável são trabalhados exatamente na mesma ordem em que os inteiros
o foram, exemplificando de maneira simples um dos propósitos fundamentais da
Matemática, a busca de padrões. Os exercícios são motivadores, condizentes com uma
primeira apresentação do assunto, têm a qualidade de não serem repetitivos e são em
número adequado.
O livro atinge dois propósitos: é referência segura para professores do ensino médio
e é uma correta introdução à Álgebra elementar em nível universitário.
Márcio Gomes Soares
v
PREFÁCIO
Na primeira metade da década de 80, nós, um grupo de professores do
Departamento de Matemática da UFMG, resolvemos escrever um texto para a disciplina
"Fundamentos de Álgebra". No então currículo de graduação em Matemática, essa
disciplina era o primeiro contato dos estudantes com o método axiomático. Sua ementa
era simples: indução matemática, números inteiros e divisibilidade, congruências
e polinômios. Essa ementa era considerada adequada para uma disciplina com
esse propósito, uma vez que, em grande parte, abordava tópicos já conhecidos dos
estudantes desde o ensino básico.
Já havia bibliografia em português para o assunto. Entretanto, os livros existentes
não tinham a preocupação de introduzir a matéria tendo em vista a completa
inexperiência de seus leitores com o método axiomático. As provas eram apresentadas
sem preocupação com sua heurística. Achávamos esse tratamento inadequado para o
objetivo almejado.
Nosso objetivo era a redação de um texto ameno, que procurasse motivar cada
conceito introduzido e, dentro do possível, apresentá-lo dentro de um contexto
histórico. Um texto que aceitasse a inexperiência inicial do aluno, mas que fosse capaz
de acompanhar sua evolução com o decorrer do curso. E, diferentemente dos textos já
existentes em português, não procurávamos a abordagem mais concisa ou elegante,
ou mesmo aquela mais passível de generalizações; queríamos adotar, tanto quanto
possível, o mesmo enfoque empregado no ensino básico, tornando nosso texto uma
fonte de consulta imediata para os professores daqueles níveis.
Não demos ênfase à apresentação de estruturas algébricas. Preferimos salientar
apenas as similaridades entre inteiros e polinômios, deixando para cursos mais
avançados a generalização das estruturas envolvidas. De qualquer maneira, pensamos
que os dois exemplos básicos dessas estruturas foram apresentados, preparando o aluno
para os conceitos mais abstratos da Álgebra.
Depois de finalizado, o texto foi editado como apostila e adotado por quase todos os
professores da disciplina "Fundamentos de Álgebra" na UFMG. Alunos dessa disciplina
que vieram a se tornar professores universitários passaram também a utilizá-lo em seus
cursos. E, assim, o texto começou a ser adotado em diversas faculdades do interior de
Minas Gerais. Independentemente das críticas feitas ao texto – algumas delas vindas de
vii
viii PREFÁCIO
seus próprios autores – há que se constatar que a receptividade desse material por parte
dos alunos sempre foi bastante favorável. Talvez essa seja a melhor justificativa para a
presente edição deste livro.
O Brasil do começo dos anos oitenta vivia um período de final de ditadura e difusão
de um sentimento de cooperação. Consonante com o espírito da época, esse trabalho
nunca foi assinado. Seus autores se identificavam com o "Grupo de Álgebra", embora
um deles nunca tenha se dedicado a essa área da Matemática. Vários de seus autores já
tinham lecionado anteriormente a disciplina "Fundamentos de Álgebra". Mesmo assim,
o texto nasceu a partir de discussões (em sua maioria, bastantes acaloradas) em torno
de cada um dos temas abordados, procurando um enfoque que satisfizesse a todos
os membros do grupo. Após extensas discussões, chegávamos à redação de um texto
provisório que, experimentado em sala de aula, era alvo de críticas e novas discussões.
Um processo que parecia interminável, mas que foi concluído por volta de 1985. Desde
então, o texto permaneceu praticamente inalterado, sofrendo apenas simples correções.
Assim, quase 20 anos após a sua edição inicial como apostila, não deixa de ser
curioso que este texto seja agora publicado como livro. Dentre seus seis autores, dois
estão aposentados e um faleceu. A sua publicação trouxe consigo um problema ético:
alterar o texto, de modo a adequá-lo às atuais concepções de parte de seus autores?
Ou mantê-lo, tanto quanto possível, inalterado? Optamos por tentar manter a essência
do texto, embora corrigindo-o e atualizando-o, quando necessário. Para tornar sua
concepção mais coerente, foram feitas adequações: alguns exercícios propostos foram
reformulados, outros deram origem a material incorporado ao texto. Foram inseridos
textos que já estavam redigidos, mas que não estavam presentes na apostila. Entretanto,
ainda é possível ver este livro como uma edição melhorada daquela apostila. E era isso
que ambicionávamos nessa revisão...
Por outro lado, a oportunidade de reavaliar o texto original nos deixou com a
impressão de que ele satisfaz os objetivos escolhidos quando de sua redação. E achamos
que isso é suficiente para justificar sua edição como livro.
Agradecimentos. No decorrer de todos esses anos após a edição inicial desse texto
como apostila, é difícil nomear todos aqueles que colaboraram para o aperfeiçoamento
do mesmo. Diversos professores que ministraram o curso de "Fundamentos de
Álgebra"na UFMG contribuíram com sugestões, correções e discussões sobre o material
apresentado. Alunos de diversos anos em que a disciplina foi lecionada apontaram
incorreções e sugeriram aprimoramentos.
Cabe, entretanto, destacar algumas pessoas: os Profs. Antônio Zumpano Pereira
Santos, Jorge Sabatucci e Márcio Gomes Soares, que adotaram o texto em seus cursos e
contribuíram com inúmeras sugestões; o aluno Rogério Scalabrini, que foi responsável
pela datilografia da apostila e muitas correções; a aluna Cláudia Regina da Silva Lima,
que digitou em LATEX este texto.
ix
Utilizamos as fontesde Peter Wilson para os caracteres hieróglifos e gregos arcaicos,
e as de Karel Píška para os caracteres cuneiformes.
A todos, o nosso muito obrigado.
A edição deste livro foi possível graças ao financiamento da Pró-Reitoria de
Graduação da UFMG, através de projeto de produção de material didático.
Belo Horizonte, abril de 2004
Dan Avritzer
Hamilton Prado Bueno
Marília Costa de Faria
Maria Cristina Costa Ferreira
Ângela Maria Vidigal Fernandes
Eliana Farias e Soares (in memoriam)
AO ALUNO
Este texto tem um duplo propósito. Por um lado, pretende apresentar o estilo em
que são redigidos os textos de matemática. Em outras palavras, introduzir o método
axiomático. Isto é feito, no nosso caso, justamente através do estudo dos conjuntos dos
números inteiros e dos polinômios.
No ensino básico, a preocupação predominante de um texto de matemática era
explicar o porquê de tal ou qual problema ter sido resolvido de uma determinada
maneira. Em outras palavras, aprender tinha o significado de o aluno ter compreendido
o que o professor (ou o livro) justificava. Para se efetuar, por exemplo, a divisão de
dois números inteiros, o professor explicava o funcionamento do algoritmo da divisão,
justificando-o da melhor maneira possível. Se essa explicação fosse convincente, o aluno
seria capaz de perceber quando tal algoritmo era aplicável, ou seja, quais números
inteiros podiam ser divididos um pelo outro. O importante era a utilização do algoritmo
ensinado e não investigar sob quais condições ele poderia ser aplicado. Essa mesma
postura foi adotada nos primórdios da matemática, cuja ênfase é prática : "é assim que
se faz".
O florescimento da matemática grega introduziu uma nova postura, que contestava
o saber prático e que tem sido utilizada desde então em todos os ramos da matemática:
não bastava verificar a validade de uma afirmação para uma série de casos; era preciso
deduzi-la de fatos básicos, tidos como inquestionáveis ou então aceitos em determinado
contexto. Assim, por exemplo, para um babilônio, era indubitável que a soma dos
ângulos internos de um triângulo é 180 graus, já que esse fato poderia ser verificado
para cada triângulo. Esse é um exemplo de utilização do saber indutivo. A matemática
grega se opunha a essa postura: era preciso provar esse fato a partir de verdades básicas
(axiomas, princípios ou postulados), através de passagens lógicas irrefutáveis1. Esse é
o método dedutivo. No Capítulo 2 apresentaremos exemplos de questionamentos ao
saber indutivo e de aplicações do método dedutivo.
Uma das grandes dificuldades de todo texto que pretende introduzir o método
axiomático é escolher quais fatos serão aceitos como inquestionáveis e quais precisarão
ser deduzidos. Tentar chegar aos princípios básicos de todo o conhecimento matemático
é uma tarefa inglória: as dificuldades serão imensas e a exposição será dificultada,
1O estudo da geometria no ensino básico é feito sob essa diretiva. Inicialmente os postulados da
geometria euclidiana foram tidos como evidentes. Entretanto, a negação de seu quinto postulado deu
origem a novas geometrias e os postulados aceitos passaram a depender do contexto.
xi
xii AO ALUNO
fazendo com que o texto perca a simplicidade. Por exemplo, podemos partir dos
números naturais como conhecidos. Mas é possível construir o conjunto dos naturais,
isto é, obtê-lo de resultados mais fundamentais.
Aceitaremos como verdadeiros fatos básicos sobre os números inteiros. Mas não
explicitaremos quais resultados serão tidos como verdadeiros. Isso pode causar-lhe
alguma dificuldade, já que você poderá ter dúvidas sobre o que é evidente e o que não é.
Como norma, podemos sintetizar que todo processo (algoritmo, resultado) geral deverá
ser demonstrado, enquanto algumas afirmações particulares serão aceitas como válidas.
Por exemplo, demonstraremos que podemos sempre dividir o número inteiro a pelo
número inteiro b, desde que b 6= 0. Mas não mostraremos a inexistência de um número
natural entre 1 e 2, fato que aceitaremos como óbvio. (A nossa experiência didática nos
diz que é infrutífera a tentativa de explicitar aquilo que aceitaremos como verdadeiro.)
O material que apresentaremos nesse curso você conhece, em grande parte, desde
o ensino básico: números inteiros, critérios de divisibilidade, números primos, máximo
divisor comum e mínimo múltiplo comum, polinômios. Isso torna, ao nosso ver, mais
fácil a introdução do método axiomático, pois você estudará apenas a demonstração de
resultados (em grande parte) já conhecidos, e terá contato restrito com material que não
conhece.
Contudo, aprender o método axiomático não é brincadeira de criança. O método
traz consigo uma linguagem abstrata que, muitas vezes, pode ser difícil de entender.
Por exemplo, você pode não ser capaz de compreender a seguinte frase: não existe um
número real a > 0 tal que a < (1/n), para todo número natural n ≥ 1. Tentaremos, tanto
quanto possível, introduzir paulatinamente a linguagem abstrata, para que você possa
se inteirar de seu significado. Isso será feito motivando o estudo de um determinado
problema ou a apresentação de uma demonstração. Mas, em última instância, a
linguagem abstrata somente deixará de ser um problema através da sua utilização
corriqueira. Em outras palavras, através de muitas horas de estudo.
Mas o texto tem um segundo objetivo: ao estudar os inteiros e polinômios, ele
pretende comparar esse conjuntos, apresentando propriedades que lhes são comuns.
Por exemplo, se b 6= 0, a possibilidade de escrevermos a = qb + r, com 0 ≤ r < b no
caso dos inteiros ou, no caso de polinômios, r = 0 ou gr(r) ≤ gr(b), em que gr(p) denota
o grau do polinômio p. Ou a possibilidade de decompormos a = p1 · · · pk como produto
de fatores primos, no caso dos inteiros, ou fatores irredutíveis, no caso de polinômios.
Se, ao final dessa jornada, o método axiomático deixar de ser uma abstração
desagradável e as similaridades entre os conjuntos dos inteiros e o dos polinômios
tornarem-se claras, estaremos duplamente recompensados. E você poderá prosseguir
no estudo da álgebra abstrata, que procura justamente estudar e classificar conjuntos
com propriedades semelhantes, em especial, grupos, anéis e corpos.
SUMÁRIO
APRESENTAÇÃO v
PREFÁCIO vii
AO ALUNO xi
1 SISTEMAS DE NUMERAÇÃO 1
1.1 O PROCESSO DE CONTAGEM . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 UM POUCO SOBRE SISTEMAS DE NUMERAÇÃO . . . . . . . . . . . . . . . . 2
1.3 A REPRESENTAÇÃO DE UM NÚMERO EM UMA BASE . . . . . . . . . . . . . 4
2 INDUÇÃO E BOA ORDENAÇÃO 9
2.1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 DEDUÇÃO E INDUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 INDUÇÃO: PRIMEIRA FORMA . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 INDUÇÃO: SEGUNDA FORMA . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 O PRINCÍPIO DA BOA ORDENAÇÃO . . . . . . . . . . . . . . . . . . . . . . 22
2.6 PRINCÍPIOS OU TEOREMAS? . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 DIVISÃO EUCLIDIANA 32
3.1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 O ALGORITMO DA DIVISÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 REPRESENTAÇÃO DE UM NÚMERO EM UMA BASE . . . . . . . . . . . . . . 39
3.4 CRITÉRIOS DE DIVISIBILIDADE . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 A EXPRESSÃO DECIMAL DOS NÚMEROS RACIONAIS . . . . . . . . . . . . 44
3.6 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 O TEOREMA FUNDAMENTAL DA ARITMÉTICA 51
4.1 NÚMEROS PRIMOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 O TEOREMA FUNDAMENTAL DA ARITMÉTICA . . . . . . . . . . . . . . . . 55
4.3 A PROCURA DE NÚMEROS PRIMOS. . . . . . . . . . . . . . . . . . . . . . . 58
4.4 EXPRESSÕES DECIMAIS FINITAS E INFINITAS . . . . . . . . . . . . . . . . . 60
4.5 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
xiii
xiv SUMÁRIO
5 DIVISORES E MÚLTIPLOS COMUNS 67
5.1 MÁXIMO DIVISOR COMUM . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 MÍNIMO MÚLTIPLO COMUM . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6 EQUAÇÕES DIOFANTINAS LINEARES 86
6.1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2 RESOLUÇÃO DE EQUAÇÕES DIOFANTINAS LINEARES . . . . . . . . . . . . 87
6.3 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7 CONGRUÊNCIAS 96
7.1 DEFINIÇÃO E PROPRIEDADES . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.2 CLASSES DE CONGRUÊNCIA . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.3 OS TEOREMAS DE FERMAT, EULER E WILSON . . . . . . . . . . . . . . . . . 113
7.4 O TEOREMA CHINÊS DO RESTO . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.5 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8 DIVISÃO DE POLINÔMIOS 128
8.1 CORPOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8.2 POLINÔMIOS: DEFINIÇÕES E OPERAÇÕES . . . . . . . . . . . . . . . . . . . 130
8.3 LEMA DA DIVISÃO DE EUCLIDES . . . . . . . . . . . . . . . . . . . . . . . . 133
8.4 MÁXIMO DIVISOR COMUM . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
8.5 MÍNIMO MÚLTIPLO COMUM . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.6 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
9 RAÍZES E IRREDUTIBILIDADE 150
9.1 RAÍZES E FATORAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
9.2 O TEOREMA FUNDAMENTAL DA ÁLGEBRA . . . . . . . . . . . . . . . . . . 153
9.3 FATORAÇÃO EM POLINÔMIOS IRREDUTÍVEIS . . . . . . . . . . . . . . . . . 161
9.4 DECOMPOSIÇÃO EM FRAÇÕES PARCIAIS . . . . . . . . . . . . . . . . . . . . 165
9.5 EXERCÍCIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
REFERÊNCIAS BIBLIOGRÁFICAS 175
ÍNDICE REMISSIVO 177
CAPÍTULO 1
SISTEMAS DE NUMERAÇÃO
1.1 O PROCESSO DE CONTAGEM
O conceito de número com o qual estamos familiarizados, e que é tão essencial
na sociedade de nossos dias, evoluiu muito lentamente. Para o homem primitivo, e
mesmo para o filósofo da antiguidade, os números estão intimamente relacionados com
a natureza. Para o homem civilizado de hoje, o número natural é um ente puramente
matemático, uma conquista de seu pensamento.
Em todas as formas de cultura e sociedade, mesmo as mais rudimentares,
encontramos algum conceito de número e, a ele associado, algum processo de contagem.
Pode-se dizer que o processo de contagem consistia, a princípio, em fazer corresponder
os objetos a serem contados com os objetos de algum conjunto familiar (chamado
conjunto de contagem): os dedos da mão, do pé, pedras, etc. Com a necessidade
de contagem de uma quantidade maior de objetos (como, por exemplo, o número de
cabeças de gado ou de dias), o homem sentiu que era necessário sistematizar o processo
de contagem e os povos de diversas partes do mundo desenvolveram vários tipos
de sistemas de contagem. Estabelecia-se então um conjunto de símbolos juntamente
com algumas regras que permitiam contar, representar e enunciar os números. Alguns
desses conjuntos continham cinco, outros dez, doze, vinte ou até sessenta símbolos,
chamados "símbolos básicos".
Hoje, o processo de contagem consiste em fazer corresponder os objetos a
serem contados com o conjunto N = {1, 2, 3, . . .}. Para se chegar à forma atual,
aparentemente tão semelhante à anterior, foram necessárias duas grandes conquistas
que estão intimamente relacionadas: o conceito abstrato de número e uma representação
adequada para esses.
A possibilidade de se estender indefinidamente a seqüência numérica e, portanto,
a existência de números arbitrariamente grandes, foi uma descoberta difícil e está
associada às duas conquistas acima citadas. Arquimedes (287 - 212 A.C.), em sua
monografia O Contador de Areia, descreve um método para enunciar um número maior
1
2 CAPÍTULO 1. SISTEMAS DE NUMERAÇÃO
do que o número de grãos de areia suficiente para encher a esfera das estrelas fixas
(então considerada como o "Todo", isto é, o Universo). Em outras palavras, Arquimedes
descreveu um número maior do que o número de elementos do maior conjunto de
contagem possível: o Universo.
Para dar uma idéia da dificuldade da questão relativa à representação dos números,
lembramos que, a princípio, nossos mais antigos antepassados contavam só até dois,
e a partir daí diziam "muitos" ou "incontáveis". (É fato que, ainda hoje, existem
povos primitivos que contam objetos dispondo-os em grupos de dois.) Os gregos, por
exemplo, ainda conservam em sua gramática uma distinção entre um, dois e mais de
dois, ao passo que a maior parte das línguas atuais só faz a distinção entre um e mais
de um, isto é, entre singular e plural.
1.2 UM POUCO SOBRE SISTEMAS DE NUMERAÇÃO
Tendo sido escolhido o conjunto de símbolos básicos, os primeiros sistemas de
numeração, em grande maioria, tinham por regra formar os numerais pela repetição
de símbolos básicos e pela soma de seus valores. Assim eram os sistemas egípcio, grego
e romano.
Por volta de 3000 A.C. os egípcios usavam figuras para representar seus numerais.
Tinham então um sistema que consistia em separar os objetos a serem contados em
grupos de dez, mas não tinham um símbolo para o zero . Portanto, para representar
cada múltiplo de dez eles utilizavam um símbolo diferente dos básicos. Um número era
formado, então, pela justaposição desses símbolos, os quais podiam estar escritos em
qualquer ordem, já que a posição do símbolo não alterava o seu valor. Por exemplo,
|, 2, 3, e
4
representavam 1, 10, 100 e 1000, respectivamente. Assim, tanto
33 322 ||| |||
quanto
232 3|| ||| |3
representavam o mesmo número, a saber, 326.
Por volta de 400 A.C. os gregos utilizavam letras para representar os números1. Mais
precisamente, era usado um sistema que consistia na separação dos números em grupos
de 9 elementos, que eram simbolizados por letras: as nove letras iniciais representavam
1Nessa mesma época, existia uma outra maneira de representar números. Veja [10].
1.2. UM POUCO SOBRE SISTEMAS DE NUMERAÇÃO 3
os números de 1 a 9; as nove letras seguintes as dezenas de 10 a 90 e os nove últimos
símbolos representavam as centenas de 100 a 900. Assim, temos a seguinte tabela2:
A B G D E F Z H �
1 2 3 4 5 6 7 8 9
I K L M N � O P Q
10 20 30 40 50 60 70 80 90
R S T U � X 	 
 M
100 200 300 400 500 600 700 800 900
Por exemplo, RIA representava o número 111. É interessante observar que aqui também
a ordem dos símbolos não altera o valor do número. (Para representar 1000, por
exemplo, os gregos de então utilizavam um sinal à esquerda do símbolo empregado
para representar 1: ´A.)
Mas essa notação aditiva tem um grande inconveniente: à medida que números
maiores são escritos, mais símbolos devem ser introduzidos para representá-los (já
que utilizar apenas os símbolos antes empregados torna a representação do número
demasiadamente extensa). Entretanto, esta dificuldade é superada atribuindo-se
importância à posição que um símbolo ocupa na representação de um número. Assim
já era o sistema desenvolvido pelos babilônicos por volta de 1800 A.C. Esses usavam
grupos de 60 elementos e seus símbolos eram combinações de cunhas verticais
à
(representando a unidade) e angulares
(representando a dezena), dando origem ao que se chama sistema sexagesimal - ainda
hoje utilizamos este sistema ao medir o tempo em horas, minutos e segundose os
ângulos em graus. Um símbolo em uma seqüência fica então multiplicado por 60
cada vez que avançamos uma casa à esquerda. Nos exemplos que se seguem temos
a representação de 1, 5, 14, 72 e 129, respectivamente:
à , m, U, à e q
(Uma exposição mais detalhada sobre sistemas posicionais será feita na Seção 1.3.)
Os babilônios também não tinham um símbolo que representasse o zero, mas nas
posições em que ele deveria aparecer era deixado um espaço em branco, ficando a
cargo do leitor a tarefa de adivinhar, pelo contexto, o valor correto que estava sendo
representado. Observe que um espaço vazio pode conter um ou mais zeros, na
2Alguns símbolos (isto é, letras) mudaram suas formas com o tempo; os símbolos relacionados com os
números 6, 90 e 900 foram abandonados no alfabeto grego de 24 letras, mas permaneceram em uso (com
aparências que evoluíram com o tempo) na representação de números.
4 CAPÍTULO 1. SISTEMAS DE NUMERAÇÃO
representação de um número. Por exemplo, à podia tanto representar 1 unidade ou
60 unidades ou 602 unidades...
Os mais antigos espécimens dos numerais utilizados pelos indianos foram
encontrados em pilares erguidos na Índia por volta de 250 A.C. Entretanto, nesses
antigos escritos ainda não existe um símbolo para o zero e a notação posicional
tampouco é empregada. Eles usavam um sistema de numeração com nove símbolos
representando os números de 1 a 9 e nomes para indicar cada potência de 10. Por
exemplo, escreviam 3 sata, 2 dasan, 7 para representar o número 327 e escreviam 1
sata, 6 para representar 106. A data exata da introdução na Índia da notação posicional
e de um símbolo para o zero não é conhecida, mas deve ter sido anterior a 800 D.C., pois
o matemático persa Al-Khowarizmi (∼ 780-850) descreve num livro escrito em 825 D.C.
um sistema hindu assim complementado.
A origem do zero é incerta; entretanto, os maias da América Central, que possuíam
um sistema vigesimal posicional, já faziam uso dele por volta de 300 D.C.
Atualmente, quase todos os povos do mundo usam o mesmo sistema de numeração
e aproximadamente os mesmos algoritmos para efetuar as operações básicas da
aritmética. Este sistema quase que universalmente adotado é conhecido como sistema
numérico hindu-arábico, por acreditar-se ter sido ele inventado pelos indianos e
introduzido na Europa pelos árabes.
Este sistema é decimal posicional. Ele é decimal, pois faz uso de dez símbolos
(chamados algarismos): nove para representar os números de um a nove e outro para
representar posições vazias ou o número zero. Usamos os algarismos 0, 1, 2, 3, 4, 5,
6, 7, 8 e 9. É posicional, pois todos os números podem ser expressos através desses
algarismos, que têm o valor alterado à medida que eles avançam para a esquerda na
representação do número: cada mudança para a esquerda multiplica seu valor por dez.
É o que passaremos a explicar.
1.3 A REPRESENTAÇÃO DE UM NÚMERO EM UMA BASE
Vimos, na seção anterior, que a cada sistema de numeração posicional está associado
um conjunto de símbolos (algarismos), a partir dos quais escrevemos todos os outros
números. Chamamos de base do sistema à quantidade destes símbolos. Por exemplo,
os babilônios usavam um sistema sexagesimal (isto é, de base 60) e hoje utilizamos o
sistema decimal, ou seja, de base 10.
A razão de utilizarmos base 10 é convencional e, provavelmente, é conseqüência do
fato de quase todos os povos terem usado os dedos das mãos para contar. Temos então
que no nosso sistema todo número pode ser representado por uma seqüência
anan−1 . . . a1a0,
1.3. A REPRESENTAÇÃO DE UM NÚMERO EM UMA BASE 5
em que cada algarismo ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. O que cada algarismo representa
depende de sua posição nessa seqüência, de acordo com a seguinte regra: cada vez que
deslocamos uma casa para a esquerda na seqüência acima, o valor do algarismo fica
multiplicado por dez.
Por exemplo, para representar o número de dias do ano na base 10, o nosso primeiro
passo consiste em formar grupos de dez dias, obtendo o diagrama abaixo, em que cada
"+" representa um dia e cada "O" indica um grupo de dez dias:
O O O O O O O O O O
O O O O O O O O O O
O O O O O O O O O O
O O O O O O + + + +
+
Como o número de grupos de dez dias é superior a nove, o nosso próximo
passo será repetir o processo anterior, formando novamente grupos de dez:
O O O O O O O O O O
O O O O O O O O O O
O O O O O O O O O O
O O O O O O + + + +
+
Obtemos assim três grupos com dez grupos de dez dias, seis grupos de dez dias e
cinco dias. Podemos, então, representar o número de dias do ano por 365: o algarismo
3 representa a quantidade de grupos formados por 10 grupos de 10 dias; o algarismo 6
o número de grupos de 10 dias excedentes a esses; e o algarismo 5 representa o número
de dias que sobraram quando da divisão em grupos de dez. Em outras palavras, como
o algarismo 6 está deslocado uma casa à esquerda na seqüência 365, seu valor é de 6
vezes 10 e como o algarismo 3 está deslocado duas casas à esquerda, seu valor é de 3
vezes 10 vezes 10. Isto significa que
365 = 3 · 10 · 10+ 6 · 10+ 5
= 3 · 102 + 6 · 10+ 5.
Generalizando: se o número de elementos de um conjunto é representado por uma
seqüência anan−1 . . . a1a0, este conjunto tem an grupos de 10n elementos, mais an−1
grupos de 10n−1 e assim por diante, até a1 grupos de 10 mais a0 elementos; ou seja,
ele tem
an · 10n + an−1 · 10n−1 + . . . + a1 · 10+ a0
elementos.
O que fizemos com grupos de dez poderíamos ter feito com grupos com
outro número de elementos. Por exemplo, se estivéssemos contando com os
6 CAPÍTULO 1. SISTEMAS DE NUMERAÇÃO
dedos da mão, o natural seria usar grupos de cinco. Teríamos então que
considerar cinco símbolos, um para cada número de um a quatro e outro para
indicar posições vazias. Usemos os símbolos 0, 1, 2, 3, 4 como os algarismos
desse sistema. Para representar o número trinta e dois na base 5 devemos,
de maneira análoga àquela utilizada para base 10, formar grupos de cinco:
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ +
Como obtivemos mais de cinco grupos de cinco elementos repetimos o processo
tendo então um grupo de cinco grupos de cinco elementos, um grupo de cinco
elementos e dois elementos. Logo a sua representação é 112, isto é:
32 = 1 · 52 + 1 · 5+ 2.
De maneira análoga, para representar o número vinte e cinco na base cinco, temos o
seguinte diagrama:
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
Logo, a sua representação é 100 já que só obtivemos um grupo de cinco grupos de
cinco elementos, isto é:
25 = 1 · 52 + 0 · 5+ 0.
Observe que nós poderíamos considerar a seqüência 112 como a representação de
1.3. A REPRESENTAÇÃO DE UM NÚMERO EM UMA BASE 7
um número na base 3 onde os algarismos considerados são 0, 1, 2. Para deixar claro que
a seqüência acima é a expressão de um número na base 5 nós escrevemos (112)5, ou seja
(112)5 = 1 · 52 + 1 · 5+ 2
(100)5 = 1 · 52 + 0 · 5+ 0.
Na verdade, não é difícil demonstrar que podemos ter sistemas de numeração
posicionais com qualquer base b ∈ N. Depois de escolhida a base b, escolhemos b
símbolos para representar os números de "0" a " b − 1". Se b ≤ 10, podemos utilizar
os nossos algarismos hindu-arábicos; se b > 10, podemos utilizar os nossos algarismos
hindu-arábicos de 0 até 9 e escrever outros símbolos (geralmente utilizamos letras) para
representar os números 10, . . . , b− 1.
Por exemplo, se b = 12 podemos utilizar os símbolos 0, 1, . . . , 9, c, d como
algarismos do nosso sistema, sendo que c representa o número dez e d
o número onze. Assim, para representar o número duzentos e oitenta e
seis na base 12, formamos grupos de doze elementos conforme o diagrama
abaixo, em que "O" representa um grupo (de doze) e cada "+" um elemento:
O O O O O O O O O O O O
O O O O O O O O O O O
+ + + + + + + + +
+
Obtemos portanto umgrupo com doze grupos de doze elementos, onze grupos de
doze elementos e dez elementos. Logo
286 = (1dc)12,
ou seja,
286 = 1 · 122 + d · 12+ c
= 1 · 122 + 11 · 12+ 10.
Assim, se b ∈N, qualquer número inteiro não-negativo a pode ser escrito como
a = anbn + . . . + a1b + a0,
em que os coeficientes ai, i = 0, 1, · · · , n tomam valores de 0 a b− 1.
O número a acima é representado posicionalmente na base b pela seqüência
anan−1 . . . a2a1a0
e escrevemos a = (anan−1 . . . a2a1a0)b. Convencionamos não escrever o subscrito b
quando estamos utilizando a base 10, que é a usual. Para cada i ∈ N, o símbolo ai
8 CAPÍTULO 1. SISTEMAS DE NUMERAÇÃO
representa, portanto, um múltiplo de alguma potência da base, a potência dependendo
da posição na qual o algarismo aparece, de modo que ao mover um símbolo uma casa
para a esquerda este tem seu valor multiplicado por b.
A afirmação que é possível representar um número natural a em uma base b faz parte
de um resultado conhecido como Teorema de Representação de um Número em uma
Base (Teorema 3.17), que garante não só a existência, mas também a unicidade dessa
representação, uma vez fixada a base. O que fizemos acima é a heurística que justifica
este resultado, que será demonstrado rigorosamente no Capítulo 3.
CAPÍTULO 2
INDUÇÃO E BOA ORDENAÇÃO
2.1 INTRODUÇÃO
Em matemática, palavras como "grande" ou "pequeno" têm pouco significado. Por
exemplo, no ano de 1742, em uma carta a Euler (1707 - 1783), Christian Goldbach (1690
- 1764) afirmou que acreditava que todo inteiro par maior1 do que 6 podia ser escrito
como a soma de dois primos ímpares (para a definição de número primo, veja a página
51). Certamente Goldbach intuiu esse resultado depois de ter observado que ele era
válido para alguns números: 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5 = 3 + 7, 12 = 7 + 5,
14 = 7 + 7 = 11 + 3, etc. Desde então muitas pessoas dedicaram-se a verificar a
conjectura para inteiros pares entre 6 e números muito grandes. Em 1940, a conjectura
havia sido verificada até 100 000. Em 1989, até 2 · 1010. Em 1998, até2 1014. Entretanto,
não podemos considerar a afirmativa de Goldbach verdadeira a partir desse fato, já que
1014 é um número insignificante comparado com a "maior parte" dos inteiros, ou mesmo
quando comparado com 1, 2 · 1080, a estimativa do número de prótons e elétrons no
Universo.
Na matemática, muitas vezes resultados são enunciados a partir da consideração de
casos particulares, como no exemplo acima. Mas eles só são tidos como verdadeiros se
puderem ser demonstrados (o que ainda não ocorreu com a conjectura de Goldbach),
isto é, deduzidos de resultados já conhecidos (teoremas, proposições, lemas, corolários,
etc.) ou então de afirmações aceitas como verdadeiras, embora não demonstradas
(axiomas, postulados, princípios). A teoria está fundamentada nestas últimas.
Neste capítulo trataremos dos números naturais a partir de um dos postulados que
os caracterizam, a saber, o Princípio de Indução Matemática. Veremos então como
utilizá-lo na demonstração de afirmações a respeito dos números naturais, entre as quais
aquela que chamamos "Princípio da Boa Ordenação".
1Goldbach formulou sua conjectura dizendo que todo inteiro positivo par era soma de dois primos
ímpares; naquela época, 1 era considerado um número primo.
2Para informações sobre os avanços mais recentes, veja em www.informatik.uni-giessen.de
9
10 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
2.2 DEDUÇÃO E INDUÇÃO
Para que se compreenda o Princípio de Indução Matemática é necessário saber
distinguir entre dedução e indução e como esses métodos são utilizados em Matemática.
Comecemos com uma série de exemplos de afirmações:
• TODO brasileiro alfabetizado fala português.
• TODO número terminado em zero é divisível por 5.
• As diagonais de TODO paralelogramo são bissectadas por seu ponto de
intersecção.
• Paulo fala português.
• As diagonais do paralelogramo ABCD são bissectadas por seu ponto de
intersecção.
• 140 é divisível por 5.
Analisando estas afirmações podemos dividi-las em dois grupos: gerais e
particulares. As três primeiras são gerais e as três últimas particulares.
A passagem de uma afirmação geral para uma particular é chamada dedução. Um
exemplo simples:
Todo brasileiro alfabetizado fala português. (a)
Paulo é um brasileiro alfabetizado. (b)
Paulo fala português. (c)
A afirmação (c) é obtida da afirmação geral (a) com o auxílio da afirmação (b).
A tentativa de generalização de uma afirmação particular, isto é, a passagem de uma
afirmação particular para uma geral, é chamada indução. Ilustremos com um exemplo.
Considere a seguinte afirmação particular:
140 é divisível por 5. (1)
Podemos fazer, com base nesta afirmação particular, uma série de afirmações gerais.
Por exemplo:
Todo número com três dígitos é divisível por 5. (2)
Todo número terminado em zero é divisível por 5. (3)
Todo número terminado em 40 é divisível por 5. (4)
Todo número cuja soma de seus algarismos é 5 é divisível por 5. (5)
2.2. DEDUÇÃO E INDUÇÃO 11
As afirmacões (2), (3), (4) e (5) são tentativas de generalização do caso particular (1).
As afirmações (3) e (4) são verdadeiras, enquanto (2) e (5) são falsas.
Temos então a seguinte questão: como poderíamos usar indução em Matemática
de forma a obter somente conclusões verdadeiras? Neste capítulo, apresentamos um
método que soluciona essa questão.
Consideremos, inicialmente, dois exemplos com generalizações inadmissíveis em
Matemática.
Exemplo 2.1 Seja
Sn =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
n(n + 1)
.
É fácil ver que:
S1 =
1
1 · 2 =
1
2
S2 =
1
1 · 2 +
1
2 · 3 =
2
3
S3 =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 =
3
4
S4 =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 +
1
4 · 5 =
4
5
Com base nos resultados obtidos afirmamos que, para todo número natural n,
Sn =
n
n + 1
. ¢
Exemplo 2.2 Considere o trinômio x2 + x + 41 (estudado por Euler). Fazendo x = 1
nesse trinômio, obtemos 43, um número primo. Substituindo x por 2, 3, · · · , 10,
obtemos, respectivamente, os números primos 47, 53, 61, 71, 83, 97, 113, 131, 151. Com
base nestes resultados, afirmamos que a substituição no trinômio de x por qualquer
natural dará como resultado um número primo. ¢
Por que este tipo de raciocínio é inadmissível em Matemática? A falha está no
fato de termos aceito uma afirmação geral com respeito a um número natural (n no
primeiro exemplo, x no segundo exemplo) somente com base no fato dessa afirmação
ser verdadeira para certos valores de n (ou de x).
O processo de indução é muito empregado em Matemática, mas devemos saber usá-
lo adequadamente. Assim, enquanto a afirmação geral do Exemplo 2.1 é verdadeira, a
afirmação geral do Exemplo 2.2 é falsa. De fato, se estudarmos mais cuidadosamente o
trinômio x2 + x + 41, veremos que sua soma é igual a um primo quando substituímos x
por 1, 2, . . . , 39. Mas, para x = 40, temos:
x2 + x + 41 = 402 + 40+ 41 = 40(40+ 1) + 41 = 41(40+ 1) = 412,
12 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
que é um número composto.
Apresentamos agora alguns exemplos de afirmações verdadeiras em certos casos
especiais, mas que são falsas em geral.
Exemplo 2.3 Considere n planos passando por um mesmo ponto tais que quaisquer 3
deles não contêm uma reta comum. Em quantas regiões eles dividem o espaço?
Ora, é fácil ver que: um plano divide o espaço em duas partes; dois planos passando
por um ponto dividem o espaço em 4 partes; três planos passando por um ponto, mas
não contendo uma reta em comum, dividem o espaço em 8 partes. Em vista disto,
parece que quando o número de planos aumenta de uma unidade, o número de partes
nas quais se divide o espaço é dobrado, e portanto 4 planos dividiriam o espaço em 16
partes.
Figura 2.1: Quatro planos, sendo que quaisquer três deles não contem uma reta em
comum, dividem o espaço em 14regiões. (Conte 7 regiões na parte frontal da figura!)
Contudo, observando a figura acima, vemos que o espaço fica dividido em 14
regiões. (Na verdade, pode-se provar que n planos, nas condições acima, dividem o
espaço em n(n− 1) + 2 partes). ¢
Exemplo 2.4 Considere os números:
22
0
+ 1 = 3, 22
1
+ 1 = 5, 22
2
+ 1 = 17, 22
3
+ 1 = 257, 22
4
+ 1 = 65537
2.3. INDUÇÃO: PRIMEIRA FORMA 13
que são primos. Fermat (1601 - 1665), matemático francês, conjecturou que todos os
números dessa forma (os quais são denominados números primos de Fermat) eram
primos. Entretanto, Euler descobriu, um século depois, que:
22
5
+ 1 = 4 294 967 297 = (641) · (6 700 417)
é um número composto. ¢
2.3 INDUÇÃO: PRIMEIRA FORMA
Os exemplos considerados anteriormente mostram que uma afirmação pode ser
válida em uma série de casos particulares e falsa em geral. Surge então a seguinte
questão: suponhamos que uma afirmação seja válida em muitos casos particulares e
que seja impossível considerar todos os casos possíveis — por exemplo, uma afirmativa
a respeito de todos os números naturais. Como se pode determinar se esta afirmativa é
válida em geral? Algumas vezes podemos resolver essa questão aplicando um método
particular de raciocínio, chamado Método de Indução Matemática (indução completa),
baseado no
Princípio da Indução Matemática - primeira forma:
Suponha que para cada número natural n se tenha uma afirmativa P(n) que satisfaça as
seguintes propriedades:
(i) P(1) é verdadeira;
(ii) sempre que a afirmativa for válida para um número natural arbitrário n = k, ela será válida
para o seu sucessor n = k + 1 (ou seja, P(k) verdadeira implica P(k + 1) verdadeira).
Então P(n) é verdadeira para todo número natural n.
Exemplo 2.5 (Modelo)
O Princípio da Indução Matemática pode também ser entendido através do seguinte
modelo. Suponhamos a existência de uma fila infinita de peças de dominó, colocadas
em pé e distribuídas como na Figura 2.2. Teremos certeza de que, golpeando a primeira
peça de dominó, todas cairão se:
• a primeira peça cair ao ser golpeada;
• as peças de dominó estiverem espaçadas de tal modo que, quando uma delas cai,
atinge e faz cair a seguinte.
14 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
Figura 2.2: As peças de dominó estão espaçadas de tal forma que, se uma cair, a seguinte
também cairá. ¢
Uma demonstração baseada no Princípio da Indução Matemática é chamada prova
por indução. Tal demonstração deve, necessariamente, consistir em duas partes, ou
seja, da prova de dois fatos independentes:
FATO 1: a afirmação é verdadeira para n = 1;
FATO 2: a afirmação é válida para n = k + 1 se ela for válida para n = k, em que k é
um número natural arbitrário.
Se ambos estes fatos são provados então, com base no Princípio da Indução
Matemática, concluímos que a afirmação é válida para todo número natural n.
As hipóteses do Princípio da Indução (quer dizer, os Fatos 1 e 2) possuem
significados específicos. A primeira hipótese cria, digamos assim, a base para se fazer
a indução. A segunda hipótese nos dá o direito de passar de um número inteiro para o
seu sucessor (de k para k + 1), ou seja, o direito de uma extensão ilimitada desta base.
(Veja o exemplo das peças de dominó). Quer dizer, como P(1) é verdadeira, podemos
concluir que P(2) também é. Mas, sendo P(2) verdadeira, podemos concluir que P(3) é
verdadeira, e assim sucessivamente.
2.3. INDUÇÃO: PRIMEIRA FORMA 15
Observação 2.6 O Fato 2 contém uma implicação. Portanto, possui uma hipótese (P(k)
é verdadeira) e uma tese (P(k + 1) é verdadeira). Consequentemente, provar o Fato 2
significa provar que a hipótese acarreta a tese. A hipótese do Fato 2 é chamada hipótese
de indução. ¢
Exemplo 2.7 Calcular a soma
Sn =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + · · ·+
1
n(n + 1)
.
Sabemos que S1 = 12 , S2 =
2
3 , S3 =
3
4 , S4 =
4
5 .
Agora não repetiremos o engano cometido no exemplo 2.1. Examinando as somas
S1, S2, S3, S4, tentaremos provar, usando o método da indução matemática que
Sn =
n
n + 1
para todo natural n.
Para n = 1 a afirmativa é verdadeira, pois S1 = 12 .
Suponhamos que a afirmativa seja verdadeira para n = k, isto é,
Sk =
1
1 · 2 +
1
2 · 3 + . . . +
1
k(k + 1)
=
k
k + 1
.
Provaremos que a hipótese é verdadeira para n = k + 1, isto é,
Sk+1 =
k + 1
k + 2
.
De fato,
Sk+1 =
1
1 · 2 +
1
2 · 3 + · · ·+
1
k(k + 1)
+
1
(k + 1)(k + 2)
= Sk +
1
(k + 1)(k + 2)
.
Pela hipótese de indução, Sk = kk+1 . Logo,
Sk+1 = Sk +
1
(k + 1)(k + 2)
=
k
k + 1
+
1
(k + 1)(k + 2)
=
k2 + 2k + 1
(k + 1)(k + 2)
=
k + 1
k + 2
.
Verificadas as hipóteses do Princípio da Indução Matemática, podemos então
afirmar que, para todo natural n,
Sn =
n
n + 1
. ¢
É necessário enfatizar que uma prova pelo Princípio da Indução Matemática requer
provas de ambas as suas hipóteses (ou seja, os Fatos 1 e 2). Já vimos, pelo Exemplo
2.2, como uma atitude negligente para com a segunda hipótese do Princípio da Indução
pode nos levar a resultados falsos. O exemplo seguinte mostra que tampouco podemos
omitir sua primeira hipótese.
16 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
Exemplo 2.8 Seja Sn = 1+ 2+ 3+ · · ·+ n e consideremos a conjectura
Sn =
1
8
(2n + 1)2.
Suponhamos que a afirmativa seja válida para um número natural n = k, isto é,
Sk =
1
8
(2k + 1)2.
Então temos que
Sk+1 = Sk + (k + 1) =
1
8
(2k + 1)2 + (k + 1) =
1
8
(4k2 + 12k + 9) =
1
8
(2(k + 1) + 1)2,
o que mostra que o Fato 2 se verifica.
Entretanto, é fácil verificar que esta conjectura não é verdadeira para qualquer
número natural n. Por exemplo,
S1 = 1 6= 18(2+ 1)
2.
Pode-se provar que3
Sn =
n(n + 1)
2
,
que é diferente de 18(2n + 1)
2 para todo n ∈N. ¢
Exemplo 2.9 Retornemos ao exemplo 2.2 para clarear um aspecto significativo do
método da indução matemática. Examinando a soma
Sn =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + · · ·+
1
n(n + 1)
,
para alguns valores de n, obtivemos S1 = 12 , S2 =
2
3 , S3 =
3
4 , · · · e estes resultados
particulares sugeriram a hipótese de que, para todo n,
Sn =
n
n + 1
,
o que foi provado no Exemplo 2.7.
Poderíamos ter feito a seguinte conjectura:
Sn =
n + 1
3n + 1
.
3Veja o Exercício 1 (a).
2.3. INDUÇÃO: PRIMEIRA FORMA 17
A fórmula acima é verdadeira para n = 1, já que S1 = 12 .
Suponhamos que ela seja verdadeira para n = k, isto é,
Sk =
k + 1
3k + 1
.
Tentaremos provar que ela também é verdadeira para n = k + 1, isto é, que
Sk+1 =
k + 2
3k + 4
.
Entretanto,
Sk+1 = Sk +
1
(k + 1)(k + 2)
=
k + 1
3k + 1
+
1
(k + 1)(k + 2)
=
k3 + 4k2 + 8k + 2
(k + 1)(k + 2)(3k + 1)
,
o que não confirma a nossa conjectura. ¢
O exemplo acima teve o intuito de mostrar que, se fizermos uma afirmativa
incorreta, não conseguiremos demonstrá-la pelo método de indução.
O Método de Indução Matemática se baseia no fato de que, depois de cada número
inteiro k, existe um sucessor (k + 1) e que cada número inteiro maior do que 1 pode ser
alcançado mediante um número finito de passos, a partir de 1. Portanto é, muitas vezes,
mais conveniente enunciá-lo do seguinte modo:
Teorema 2.10 (Formulação equivalente do Princípio da Indução)
Seja S ⊂N um subconjunto tal que:
(i) 1 ∈ S;
(ii) sempre que k ∈ S tem-se que (k + 1) também pertence a S.
Então podemos afirmar que S =N.
Exemplo 2.11 Para mostrar que
1
1 · 2 +
1
2 · 3 + . . . +
1
n(n + 1)
=
n
n + 1
para todo n ≥ 1,
poderíamos ter considerado o conjunto
S =
{
n ∈N : 1
1 · 2 +
1
2 · 3 + . . . +
1
n(n + 1)
=
n
n + 1
}
e então, pelos mesmos argumentos utilizados no exemplo 2.7, concluiríamos que 1 ∈ S
e, se k ∈ S, então (k + 1) ∈ S. Logo, poderíamos concluir que S =N, ou seja, a fórmula1
1 · 2 +
1
2 · 3 + . . . +
1
n(n + 1)
=
n
n + 1
é verdadeira para todo n ∈N. ¢
18 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
Observação 2.12 Não é essencial começarmos a indução em n = 1. Dada uma
afirmativa a respeito de números inteiros, algumas vezes essa afirmativa faz sentido
para todos os inteiros maiores do que um inteiro n0 fixo4. Assim, podemos reescrever o
Princípio da Indução Matemática da seguinte forma:
Teorema 2.13 (Formulação equivalente do Princípio da Indução)
Suponha que, para cada número inteiro n ≥ n0, se tenha uma afirmativa P(n) que satisfaça
as seguintes propriedades:
(i) P(n0) é verdadeira;
(ii) sempre que a afirmativa for válida para um inteiro n = k ≥ n0, ela também será válida
para n = k + 1.
Então P(n) é verdadeira para todo número inteiro n ≥ n0.
No modelo das peças de dominó (Exemplo 2.5), se tivéssemos escolhido a quarta
peça para ser golpeada inicialmente, poderíamos afirmar que todas as peças seguintes
cairiam. (Nesse exemplo não faz sentido considerar inteiros não-positivos.) ¢
2.4 INDUÇÃO: SEGUNDA FORMA
Apresentaremos a seguir uma formulação alternativa do Princípio da Indução.
Como veremos no exemplo abaixo, esta formulação será útil nos casos em que a
validade de P(k + 1) não puder ser obtida facilmente da validade de P(k), mas sim
da validade de algum P(m), em que 1 ≤ m ≤ k.
Exemplo 2.14 Considere a seqüência de Fibonacci (∼ 1170-1250)
1, 1, 2, 3, 5, 8, 13, 21, . . . (2.1)
em que cada elemento, a partir do terceiro, é a soma dos dois anteriores. Se Fn denota o
n-ésimo termo dessa seqüência, podemos defini-la por:
F1 = 1
F2 = 1
Fn = Fn−2 + Fn−1, se n ≥ 3.
Os termos da seqüência de Fibonacci satisfazem a desigualdade
Fn <
(
7
4
)n
para todo n ≥ 1. (2.2)
Tentaremos mostrar a desigualdade (2.2) usando a primeira forma do Princípio da
Indução.
4No exemplo 2.4 começamos considerando n = 0. No exemplo 2.2 poderíamos ter considerado
qualquer número inteiro x.
2.4. INDUÇÃO: SEGUNDA FORMA 19
A desigualdade é verdadeira para n = 1 e n = 2. Suponhamos que P(k) seja válida,
isto é, suponhamos que Fk < (74)
k. Devemos mostrar que Fk+1 < (74)
k+1.
Suponhamos k ≥ 2. Como k + 1 ≥ 3, então Fk+1 = Fk + Fk−1 e não fica claro como
obter a desigualdade desejada a partir da hipótese de indução. Observe que
Fk−1 ≤ Fk
e então
Fk+1 = Fk + Fk−1 ≤ Fk + Fk < 2
(
7
4
)k
=
(
8
7
)(
7
4
)k+1
,
que é uma quota maior de que a desejada.
Entretanto, se além de Fk <
(
7
4
)k
, soubéssemos que Fk−1 <
(
7
4
)k−1
, teríamos
Fk+1 = Fk + Fk−1 <
(
7
4
)k
+
(
7
4
)k−1
=
(
7
4
)k−1 (7
4
+ 1
)
,
donde
Fk+1 <
(
7
4
)k−1 (7
4
)2
=
(
7
4
)k+1
.
¢
Observação 2.15 (A seqüência de Fibonacci e o problema dos coelhos).
A seqüência (2.1) tem o seu nome devido ao matemático italiano Leonardo de Pisa,
mais conhecido como Fibonacci, autor de Liber abaci (Livro sobre o ábaco), escrito em
1202, que contém grande parte do conhecimento aritmético e algébrico desta época e
que teve grande influência no desenvolvimento da Matemática na Europa Ocidental.
Neste livro Fibonacci formulou e resolveu o seguinte problema:
Os coelhos se reproduzem rapidamente. Admitamos que um par de coelhos adultos
produza um casal de coelhos jovens todo mês, e que os coelhos recém-nascidos se
tornem adultos em dois meses e produzam, por sua vez, nessa época, um outro casal
de coelhos. Começando com um casal jovem, de que tamanho estará a colônia após
um certo número de meses?
Se começarmos com um casal recém-nascido, durante o primeiro e o segundo meses
teremos somente este casal. No terceiro mês nasce um novo casal, de modo que agora
existem dois casais. No quarto mês o casal original produziu outro par, existindo então
três casais. Um mês mais tarde, tanto o par original quanto o primeiro casal nascido
produziram novos casais, de forma que agora existem dois casais adultos e três casais
20 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
jovens. Os dados podem ser colocados na seguinte tabela:
Crescimento de uma colônia de coelhos
meses casais adultos casais jovens total
1 - 1 1
2 - 1 1
3 1 1 2
4 1 2 3
5 2 3 5
6 3 5 8
Se denotarmos por Fn o número total de casais de coelhos no n-ésimo mês então Fn
é o n-ésimo termo da seqüência de Fibonacci. ¢
Para facilitar a solução de problemas como o que surgiu no exemplo 2.14, podemos
fazer uso da segunda forma do Princípio da Indução, que enunciaremos a seguir.
Teorema 2.16 (Princípio da Indução Matemática - segunda forma)
Seja a um número inteiro. Suponha que, para todo inteiro n ≥ a, se tenha uma afirmativa
P(n) que satisfaça as seguintes propriedades:
(i) P(a) é verdadeira;
(ii) P(m) verdadeira para todo natural m com a ≤ m ≤ k implica P(k + 1) verdadeira.
Então P(n) é verdadeira para todo n ≥ a.
Observação 2.17 Note que aqui também a condição (ii) consiste em uma implicação.
Sua hipótese, como antes, é chamada hipótese de indução. A diferença entre as duas
formas do Princípio de Indução Matemática está exatamente na hipótese de indução:
na primeira forma, supõe-se que P(k) seja verdadeira e, na segunda, supõe-se que
P(k), P(k− 1), . . . , P(a + 1), P(a)
sejam todas verdadeiras. ¢
Voltemos ao exemplo anterior.
Exemplo 2.18 (Continuação do Exemplo 2.14)
Vamos reescrever formalmente, utilizando a segunda forma do Princípio da
Indução, o que já foi feito anteriormente.
Seja P(n) a afirmativa (2.2): Fn <
(
7
4
)n
para todo n ∈N.
2.4. INDUÇÃO: SEGUNDA FORMA 21
Se k = 1, Fk+1 = F2 = 1 <
(
7
4
)2
. Assim, P(1) é verdadeira. Seja k ≥ 2 e
suponhamos que P(m) seja verdadeira para todo 1 ≤ m ≤ k. Precisamos mostrar que
P(k + 1) é verdadeira, ou seja,
Fk+1 <
(
7
4
)k+1
.
Se k ≥ 2, Fk+1 = Fk + Fk−1. Temos, por hipótese de indução, que
Fk <
(
7
4
)k
e Fk−1 <
(
7
4
)k−1
.
Consequentemente:
Fk+1 <
(
7
4
)k
+
(
7
4
)k−1
=
(
7
4
)k (
1+
4
7
)
=
(
7
4
)k (11
7
)
<
(
7
4
)k (7
4
)
=
(
7
4
)k+1
.
Portanto, Fk+1 <
(
7
4
)k+1
, como queríamos demonstrar. ¢
A segunda forma do Princípio de Indução é uma afirmativa sobre os números
naturais e faz sentido tentar prová-la usando a primeira forma. Faremos isto a seguir.
Demonstração da segunda forma do Princípio de Indução: Para mostrar que a
afirmativa P(n) é verdadeira para todo natural n ≥ a, consideraremos o conjunto
S = {n ∈ Z : n ≥ a e P(a), P(a + 1), . . . , P(n) são verdadeiras}
e mostraremos, usando a primeira forma do Princípio de Indução, que
S = {n ∈ Z : n ≥ a}.
Pela condição (i) temos que P(a) é verdadeira, ou seja, a ∈ S. Seja k ≥ a tal que
k ∈ S. Logo, pela definição de S, P(a), P(a + 1), . . . , P(k) são verdadeiras e então, pela
condição (ii), temos que P(k + 1) também é verdadeira, donde (k + 1) ∈ S.
Temos então, pelo Teorema 2.10, que todos os inteiros n tais que n ≥ a pertencem a
S, isto é:
S = {n ∈ Z : n ≥ a},
donde P(n) é verdadeira para todo n ≥ a. 2
22 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
2.5 O PRINCÍPIO DA BOA ORDENAÇÃO
Além do Princípio da Indução Matemática, uma outra propriedade importante dos
números naturais é o Princípio da Boa Ordenação, também conhecido com Princípio
do Menor Inteiro. Tal princípio também é muito útil na demonstração de resultados a
respeito dos números inteiros.
Dizemos que um conjunto S ⊂ R é limitado inferiormente se existe um número
a ∈ R tal que a ≤ s para todo s ∈ S. Nesse caso, a é uma cota inferior para o conjunto
S. Se a cota inferior está no conjunto S, dizemos que a é o menor elemento de S.
Teorema 2.19 (Princípio da Boa Ordenação)
Seja S ⊂ Z um conjunto não-vazio e limitado inferiormente. Então S possui um menor
elemento.
Exemplo 2.20 No conjunto {7, 9, 11, 13, 15, . . .} dos números ímpares maioresdo que 5,
temos que 7 é o menor elemento. ¢
Exemplo 2.21 O conjunto dos números inteiros
Z = {0,±1,±2,±3, . . .}
não possui menor elemento, pois se z ∈ Z então (z− 1) ∈ Z, isto é, Z não é limitado
inferiormente. ¢
De acordo com o exemplo anterior, não podemos esperar que conjuntos não
limitados inferiormente possuam um menor elemento. O próximo exemplo mostra
que mesmo conjuntos que são limitados inferiormente podem não possuir um menor
elemento.
Exemplo 2.22 Considere o conjunto dos números racionais positivos
Q+ =
{m
n
: m e n são naturais positivos
}
,
isto é, o conjunto de todas as frações positivas. Note que 0 é menor que todos os
elementos de Q+, donde Q+ é limitado inferiormente.
Como 0 6∈ Q+, 0 não é o menor elemento de Q+. Vamos mostrar que Q+ não possui
menor elemento. Suponhamos, por absurdo, que a ∈ Q+ seja o menor elemento deQ+.
Então, vemos, facilmente, que a2 também pertence a Q
+. Como a2 < a chegamos a uma
contradição. ¢
Consideremos, agora, uma afirmativa P(n) a respeito dos números naturais maiores
do que a. Temos então duas possibilidades:
• P(n) é verdadeira para todo número inteiro n ≥ a, ou
• existe pelo menos um número inteiro n ≥ a tal que P(n) é falsa.
2.5. O PRINCÍPIO DA BOA ORDENAÇÃO 23
Observemos que essas possibilidades são exclusivas, ou seja, se uma é verdadeira, a
outra é falsa. Uma maneira de verificarmos que a primeira possibilidade é verdadeira
é aplicar o Princípio da Indução. Entretanto, podemos concluir que a primeira
possibilidade é verdadeira mostrando que a segunda é falsa.
Uma das maneiras de aplicarmos o Princípio da Boa Ordenação (outra será vista
posteriormente) na demonstração de resultados sobre os inteiros é justamente esta:
supomos que a segunda possibilidade seja verdadeira e consideramos então o conjunto
F = {n ∈ Z : n ≥ a e P(n) é falsa}.
Se a segunda possibilidade for verdadeira, F 6= ∅. Aplicamos então o Princípio da
Boa Ordenação, tomamos o menor elemento de F e tentamos obter uma contradição. Se
obtivermos esta contradição, necessariamente concluiremos que F = ∅, o que implica
que a primeira possibilidade é verdadeira. Este é o procedimento que usaremos no
seguinte exemplo.
Exemplo 2.23 Vamos mostrar, usando o Princípio da Boa Ordenação, que
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
n(n + 1)
=
n
n + 1
para todo n ≥ 1,
o que já foi provado aplicando-se a primeira forma do Princípio da Indução.
Seja Sn =
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
n(n + 1)
. Queremos mostrar que
F =
{
n ∈N : Sn 6= nn + 1
}
é o conjunto vazio. Vamos supor que F 6= ∅ e então obteremos uma contradição, donde
a única alternativa é concluirmos que F = ∅ e, portanto, que Sn = nn+1 para todo n ∈N.
Ora, se F 6= ∅, então o Princípio da Boa Ordenação se aplica. Logo, existe a ∈ F tal
que a ≤ n para todo n ∈ F. Assim,
Sa 6= aa + 1.
Temos que a > 1 pois S1 = 12 =
1
1+1 (isto implica 1 6∈ F). Como a é o menor elemento
para o qual a afirmativa é falsa,
Sa−1 =
a− 1
(a− 1) + 1 =
a− 1
a
.
Somando 1a(a+1) em ambos os lados, obtemos
1
1.2
+
1
2.3
+ · · ·+ 1
(a− 1)a +
1
a(a + 1)
=
a− 1
a
+
1
a(a + 1)
.
24 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
Mas o lado esquerdo é Sa, enquanto a−1a +
1
a(a+1) =
a
a+1 (verifique!).
Portanto,
Sa =
a
a + 1
,
o que contradiz
Sa 6= aa + 1
Concluímos então que F = ∅, o que prova nossa afirmativa. ¢
Em geral, qualquer resultado sobre os números inteiros que pode ser demonstrado
usando-se o Princípio da Indução, também pode ser demonstrado usando-se o Princípio
da Boa Ordenação.
Demonstraremos agora o Princípio da Boa Ordenação, usando a segunda forma do
Princípio da Indução. A primeira vista bastaria usar o seguinte procedimento: dado um
conjunto S ⊂ Z de inteiros maiores do que o inteiro a, verificamos se a ∈ S. Se a ∈ S,
então a é o menor elemento de S, pois S ⊂ Z é um conjunto de inteiros maiores do que
a. Se a 6∈ S, verificamos se a + 1 ∈ S. Se a + 1 ∈ S então a + 1 é o menor elemento de
S pois a 6∈ S e S é um conjunto de inteiros maiores do que a. Se a + 1 6∈ S, verificamos
se a+ 2 ∈ S, e assim sucessivamente. O primeiro elemento pertencente a S seguindo tal
procedimento seria o menor elemento de S.
Este processo, entretanto, é difícil de ser formalizado. Adotaremos um método
alternativo: consideraremos um conjunto S ⊂ Z de inteiros maiores do que o inteiro
a e suporemos que S não possui menor elemento; provaremos que este conjunto só
pode ser o conjunto vazio, donde podemos concluir que, se S é um conjunto de inteiros
maiores do que o inteiro a e S 6= ∅, então S possui menor elemento.
Demonstração do Princípio da Boa Ordenação: Seja S ⊂ Z um conjunto não-vazio e
limitado inferiormente. Seja a ∈ Z uma cota inferior para S. Suponhamos que S não
possua menor elemento.
Temos então que a 6∈ S pois, caso contrário, a seria o menor elemento de S.
Suponhamos que a, a+ 1, a+ 2, . . . , a+ k não estejam em S (segunda forma do Princípio
da Indução). Afirmamos que a+(k+ 1) 6∈ S. De fato, se a+(k+ 1) ∈ S então a+(k+ 1)
seria o menor elemento de S, pois todos os inteiros maiores do que a e menores do
que a + (k + 1) não estão em S; como S não possui menor elemento, concluímos que
a + (k + 1) 6∈ S. Logo, pela segunda forma do Princípio da Indução, nenhum elemento
de Zmaior do que a está em S.
Como S ⊂ Z é um conjunto de números maiores do que a, só podemos ter S = ∅.
Concluímos que a única possibilidade de S não possuir menor elemento é quando
S = ∅, o que mostra o Princípio da Boa Ordenação. 2
2.6. PRINCÍPIOS OU TEOREMAS? 25
2.6 PRINCÍPIOS OU TEOREMAS?
A segunda forma do Princípio de Indução e o Princípio da Boa Ordenação foram
apresentados como teoremas: a segunda forma do Princípio de Indução foi provada
utilizando-se a primeira forma, enquanto o Princípio da Boa Ordenação resultou da
segunda forma do Princípio de Indução. Mantivemos, entretanto, a denominação de
"Princípios" para esses resultados. Qual a razão desse procedimento?
Dizemos que duas afirmações A e B são equivalentes se A implica B (notação:
A ⇒ B) e, reciprocamente, B implica A (notação: B ⇒ A) e escrevemos A ⇔ B, que
se lê: A se, e somente se, B. (Para uma discussão mais detalhada desta linguagem veja
[16], pp. 38-47.) Quer dizer, a afirmativa A é verdadeira se, e somente se, a afirmativa B
for verdadeira.
Observe que já demonstramos que a primeira forma do Princípio de Indução
implica a segunda forma, e que essa implica o Princípio da Boa Ordenação. Assim,
para completarmos a verificação que esses Princípios são todos equivalentes, basta
mostrarmos que o Princípio da Boa Ordenação implica a primeira forma do Princípio
da Indução. É o que faremos agora. Uma vez mostrado esse resultado, poderemos
concluir que todas essas afirmativas são equivalentes: não importa qual aceitemos como
verdadeira, as outras também serão verdadeiras.
Teorema 2.24 O Princípio da Boa Ordenação implica a primeira forma do Princípio de Indução.
Demonstração: Seja P(n) uma afirmativa à respeito dos números inteiros, tais que
(a) P(n0) é verdadeira;
(b) se k ≥ n0, P(k) verdadeira implica P(k + 1) verdadeira.
Queremos mostrar que P(n) é verdadeira para todo n ≥ n0. Para isso, definimos o
conjunto
S = {n ∈ Z : n ≥ n0 e P(n) é falsa.}.
Vamos mostrar, usando o Princípio da Boa Ordenação, que S = ∅, donde podemos
concluir o desejado.
Claramente S é um conjunto limitado inferiormente. Suponhamos que S não seja
vazio. Então, pelo Princípio da Boa Ordenação, S tem um menor elemento k0 ∈ S.
Temos que k0 6= n0 pois, por hipótese, P(n0) é uma afirmação verdadeira. Logo, k0 > n0.
Isso quer dizer que k0 − 1 6∈ S e também que P(k0 − 1) é uma afirmação verdadeira
(pois k0 é a primeira afirmativa falsa). Mas isso é uma contradição com a hipótese (b):
P(k0 − 1) verdadeira implica P(k0) verdadeira. 226 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
2.7 EXERCÍCIOS
1. Verifique, por indução, que as seguintes fórmulas são válidas para n ≥ 1:
(a) 1+ 2+ 3+ . . . + n =
n(n + 1)
2
;
(b) 5+ 9+ 13+ . . . + (4n + 1) = n(2n + 3);
(c) 1+ 4+ 9+ . . . + n2 =
n(n + 1)(2n + 1)
6
;
(d) 1 · 2+ 2 · 3+ 3 · 4+ . . . + n(n + 1) = n(n + 1)(n + 2)
3
;
(e) 1+ 23 + 33 + . . . + n3 =
(
n(n + 1)
2
)2
;
(f) (1+ 25 + 35 + . . . + n5) + (1+ 27 + 37 + . . . + n7) = 2
(
n(n + 1)
2
)4
.
Usando indução, é possível provar regras conhecidas. Os Exercícios 2 e 3 tratam de
progressões aritméticas e geométricas. Relembramos suas definições:
Definição 2.25 Uma progressão aritmética de razão r e termo inicial a1 é uma seqüência
a1, a2, . . . , an, . . .
em que a diferença de dois termos consecutivos é sempre igual a r, isto é,
an − an−1 = r, ∀ n ≥ 2.
Uma progressão geométrica de razão q 6= 1 e termo inicial a1 é uma seqüência
a1, a2, . . . , an, . . .
em que o quociente an/an−1 é sempre igual a q, para todo n ≥ 2.
2. Considere uma progressão aritmética de razão r e termo inicial a1. Usando
indução, prove que:
(a) an = a1 + (n− 1)r;
(b) mostre que a soma Sn dos n primeiros termos desta progressão, é dada por
Sn =
n(a1 + an)
2
.
3. Considere uma progressão geométrica de razão q 6= 1 e termo inicial a1. Usando
indução, prove que:
(a) an = a1qn−1;
2.7. EXERCÍCIOS 27
(b) mostre que a soma Sn dos n primeiros termos desta progressão, é dada por
Sn = a1
1− qn
1− q .
Às vezes, antes de aplicar o método de indução, precisamos formular uma lei que
englobe alguns casos considerados. É o que acontece nos próximos exercícios:
4. Encontre a lei geral sugerida e em seguida demonstre-a por indução.
(a) 1+
1
2
= 2− 1
2
, 1+
1
2
+
1
4
= 2− 1
4
, 1+
1
2
+
1
4
+
1
8
= 2− 1
8
(b) 1− 1
2
=
1
2
,
(
1− 1
2
)(
1− 1
3
)
=
1
3
,
(
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
=
1
4
(c) 1 = 1, 1− 4 = −(1+ 2), 1− 4+ 9 = 1+ 2+ 3,
1− 4+ 9− 16 = −(1+ 2+ 3+ 4).
5. Deduza a expressão geral que exprime de modo simplificado o produto:(
1− 1
4
)(
1− 1
9
)
. . .
(
1− 1
n · n
)
.
Demonstre o resultado por indução.
6. (a) Seja A =
(
1 1
0 1
)
. Calcule A2 e A3 para determinar uma possível fórmula
para An , n ∈N.
(b) Demonstre o resultado obtido em (a) por indução.
Também podemos aplicar o método de indução para provar desigualdades. Vejamos:
7. Mostre, por indução, que:
(a) 1+ n ≤ 2n para todo inteiro n ≥ 0;
(b) 2n < n! para todo n ≥ 4, n ∈N;
(c) Para todo a ∈ R, a < 0 temos a2n > 0 e a2n−1 < 0 para todo n ∈N.
(d) Seja x ∈ R. Então (1+ x)2n > 1+ 2nx para todo n ∈N.
(e) Seja x ∈ R, 0 < x < 1. Então (1− x)2n ≥ 1− 2nx para todo n ∈N.
(f) Se a > 0 e x > 0 são números reais, então
(a + x)n ≥ an + nxan−1
para todo n ∈N.
Resultados a respeito de somatórios também podem ser provados por indução.
Relembramos a notação de somatório:
28 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
Definição 2.26 Se n ∈ N e ai ∈ R para i ∈ N com 1 ≤ i ≤ n, indicamos a soma
a1 + a2 + · · ·+ an por
n
∑
i=1
ai
e lemos "somatório de ai, com i variando de 1 a n".
Se m e n são inteiros, com m ≤ n, definimos5
n
∑
i=m
ai = am + am+1 + . . . + an.
8. Demonstre as seguintes propriedades dos somatórios.
(a)
n
∑
i=1
(ai ± bi) =
(
n
∑
i=1
ai
)
±
(
n
∑
i=1
bi
)
;
(b)
n
∑
i=1
kai = k
(
n
∑
i=1
ai
)
;
(c)
n
∑
i=1
(ai + a) =
(
n
∑
i=1
ai
)
+ na;
(d)
n
∑
i=1
(
n
∑
j=1
aij
)
=
n
∑
j=1
(
n
∑
i=1
aij
)
.
9. Mostre que
n
∑
j=1
n
∑
i=1
aibj =
n
∑
i=1
ai
n
∑
j=1
bj.
Podemos também usar dois índices no mesmo somatório. Para isso definimos, tendo
como base a propriedade (d) do Exercício 8,
Definição 2.27
n
∑
i,j=1
aij =
n
∑
i=1
n
∑
j=1
aij.
5Por exemplo, temos:
6
∑
i=1
i = 1+ 2+ 3+ 4+ 5+ 6 = 21
e
6
∑
j=3
(7− 3j) = (7− 3 · 3) + (7− 3 · 4) + (7− 3 · 5) + (7− 3 · 6) = −26.
Observe que
n
∑
i=1
i = n e
n
∑
i=1
k = kn.
2.7. EXERCÍCIOS 29
10. Calcule
(a)
n
∑
i=1
(5i + 3);
(b)
n
∑
i,j=1
aijaji, em que axy =
x
y
.
Também regras a respeito da potenciação de números reais podem ser provadas pelo
método de indução. Relembramos a definição pertinente:
Definição 2.28 Seja a ∈ R, com a 6= 0. Definimos:
a0 = 1 e aj = aaj−1, para todo j ∈N.
Se a = 0, definimos aj = 0 para todo j ∈ {0, 1, . . .}.
11. Sejam a ∈ R e m, n ∈ {0, 1, . . .}. Mostre, por indução:
(a) am · an = am+n;
(b) (am)n = am.n.
12. Mostre que, para todo n ∈N,
an − bn = (a− b)(an−1 + an−2b + · · ·+ bn−1) = (a− b)
n−1
∑
i=0
a(n−1)−ibi.
A fórmula do binômio de Newton (1642-1727) pode ser provada por indução.
Relembramos:
Definição 2.29 Sejam n, p ∈N, com 1 ≤ p ≤ n. Defina:
n! = n · (n− 1) · . . . · 3 · 2 · 1, 0! = 1 e
(
n
p
)
=
n!
p!(n− p)! .
13. (a) Demonstre a relação de Stiefel (1487-1567),(
n
p
)
=
(
n− 1
p− 1
)
+
(
n− 1
p
)
.
(b) Mostre, por indução, a fórmula do binômio de Newton:
(x + a)n =
n
∑
p=0
(
n
p
)
apxn−p, n ∈N.
14. (a) Sejam b e x números reais com x 6= 1. Mostre que, para todo n ∈N,
n−1
∑
j=0
bxj = b
xn − 1
x− 1 .
30 CAPÍTULO 2. INDUÇÃO E BOA ORDENAÇÃO
(b) Refaça (a) usando o resultado obtido no Exercício 3 (b).
(c) Observe que
n−1
∑
j=0
mj > n. Deduza então de (a) que n < mn, sendo m e n
naturais arbitrários e m > 1.
(d) Refaça (c) usando indução.
O próximo exercício apresenta algumas propriedades da seqüência de Fibonacci:
15. Seja Fi o i-ésimo termo da seqüência de Fibonacci. Mostre que:
(a) F1 + F2 + . . . + Fn = Fn+2 − 1
(b) F1 + F3 + . . . + F2n−3 + F2n−1 = F2n
(c) F2 + F4 + . . . + F2n−2 + F2n = F2n+1 − 1
(d) F21 + F
2
2 + . . . + F
2
n = FnFn+1
(e) Fm+n = Fm−1Fn + FmFn+1
(f) F2n+1 = FnFn+2 + (−1)n
(g) F2n−1 = F2n + F2n−1
Mesmo resultados geométricos podem ser provados por indução. O próximo exercício
é um exemplo:
16. (a) Prove que o número de diagonais dn de um polígono convexo de n lados é
dado por
dn =
n(n− 3)
2
.
(b) Prove que a soma Sn dos ângulos internos de um polígono convexo de n lados
é: Sn = (n− 2) · 180o.
A demonstração de uma afirmação pelo método de indução deve ser feita através de
aplicação criteriosa da hipótese de indução. Vejamos:
17. Explique o erro na seguinte "demonstração" por indução:
Proposição: "Em um conjunto de n bebês, todos têm a mesma cor de olhos".
Demonstração: Seja P(n) a afirmativa da proposição. Claramente P(1) é
verdadeira.
Suponhamos que P(k) seja verdadeira e consideremos que P(k + 1).
Seja um conjunto de k + 1 bebês.
Se escolhermos os k primeiros bebês do conjunto, como estamos supondo que
P(k) seja verdadeira, temos que todos têm os olhos da mesma cor. O mesmo é
2.7. EXERCÍCIOS 31
verdadeiro para os k últimos bebês. Mas então o primeiro bebê tem a mesma cor
de olhos que o segundo, que tem a mesma cor que os k últimos.
Assim P(k + 1) é verdadeira e, pelo Principio de Indução, P(n) é verdadeira para
todo natural n, o que prova a nossa proposição.
Nota: Este exemplo deve-se ao matemático húngaro G. Pólya (1887-1985),
professor da Universidade de Stanford (EUA), que sugeria ao leitor que
comprovasse experimentalmente a validade da proposição.
O Princípio da Boa Ordenação pode ser utilizado como alternativa ao Princípio da
Indução:
18. Refaça os exercícios 1, 4, 5 e 7 usando o Princípio da Boa Ordenação.
19. Defina conjunto limitado superiormente. Use o Princípio da Boa Ordenação para
provar que qualquer subconjunto dos inteiros não-vazio e limitado superiormente
tem um maior elemento.
(Sugestão: suponha que cada elementonesse conjunto, S, seja menor do que n.
Considere o conjunto de todos os números da forma n− s, onde s ∈ S.)
20. Adapte o enunciado do Teorema 2.10 para o caso de subconjunto S ⊂ Z. Quais
hipóteses devem ser feitas sobre S nesse caso?
CAPÍTULO 3
DIVISÃO EUCLIDIANA
3.1 INTRODUÇÃO
O mais antigo texto matemático grego completo que conhecemos é Os Elementos,
escrito por Euclides de Alexandria (∼ 325-265 A.C.) por volta de 300 A.C. Nesta
obra, escrita em treze volumes (cada um deles denominado "Livro"), Euclides
conseguiu incorporar praticamente todo o conhecimento matemático acumulado por
seus antecessores. O material é apresentado de forma sistemática, sendo a aplicação
mais antiga do método axiomático que chegou até nossos dias.
Os Livros VII, VIII e IX d’Os Elementos são sobre teoria de números. Para os gregos de
então, a palavra número significava o que hoje denominamos número natural e nesses
livros cada número é representado por um segmento de reta. Assim, Euclides se refere
a um número como AB e não usa as expressões "é múltiplo de" ou "é dividido por", mas
"é medido por" ou "mede", respectivamente. O modelo concreto de número utilizado
por Euclides era um segmento de reta de comprimento igual a esse número, sendo a
unidade de medida u escolhida arbitrariamente; por exemplo, o número 7 era entendido
como o segmento AB abaixo:
A
u
B
Uma característica dos inteiros é que um número nem sempre divide o outro e
Euclides interessava-se particularmente pelo estudo dessa relação, ou seja, pela teoria
da divisibilidade. Nos livros acima citados encontramos importantes resultados sobre
os inteiros – com demonstrações que são utilizadas até hoje, apenas reescritas numa
notação moderna.
Neste capítulo apresentaremos o resultado conhecido hoje como Lema da Divisão
de Euclides. A partir desse resultado, demonstraremos o Teorema da Representação
de um Número em uma Base qualquer b > 1 e obteremos também alguns critérios de
divisibilidade.
32
3.2. O ALGORITMO DA DIVISÃO 33
3.2 O ALGORITMO DA DIVISÃO
Retornando ao modelo de número utilizado por Euclides, dados dois segmentos de
reta AB e CD é natural comparar os seus comprimentos e nos perguntarmos sobre a
possibilidade de utilizar um deles para medir o outro. Assim, pode ser que o segmento
AB esteja contido um número exato de vezes no segmento CD, isto é, o segmento CD
pode ser obtido pela justaposição do segmento AB um certo número de vezes:
C D
A B
AB AB ABC D
Nesse caso, Euclides dizia que CD possuía AB como parte exata ou que AB servia
para medir CD. Assim
CD = AB + AB + AB = 3AB,
em que, aqui, a soma é a soma do número natural representado por AB. Obtemos daí a
definição de múltiplo. Damos a definição abstrata:
Definição 3.1 Dados os números naturais a e b, dizemos que a é múltiplo de b, se existe um
número natural n tal que a = nb.
Se o segmento AB não for uma parte exata do segmento CD, podemos considerar o
número máximo de segmentos do tamanho de AB que cabe em CD e obter um segmento
restante, que chamaremos MN, o qual possui comprimento menor do que o de AB:
C D
A
C
B
AB AB MN
D
Portanto, se os segmentos CD e AB representam os números naturais a e b,
respectivamente, temos que a = nb+ r, em que r < b é o número natural que representa
34 CAPÍTULO 3. DIVISÃO EUCLIDIANA
o segmento MN e n é o número máximo de segmentos do tamanho de AB que cabe em
CD.
Esse é o enunciado, para os números naturais, do que hoje chamamos Lema da
Divisão de Euclides, cuja prova pode ser encontrada no Livro VII d’Os Elementos.
Nosso objetivo agora é enunciar e demonstrar esse resultado, cuja veracidade parece
ser evidente pelo raciocínio acima, com uma linguagem atual.
Repetimos o processo heurístico apresentado acima, com uma linguagem um pouco
mais abstrata. Sejam a e b números naturais. Dispondo os números naturais sobre uma
semireta e destacando os múltiplos de b, obtemos uma divisão dessa em intervalos de
comprimento b
-
0 b 2b 3b 4b
e então vemos que existem somente duas possibilidades: ou a é múltiplo de b, isto é,
a = qb, em que q ∈N,
ou a está compreendido entre dois múltiplos consecutivos de b:
-
qb a (q + 1)b
Nesse último caso, temos que a distância de a a qb é menor do que a distância entre
dois múltiplos consecutivos de b. Assim, podemos escrever
a = qb + r, em que 0 < r < b.
Observação 3.2 Observe que, até agora, consideramos o "1" como o primeiro número
natural. No lema de Euclides, a seguir, consideraremos "0" como número natural. É
uma simples convenção a questão do zero ser ou não natural. No texto, adotaremos a
postura que for mais conveniente no momento. ¢
Passamos agora ao tratamento formal desse resultado de Euclides:
Lema 3.3 (Lema da Divisão de Euclides)
Sejam a e b números naturais, com b > 0. Então existem números naturais q e r, com
0 ≤ r < b, de modo que a = qb + r.
Demonstração: Faremos a demonstração por indução em a.
3.2. O ALGORITMO DA DIVISÃO 35
Se a = 0, escolhemos q = 0 e r = 0, obtendo 0 = 0 · b + 0. Neste caso, o resultado
está demonstrado.
Seja então a > 0 (inclusive menor que b) e suponhamos, por indução, que o resultado
seja válido para o número natural (a− 1): existem q′, r′ ∈N tais que
(a− 1) = q′b + r′, em que 0 ≤ r′ < b.
Logo,
a = q′b + r′ + 1 com 1 ≤ r′ + 1 ≤ b.
Se r′ + 1 < b, tomamos q = q′ e r = r′ + 1, o que mostra o resultado. Se, por outro
lado, r′ + 1 = b, temos que
a = q′b + b = (q′ + 1)b,
e basta tomar, nesse caso, q = q′ + 1 e r = 0. 2
Portanto, o Lema da Divisão de Euclides nos garante que, dados a, b ∈N, com b > 0,
sempre podemos achar o quociente q e o resto r da divisão de a por b, o que fazíamos
desde o ensino básico, para pares particulares de números naturais a e b.
Podemos agora nos perguntar se o quociente e o resto são únicos. A nossa
experiência nos diz que a resposta a essa pergunta é afirmativa: há muito tempo
sabemos que existe uma única "resposta certa" para a divisão de a por b. (Verifique
que esta unicidade fica clara ao considerarmos o nosso modelo geométrico).
Para demonstrar formalmente este fato, vamos supor que (q′, r′) e (q′′, r′′) sejam dois
pares de números naturais tais que
a = q′b + r′, a = q′′b + r′′, com 0 ≤ r′ < b e 0 ≤ r′′ < b.
Queremos concluir que
q′ = q′′ e r′ = r′′.
Se tivéssemos q′ > q′′, obteríamos (q′ − q′′)b = r′′ − r′, e como q′ − q′′ é um número
natural não-nulo, q′ − q′′ ≥ 1 e, portanto, (q′ − q′′)b ≥ b. Logo, obteríamos r′′ − r′ ≥ b,
o que é absurdo, já que 0 ≤ r′ < b e 0 ≤ r′′ < b. Assim, não podemos ter q′ > q′′.
Analogamente, não podemos ter q′′ > q′ e, portanto, q′ = q′′. Mas então
r′ = a− q′b = a− q′′b = r′′.
Provamos assim a unicidade no lema de divisão de Euclides.
Gostaríamos agora de estender o lema de Euclides para o conjunto dos inteiros
Z = {· · · ,−2,−1, 0, 1, 2, · · · }.
Esses podem ser representados sobre uma reta escolhendo um ponto arbitrário como
a posição do zero (chamado origem) e associando os pontos à direita do zero aos
números naturais e os pontos à esquerda do zero aos números negativos:
36 CAPÍTULO 3. DIVISÃO EUCLIDIANA
-
−2 −1 0 1 2
Temos então que o ponto correspondente a 2 fica à direita da origem e a duas
unidades dessa, enquanto que o número −2 fica à esquerda da origem, também a
duas unidades dessa. Assim a cada inteiro b está associado um número natural que
é a distância de b à origem chamado valor absoluto de b. Temos então a seguinte
Definição 3.4 O valor absoluto de um número inteiro b, denotado por |b|, é
|b| =
{
b, se b ≥ 0,
−b, se b < 0.
Observação 3.5 Para todo b ∈ Z, |b| é um número natural. Além disso, |b| = | − b|. ¢
Dado um número inteiro não-nulo b, podemos obter, a partir do zero, uma partição
da reta em segmentos de comprimento |b|. Como |b| = | − b|, esse processo nos dá a
mesma subdivisão da reta se consideramos b ou −b:
-