1
Inteiros e Indu»c~
ao Finita
Neste cap¶³tulo estudaremos uma estrutura alg¶ebrica que j¶a nos ¶e familiar: a estrutura alg¶ebrica do conjunto Z dos n¶umeros inteiros.
Por estrutura alg¶ebrica do conjunto Z entende-se o conjunto de propriedades
dos n¶
umeros inteiros que dizem respeito µas suas duas opera»c~oes habituais, a adi»c~ao
e a multiplica»c~ao, bem como µa ordem de¯nida no conjunto Z pela rela»c~ao <, a
chamada rela»c~ao de ordem \menor".
Na parte ¯nal do cap¶³tulo, estabeleceremos os assim chamados princ¶³pios de
indu»c~ao ¯nita e mostraremos algumas de suas aplica»c~oes.
1.1
Axiom¶
atica da estrutura de Z
Introduziremos as opera»c~oes de adi»c~ao e multiplica»c~ao em Z de forma axiom¶atica,
isto ¶e, a partir de um conjunto de axiomas ou postulados | propriedades b¶asicas,
admitidas a priori | que caracterizam essas opera»c~oes em Z. A partir desse
conjunto de propriedades axiom¶aticas, deduziremos algumas outras propriedades,
tamb¶em elementares e conhecidas por todos n¶os, por¶em \demonstr¶aveis", isto ¶e,
dedut¶³veis a partir dos axiomas b¶asicos.
Admitiremos axiomaticamente que existe um conjunto Z, cujos elementos
s~ao chamados n¶umeros inteiros, havendo em Z dois elementos destacados e distintos que s~ao, a saber, 0 (zero) e 1 (um).
Admitiremos tamb¶em que em Z, s~ao de¯nidas duas opera»c~oes, a adi»c~ao
(denotada por +) e a multiplica»c~ao (denotada por ¢). Dizendo que + e ¢ s~ao duas
opera»c~oes em Z, queremos dizer que + e ¢ s~ao duas fun»c~oes
+ : Z £ Z ! Z e ¢ : Z £ Z ! Z;
sendo que a primeira (+) associa cada par ordenado de inteiros (x; y) a um u¶nico
inteiro x + y, chamado soma de x e y, e a segunda (¢) associa cada par de inteiros
(x; y) a um u¶nico inteiro x ¢ y (denotado tamb¶em por xy, quando isto n~ao gerar
ambigÄuidade), chamado produto de x e y.
1
~o Finita
Inteiros e Induc
»a
2
Assumiremos que as opera»co~es adi»c~ao e multiplica»c~ao em Z tem as seguintes
propriedades:
Para cada x, cada y, e cada z, todos em Z, tem-se:
(A1) x + (y + z) = (x + y) + x (isto ¶e, a adi»c~ao em Z ¶e associativa);
(A2) x + y = y + x (a adi»c~ao em Z ¶e comutativa);
(A3) x + 0 = 0 + x = x (isto ¶e, 0 ¶e elemento neutro da adi»c~ao em Z);
(A4) Existe um elemento ¡x em Z, chamado oposto de x ou inverso aditivo de
x, ou ainda sim¶etrico de x relativamente µa opera»c~ao adi»c~ao, satisfazendo
x + (¡x) = (¡x) + x = 0.
(M1) x(yz) = (xy)z (a multiplica»c~ao em Z ¶e tamb¶em associativa);
(M2) xy = yx (a multiplica»c~ao em Z ¶e tamb¶em comutativa);
(M3) x ¢ 1 = 1 ¢ x = x (1 ¶e elemento neutro da multiplica»c~ao em Z);
(D) x(y + z) = xy + xz (a multiplica»c~ao ¶e distributiva em rela»c~ao µa adi»c~ao).
De¯ni»c~
ao 1.1 (Subtra»c~
ao em Z) Chama-se diferen»ca de dois inteiros x e y µa
soma x + (¡y). A subtra»c~ao em Z ¶e a opera»c~ao ¡: Z £ Z ! Z, que associa cada
par ordenado (x; y) µa diferen»ca x ¡ y.
Teorema 1.1 Para cada x, cada y, e cada z, todos em Z, valem as propriedades:
1. x + y = x ) y = 0 (ou seja, 0 ¶e o ¶unico elemento neutro da adi»c~ao em Z)
2. x + y = 0 ) y = ¡x (ou seja, o oposto de um inteiro x ¶e u¶nico);
3. x + y = x + z ) y = z ( lei do cancelamento da adi»c~ao);
4. ¡(¡x) = x;
5. ¡(x + y) = ¡x ¡ y (aten»c~ao!: ¡x ¡ y signi¯ca (¡x) ¡ y, ou seja, (¡x) +
(¡y));
6. x ¢ 0 = 0;
7. (¡x)y = ¡xy;
8. (¡x)(¡y) = xy;
9. (x ¡ y)z = xz ¡ yz.
~o Finita
Inteiros e Induc
»a
3
Demonstra»c~ao.
1. x + y = x ) (¡x) + (x + y) = (¡x) + x. Pelos axiomas (A1), (A3) e (A4),
temos conseqÄuentemente que
((¡x) + x) + y = 0 ) 0 + y = 0 ) y = 0
2. Se x + y = 0 ent~ao (¡x) + (x + y) = (¡x) + 0. Pelos axiomas (A1), (A3)
e (A4), temos conseqÄ
uentemente que
((¡x) + x) + y = ¡x ) 0 + y = ¡x ) y = ¡x
3. Se x + y = x + z, ent~ao (¡x) + (x + y) = (¡x) + (x + z). Pelo axioma
(A1), ((¡x) + x) + y = ((¡x) + x) + z ) 0 + y = 0 + z, e ent~ao, pelo
axioma (A3), y = z.
4. Pelo axioma (A4) ¡(¡x) + (¡x) = 0.
Logo, [¡(¡x)+(¡x)]+x = 0+x. Aplicando ent~ao os axiomas (A1) e (A3),
deduzimos: ¡(¡x) + [(¡x) + x] = x ) ¡(¡x) + 0 = x ) ¡(¡x) = x.
5. (Exerc¶³cio para o leitor. Sugest~ao: Calcule inicialmente a soma (x + y) +
[(¡x) + (¡y)], aplicando os axiomas da adi»c~ao.)
6. Seja x ¢ 0 = a. Ent~ao, pelos axiomas (A3) e (D), a = x ¢ 0 = x ¢ (0 + 0) =
x ¢ 0 + x ¢ 0 = a + a. Logo, a + a = a + 0, e ent~ao, pelo item 3 provado
acima, a = 0, ou seja x ¢ 0 = 0.
7. Por um lado, temos que [(¡x) + x]y = (¡x)y + xy. Por outro, temos que
[(¡x) + x]y = 0 ¢ y = 0. Logo, aplicando o resultado do item 2 demonstrado
acima, (¡x)y + xy = 0 ) ¡(xy) = (¡x)y.
8. (Exerc¶³cio para o leitor. Sugest~ao: Aplique o resultado do item anterior)
9. (Exerc¶³cio para o leitor.)
Observa»c~
ao 1.1 Os axiomas listados ainda n~ao s~ao su¯cientes para caracterizar
o conjunto Z de maneira u¶nica. Em outras palavras, existem outras estruturas
alg¶ebricas familiares que tamb¶em satisfazem µas propriedades acima.
O leitor certamente j¶a est¶a familiarizado com os conjuntos num¶ericos Q, dos
n¶umeros racionais, e R, dos n¶umeros reais. Sabe portanto, que em Q, bem como
em R, tamb¶em s~ao de¯nidas uma adi»c~ao e uma multiplica»c~ao, as quais, embora
tendo propriedades adicionais, satisfazem a todos os axiomas listados acima.
Isto indica claramente que esses axiomas s~ao satisfeitos por outras estruturas
alg¶ebricas familiares, tais como as de Q e R.
Existem tamb¶em estruturas alg¶ebricas \abstratas" satisfazendo os axiomas
(A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D).
4
~o Finita
Inteiros e Induc
»a
Consideremos, por exemplo, o conjunto Z = f0; 1g, no qual de¯niremos
uma adi»c~ao e uma multiplica»c~ao conforme as tabelas abaixo (aten»c~ao! Aqui, os
n¶umeros 0 e 1 n~ao s~ao aqueles do conjunto Z dos n¶umeros inteiros.)
+ 0 1
0 0 1
1 1 0
¢ 0
0 0
1 0
1
0
1
Assim, as opera»c~oes + e ¢, de¯nidas em Z conforme suas t¶abuas dadas
acima, satisfazem os axiomas (A1), (A2), (A3), (A4), (M1), (M2), (M3) e (D).
Veri¯que. Note que este \Z" tem apenas dois elementos.
1.1.1
Problemas complementares
..
1. °
^ Usando somente os axiomas (A1) a (D) das opera»c~oes em Z, deduza
que (¡1)(¡1) = 1. (N~ao utilize o resultado do item 8 do teorema 1.1) Use
o menor n¶umero de axiomas poss¶³vel para essa dedu»c~ao. Quais axiomas s~ao
utilizados nela?
..
2. °
^ Existe um elemento neutro para a opera»c~ao de subtra»c~ao em Z? Explique.
1.2
Ordem em Z
J¶a temos um conhecimento intuitivo de que os inteiros s~ao ordenados, no sentido
de que ¡1 ¶e menor que 0, que por sua vez ¶e menor que 1, que ¶e menor que 2,
e assim por diante. Nesta se»c~ao trataremos de caracterizar a rela»c~ao de ordem
\menor" (<) no conjunto Z de maneira formal.
De¯ni»c~
ao 1.2 (Rela»c~
ao num conjunto) Sendo A um conjunto n~ao vazio, dizemos que R ¶e uma rela»c~ao em A, se R ¶e um subconjunto do produto cartesiano
A £ A. (O produto cartesiano A £ B de dois conjuntos A e B ¶e o conjunto cujos
elementos s~ao todos os pares ordenados (a; b), com a 2 A e b 2 B.)
Por exemplo, R = f(1; 2); (1; 4); (2; 3)g ¶e uma rela»c~ao em A = f1; 2; 3; 4g.
Tamb¶em s~ao rela»co~es em A os conjuntos S = ¿ e T = A £ A.
Se S ¶e uma rela»c~ao em A, e se o par (a; b) faz parte dessa rela»c~ao, escrevemos
(a; b) 2 S ou aSb, e dizemos que a est¶a relacionado com b pela rela»c~ao S. Se
(x; y) 6
2 S, tamb¶em escrevemos x 6
Sy.
No exemplo acima, temos 1S2, 1S4 e 2S3 mas, por exemplo, 16
S3.
5
~o Finita
Inteiros e Induc
»a
1.2.1
Axiomas para a rela»c~
ao \menor" (<) em Z
Admitiremos que em Z est¶a de¯nida uma rela»c~ao <, chamada rela»c~ao menor. Se
(x; y) 2 <, escrevemos x < y (ou y > x) e dizemos que x ¶e menor que y (ou,
respectivamente, que y ¶e maior que x),
Admitiremos que a rela»c~ao < em Z satisfaz os seguintes axiomas: Para cada
x, cada y, e cada z, todos em Z,
(O1) Lei da tricotomia. Vale uma e somente uma das a¯rma»c~oes:
x < y;
x = y;
y<x
(O2) Se x < y e y < z ent~ao x < z (a rela»c~ao < em Z ¶e transitiva);
(O3) Se x < y ent~ao x + z < y + z (a rela»c~ao < em Z ¶e compat¶³vel com a
adi»c~ao);
(O4) Se x > 0 e y > 0 ent~ao xy > 0 (a rela»c~ao < em Z ¶e compat¶³vel com a
multiplica»c~ao).
Observa»c~
ao 1.2 Escrevemos a · b quando a < b ou a = b. Analogamente,
escrevemos a ¸ b se a > b ou a = b. Assim, por exemplo, 2 · 4, bem como
3 · 3.
Teorema 1.2 (Propriedades adicionais da rela»c~
ao <) Para cada x, cada y,
cada z e cada w, todos em Z, valem as seguintes propriedades:
1. x < y se e somente se x ¡ y < 0;
2. x < 0 se e somente se ¡x > 0;
3. (Lei do Cancelamento para a adi»c~ao) Se x + z < y + z ent~ao x < y;
4. Se x < y e z < w ent~ao x + z < y + w;
5. (Regras de Sinais)
(a) Se x < 0 e y > 0 ent~ao xy < 0;
(b) Se x < 0 e y < 0 ent~ao xy > 0;
6. Se x 6
= 0 ent~ao x2 > 0;
7. 1 > 0;
8. (a) Se x < y e z > 0 ent~ao xz < yz;
(b) Se x < y e z < 0 ent~ao xz > yz;
9. Se x > y > 0 e z > w > 0 ent~ao xz > yw > 0;
~o Finita
Inteiros e Induc
»a
6
10. (Leis do Cancelamento para a multiplica»c~ao)
(a) Se xz < yz e z > 0 ent~ao x < y;
(b) Se xz < yz e z < 0 ent~ao x > y.
Demonstra»c~ao.
1. Se x < y ent~ao, pelo axioma (O3), x + (¡y) < y + (¡y), e portanto
x ¡ y < 0.
2. (Exerc¶³cio para o leitor).
3. (Exerc¶³cio para o leitor).
4. Se x < y ent~ao, pelo item 1, x + z < y + z. Analogamente, z < w )
y + z < y + w. Logo, x + z < y + z e y + z < y + w e ent~ao, pelo axioma
(O2), x + z < y + w.
5. Provaremos a primeira das a¯rma»c~oes e deixaremos a segunda como exerc¶³cio. Se x < 0 e y > 0 ent~ao ¡x > 0 e y > 0. Pelo axioma (O4), temos
¡(xy) = (¡x)y > 0, e ent~ao, pelo item 2, xy < 0,
6. (Exerc¶³cio para o leitor).
7. Temos que 1 6
= 0 e que 12 = 1 ¢ 1 = 1. Da¶³, pelo item 6, 1 > 0.
8. Provaremos a primeira das a¯rma»c~oes e deixaremos a segunda como exerc¶³cio. Se x < y e z > 0, ent~ao x ¡ y < 0, pelo item 1. Aplicando a
propriedade (a) do item 5, x ¡ y < 0 e z > 0 ) (x ¡ y)z < 0, de onde
xz ¡ yz < 0, e ent~ao xz < yz.
9. (Exerc¶³cio para o leitor).
10. Provaremos o item (a) e deixaremos o item (b) como exerc¶³cio. Ambos os
itens s~ao conseqÄ
u^encia direta do item 8. Se xz < yz e z > 0 ent~ao necessariamente x < y pois, caso contr¶ario, teremos x > y ou x = y. Pelo item
8, sub-item (a), como z > 0, temos que xz > yz ou xz = yz, contrariando
nosso dado inicial de que xz < yz. Portanto xz < yz e z > 0 ) x < y.
Proposi»c~
ao 1.1 Se x e y s~ao inteiros, com x 6
= 0 e y 6
= 0, ent~ao xy 6
= 0.
Equivalentemente, xy = 0 ) x = 0 ou y = 0.
Demonstra»c~ao. Se x 6
=0 ey 6
= 0 ent~ao, pela lei da tricotomia (axioma (O1)),
temos x < 0 ou x > 0, bem como tamb¶em y < 0 ou y > 0. Da¶³, aplicando
o axioma (O4) ou o teorema 1.2, item 5, teremos xy > 0 ou xy < 0, portanto
xy 6
= 0.
~o Finita
Inteiros e Induc
»a
1.2.2
7
O conjunto N dos n¶
umeros naturais e o Princ¶³pio da
Boa Ordem
Alguns textos introdut¶orios de estruturas alg¶ebricas, bem como outros tantos de
introdu»c~ao µa teoria dos n¶
umeros apresentam uma teoria axiom¶atica dos n¶
umeros
naturais e ent~ao, a partir dos n¶umeros naturais e suas propriedades, uma constru»c~ao
dos n¶umeros inteiros. Um desses conjuntos de axiomas ¶e conhecido como Axiomas
de Peano, levando o sobrenome de Giuseppe Peano, que em 1889 formulou uma
abordagem axiom¶atica dos n¶umeros naturais.
Em nossa introdu»c~ao µas estruturas alg¶ebricas, optamos por partir axiomaticamente dos n¶umeros inteiros e ent~ao, a partir deles, de¯nir os n¶
umeros naturais.
Uma das vantagens dessa estrat¶egia ¶e a economia de tempo na elabora»c~ao de conceitos e resultados fundamentais, bem como o r¶apido atalho tomado em dire»c~ao a
resultados, sobre os inteiros, j¶a n~ao t~ao intuitivos, conforme veremos adiante.
De¯ni»c~
ao 1.3 (O conjunto N dos n¶
umeros naturais) Chamaremos de n¶ume
ros naturais aos elementos do conjunto
N = fx 2 Z j x ¸ 0g
Se x e y s~ao n¶
umeros naturais ent~ao, por resultados acima estabelecidos
(quais?), x + y e xy tamb¶em s~ao n¶umeros naturais. Na linguagem dos algebristas,
o conjunto N ¶e fechado nas opera»co~es de adi»c~ao e multiplica»c~ao de¯nidas em Z,
isto ¶e, somando-se ou multiplicando-se elementos de N, tem-se o resultado (soma
ou produto) sempre em N.
Tamb¶em s~ao utilizadas as nota»c~oes Z+ =N e Z¤+ =N¤ =fx 2 Z j x > 0g.
Os elementos de N¤ s~ao chamados inteiros positivos. Se n ¶e um inteiro e
n < 0, ent~ao n ¶e chamado um inteiro negativo. O conjunto dos inteiros negativos
ser¶a denotado por Z¤¡ .
Pela lei da tricotomia, temos que Z decomp~oe-se como reuni~ao de tr^es partes
disjuntas, a saber
Z = Z¤¡ [ f0g [ Z¤+
Enunciaremos agora o
Axioma da Boa Ordem em N, ou Princ¶³pio do Menor N¶
umero Natural. Cada subconjunto n~ao vazio do conjunto N possui um menor (ou primeiro)
elemento.
O axioma da boa ordem em N a¯rma que se A ¶e um subconjunto do conjunto
NeA6
= ¿ ent~ao existe um elemento n0 em A satisfazendo n0 · a para cada
inteiro a do conjunto A.
Observa»c~
ao 1.3 Observe que as propriedades elementares das opera»c~oes em Z,
bem como as propriedades da rela»c~ao <, axiomatizadas ou deduzidas at¶e o presente
~o Finita
Inteiros e Induc
»a
8
momento, excetuando-se o Axioma da Boa Ordem em Z+ , s~ao igualmente v¶alidas
para os n¶umeros racionais e para os n¶
umeros reais. Do ponto de vista axiom¶atico,
o axioma da boa ordem ¶e o primeiro dos axiomas que ¶e satisfeito pelos inteiros
n~ao negativos mas n~ao ¶e satisfeito pelos racionais n~ao negativos, visto que nem
todo conjunto de n¶umeros racionais n~ao negativos possui um primeiro elemento.
Admitamos, por um momento, familiaridade com o conjunto Q dos n¶umeros
racionais. O conjunto dos n¶umeros racionais positivos da forma 1=n, com n inteiro
positivo, n~ao possui um menor elemento. Se n > 0 ent~ao n + 1 > n (visto que
1
1 > 0). No ^ambito dos n¶umeros racionais, ¶e sabido que ent~ao 0 < n+1
< n1 , o
que demonstra ser imposs¶³vel encontrar um primeiro (o menor) racional da forma
1=n, com n inteiro positivo.
Observa»c~
ao 1.4 (Diferentes leituras de uma mesma nota»c~
ao) Quando escrevemos \se x 2 A ent~ao..." queremos dizer \se x ¶e elemento de A, ent~ao...",
mas na frase \para cada x 2 A, tem-se...", seremos for»cados a ler \para cada x
pertencente a A, tem-se...". De modo an¶alogo, as senten»cas \se x > 2 ent~ao..."
e \para cada x > 2, tem-se..." s~ao lidas de modos diferentes. Nas senten»cas do
primeiro tipo, os s¶³mbolos empregados ( 2, > etc.) tem um papel verbal ( \¶e elemento de", \¶e maior que"), enquanto que no segundo caso, o s¶³mbolo empregado
quali¯ca o objeto que o precede ( \x pertencente a", \x maior que").
Estabeleceremos agora as primeiras conseqÄu^encias do Princ¶³pio do Menor
N¶umero Natural.
Teorema 1.3
1. N~ao existe um inteiro n tal que 0 < n < 1;
2. Para cada inteiro m, n~ao existe um inteiro n tal que m < n < m + 1;
3. Se m e n s~ao inteiros com m < n ent~ao m + 1 · n. Reciprocamente, se
m + 1 · n ent~ao m < n.
Demonstra»c~ao.
1. Suponhamos que existe um inteiro n tal que 0 < n < 1. Tal n ¶e um n¶umero
natural, e portanto o conjunto A de n¶umeros naturais caracterizado por
A = fx 2 N j 0 < x < 1g
¶e um conjunto n~ao vazio (visto que n 2 A).
Pelo axioma da boa ordem, A tem um menor elemento n0 . Por¶em
0 < n0 < 1 ) 0 ¢ n0 < n0 ¢ n0 < 1 ¢ n0 ;
ou seja, 0 < n20 < n0 . Temos a¶³ uma contradi»c~ao, pois 0 < n20 < 1 ) n20 2 A,
por¶em n0 ¶e o menor elemento de A e n20 < n0 .
~o Finita
Inteiros e Induc
»a
9
2. Sejam m e n dois inteiros e suponhamos que m < n < m + 1. Ent~ao
m ¡ m < n ¡ m < (m + 1) ¡ m, ou seja, 0 < n ¡ m < 1, o que ¶e imposs¶³vel,
segundo o item 1 acima.
3. (Exerc¶³cio para o leitor).
De¯ni»c~
ao 1.4 Seja A um subconjunto n~ao vazio de Z.
1. Dizemos que A ¶e limitado inferiormente por um inteiro m se a ¸ m, para
cada a em A;
2. Dizemos que A ¶e limitado superiormente por um inteiro M se a · M , para
cada a em A.
Uma conseqÄu^encia imediata do princ¶³pio do menor n¶umero natural ¶e a seguinte proposi»c~ao:
Proposi»c~
ao 1.2 Seja A um subconjunto n~ao vazio de Z.
1. Se A ¶e limitado inferiormente por m 2 Z, ent~ao A possui um primeiro
(menor) elemento, isto ¶e, existe a0 em A tal que a ¸ a0 para cada a em A.
(Tal a0 ¶e chamado m¶³nimo de A).
2. Se A ¶e limitado superiormente por M 2 Z, ent~ao A possui um u¶ltimo
(maior) elemento, isto ¶e, existe b0 em A tal que a · b0 para cada a em A.
(Tal b0 ¶e chamado m¶aximo de A).
Demonstra»c~ao.
1. Considere o conjunto
A0 = fx 2 Z j x = a ¡ m; com a 2 Ag
Para cada a 2 A, temos a ¸ m, logo a ¡ m ¸ 0, o que implica que cada elemento
x de A0 ¶e um n¶
umero natural. Como A0 ½ N e A0 6
= ¿ (pois A 6
= ¿), pelo Axioma
0
da Boa Ordem, existe n0 2 A tal que x ¸ n0 para cada x 2 A0 .
Sendo n0 um elemento de A0 , temos que n0 = a0 ¡ m para algum inteiro
a0 2 A. Logo, para cada x 2 A0 , x ¸ a0 ¡ m. Isto signi¯ca que para cada a 2 A,
a ¡ m ¸ a0 ¡ m, ou seja, a ¸ a0 .
2. Considere o conjunto
A00 = fx 2 Z j x = ¡a; com a 2 Ag
Para cada a 2 A, temos a · M ou, equivalentemente, ¡a ¸ ¡M. Logo,
para cada x 2 A00 , temos x ¸ ¡M . Pelo item 1 provado acima, A00 tem um
primeiro elemento, ou seja, existe c0 2 A00 tal que x ¸ c0 para cada x 2 A00 . Pela
caracteriza»c~ao dos elementos de A00 , c0 = ¡b0 para algum b0 2 A. Da¶³, ¡a ¸ ¡b0
para cada a 2 A, ou seja, a · b0 para cada a 2 A.
~o Finita
Inteiros e Induc
»a
1.2.3
10
Problemas complementares
. . Para cada inteiro m, de¯ne-se o m¶odulo ou valor absoluto de m, como
1. °
sendo o inteiro
½
m
se m ¸ 0
jmj =
¡m se m < 0
Mostre (prove) que se a e b s~ao inteiros, ent~ao
..
(a) °
^
..
(b) °
^
..
(c) °
^
..
(d) °
j ¡ mj = jmj;
jmj ¸ 0; jmj = 0 , m = 0;
jmj ¢ jnj = jmnj;
jm+nj · jmj+jnj [Sugest~ao: mostre que jm+nj2 · (jmj+jnj)2 ];
. . jmj · n , ¡n · m · n.
(e) °
. . Demonstre que a e b s~ao inteiros com ab = 1 ent~ao a = b = §1.
2. °
[Sugest~ao: Pelas regras de sinais, temos que a e b s~ao simultaneamente
positivos ou negativos. Suponha primeiramente a > 0 e b > 0. Mostre que
ent~ao a ¢ (b ¡ 1) · 0, de onde b · 1. Sendo 0 < b · 1, tem-se ent~ao b = 1
e ent~ao a = b = 1. Trabalhe ent~ao no caso a < 0 e b < 0.]
..
3. °
^ Prove que se a e b s~ao inteiros com a > b > 0 ent~ao a2 > b2 .
. . Agora prove que se a e b s~ao inteiros positivos com a2 > b2 ent~ao
4. °
a > b. Prove tamb¶em que se n ¸ 3 ¶e um inteiro positivo e an > bn ent~ao
a > b. [Sugest~ao: use os \produtos not¶aveis" a2 ¡ b2 = (a ¡ b)(a + b) e
an ¡ bn = (a ¡ b)(an¡1 + an¡2 b + : : : + abn¡2 + bn¡1 ), para n ¸ 2.]
. . Mostre que se n ¶e um inteiro ent~ao n + 1 ¶e o menor inteiro maior que n
5. °
(Todo mundo sabe disto. Compete a voc^e, futuro matem¶atico, demonstr¶alo!).
..
6. °
^ Admita familiaridade com o conjunto R dos n¶umeros reais, bem como
das propriedades da adi»c~ao e multiplica»c~ao em R. Em R tamb¶em de¯nese uma rela»c~ao de ordem < satisfazendo os axiomas de ordem O1 a O4
descritos na p¶agina 5.
Sendo A um subconjunto n~ao vazio de R, dizemos que A ¶e bem-ordenado
ou que A satisfaz o axioma da boa ordem se todo subconjunto n~ao vazio de
A possui um menor elemento.
Quais dos seguintes conjuntos de n¶
umeros reais ¶e bem-ordenado? Em caso
positivo, demonstre sua a¯rma»c~ao. Em caso negativo, exiba um subconjunto
n~ao vazio sem um menor elemento.
(a) R+ = fx 2 R j x ¸ 0g
(b) Z
(c) P = fx j x = 2n; n 2 Ng
~o Finita
Inteiros e Induc
»a
1.3
11
Indu»c~
ao Finita
Os chamados princ¶³pios de indu»c~ao ¯nita nos prov^eem um m¶etodo para demonstrar
propriedades dos n¶umeros inteiros que tem um formato do tipo \Para cada inteiro
n, a partir de um certo inteiro n0 dado, vale a propriedade..."
Como veremos ao ¯nal da se»c~ao, ambos os princ¶³pios s~ao conseqÄu^encias da
proposi»c~ao 1.2, por conseguinte do Princ¶³pio do Menor Inteiro.
Teorema 1.4 (Primeiro Princ¶³pio de Indu»c~
ao Finita) Seja n0 um n¶umero
inteiro e suponhamos que a cada inteiro n, n ¸ n0 , est¶a associada uma a¯rma»c~ao
A(n), a qual possui, para cada n, um valor l¶ogico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condi»c~oes 1 e 2 abaixo sejam veri¯cadas:
1. A a¯rma»c~ao A(n) ¶e verdadeira para n = n0 ;
2. Para cada k ¸ n0 , se A(k) ¶e verdadeira, ent~ao (¶e poss¶³vel demonstrar que)
A(k + 1) ¶e tamb¶em verdadeira.
Ent~ao a a¯rma»c~ao A(n) ¶e verdadeira para cada n ¸ n0 .
Antes de passarmos µa demonstra»c~ao do Primeiro Princ¶³pio da Indu»c~ao Finita,
daremos exemplos de resultados (teoremas) que podem ser demonstrados mediante
sua aplica»c~ao.
Exemplo 1.1 (Teoreminha) Para cada inteiro n, n ¸ 0, o inteiro 9n ¡ 1 ¶e
divis¶³vel por 8.
Demonstra»c~ao. (habitualmente chamada \prova por indu»c~ao sobre n").
Aqui a a¯rma»c~ao A(n), que queremos provar ser verdadeira para cada inteiro
n ¸ 0, ¶e a seguinte:
A(n): \9n ¡ 1 ¶e divis¶³vel por 8".
A prova de que vale a propriedade A(n) para cada n ¸ 0, por indu»c~ao sobre
n, consiste em veri¯car a validade de A(n) em apenas duas inst^ancias, realizando
duas \veri¯ca»c~oes" (da¶³ o nome \indu»c~ao ¯nita"), a saber,
² veri¯camos a validade da a¯rma»c~ao A(n) para n = 0;
² considerando um inteiro k qualquer, k ¸ 0, supomos que a a¯rma»c~ao A(n)
j¶a esteja valendo para n = k (esta suposi»c~ao ¶e chamada hip¶otese de indu»c~ao)
e, a partir disto, deduzimos (demonstramos) que a¯rma»c~ao A(n) tamb¶em
vale para n = k + 1.
Se n = 0, A(n) = A(0) ¶e a a¯rma»c~ao \90 ¡ 1 ¶e divis¶³vel por 8", que ¶e
verdadeira.
~o Finita
Inteiros e Induc
»a
12
Seja ent~ao k um inteiro, k ¸ 0, e admitamos a hip¶otese de indu»c~ao, de que
A(k) ¶e verdadeira, ou seja, de que 9k ¡ 1 ¶e divis¶³vel por 8. Provaremos que ent~ao
9k+1 ¡ 1 tamb¶em ¶e divis¶³vel por 8.
Por hip¶otese de indu»c~ao, 9k ¡ 1 = 8a para algum inteiro a. Da¶³ 9k = 8a + 1.
Como conseqÄu^encia temos ent~ao
9k+1 ¡ 1 = 9k ¢ 9 ¡ 1 = (8a + 1) ¢ 9 ¡ 1 = 72a + 9 ¡ 1 = 72a + 8 = 8(9a + 1),
e assim, acabamos deduzindo que 9k+1 ¡ 1 = 8(9a + 1) ¶e um m¶ultiplo inteiro de
8, ou seja, tamb¶em ¶e divis¶³vel por 8.
Provamos portanto que a hip¶otese de indu»c~ao, isto ¶e, a validade da a¯rma»c~ao
A(k), implica na validade da a¯rma»c~ao A(k + 1).
Sendo assim, provamos, pelo Primeiro Princ¶³pio de Indu»c~ao Finita, que A(n)
¶e v¶alida para cada n ¸ 0, ou seja, que 9n ¡ 1 ¶e divis¶³vel por 8 para cada n ¸ 0.
Outro importante resultado da aritm¶etica dos inteiros, e que pode ser demonstrado por indu»c~ao ¯nita, ¶e o seguinte teorema.
Teorema 1.5 (Algoritmo da Divis~
ao Euclidiana em N) Para cada n¶umero
natural n, e cada inteiro positivo d, existem n¶umeros naturais q (quociente) e r
(resto) satisfazendo:
n = d ¢ q + r e 0 · r < d:
Al¶em disso, os naturais q e r, satisfazendo as condi»c~oes acima, s~ao u¶nicos.
Prova da exist^encia dos naturais q e r, por indu»c~ao sobre n.
Mostraremos que, ¯xado um inteiro positivo d, para cada n¶umero natural n,
existem q e r nas condi»c~oes enunciadas.
Se n = 0, basta tomar q = r = 0.
Seja k um n¶umero natural e suponhamos que existem q e r satisfazendo
k = dq + r e 0 · r < d:
Ent~ao k + 1 = dq + (r + 1).
Como 0 · r < d, temos r + 1 < d + 1, ou seja, r + 1 · d. Se r + 1 < d,
tomamos q 0 = q e r0 = r + 1 e teremos k + 1 = dq 0 + r0 , com 0 · r0 < d.
Se r + 1 = d, ent~ao k + 1 = dq + d = d(q + 1) = dq 00 + r00 , onde q 00 = q + 1
e r = 0.
00
Portanto, pelo Primeiro Princ¶³pio de Indu»c~ao Finita, para cada n 2 N ,
existem q e r satifazendo n = dq + r, com 0 · r < d.
Para a demonstra»c~ao da unicidade de q e r, veja problema 7, na se»c~ao 1.3.2.
13
~o Finita
Inteiros e Induc
»a
Observa»c~
ao 1.5 (Uma nota»c~
ao para o algoritmo da divis~
ao.) Se n e d s~ao
n¶umeros naturais, com d 6
= 0, e se q e r s~ao n¶umeros naturais como no teorema
1.5, denotamos simbolicamente:
n d
r q
Neste caso, nessa divis~ao euclidiana de n por d, n ¶e o dividendo, d ¶e o
divisor, q ¶e o quociente e r ¶e o resto.
Observa»c~
ao 1.6 O leitor poder¶a veri¯car facilmente, atrav¶es de alguns poucos
exemplos, que o teorema 1.5 n~ao ¶e v¶alido se d = 0.
Observa»c~
ao 1.7 No pr¶oximo cap¶³tulo enunciaremos e provaremos um teorema do
algoritmo da divis~ao na sua vers~ao mais geral para inteiros, n~ao necessariamente
naturais.
Uma segunda forma de prova por indu»c~ao ¯nita, por vezes utilizada, ¶e estabelecida pelo seguinte teorema:
Teorema 1.6 (Segundo Princ¶³pio de Indu»c~
ao Finita.) Seja n0 um n¶umero
inteiro e suponhamos que a cada inteiro n, n ¸ n0 , est¶a associada uma a¯rma»c~ao
A(n), a qual possui, para cada n, um valor l¶ogico V (quando verdadeira) ou F
(quando falsa). Suponhamos que as condi»c~oes 1 e 2 abaixo sejam veri¯cadas:
1. A a¯rma»c~ao A(n) ¶e verdadeira para n = n0 ;
2. Para cada inteiro k ¸ n0 , se A(n) ¶e verdadeira para n0 · n · k ent~ao
A(k + 1) ¶e tamb¶em verdadeira.
Ent~ao a a¯rma»c~ao A(n) ¶e verdadeira para cada n ¸ n0 .
Observa»c~
ao 1.8 O que difere o segundo princ¶³pio de indu»c~ao ¯nita do primeiro ¶e a forma como ¶e formulada a hip¶otese de indu»c~ao. No primeiro princ¶³pio,
supomos que a asser»c~ao A(n) ¶e verdadeira para n = k somente, enquanto que no
segundo, supomos A(n) v¶alida para cada n satisfazendo n0 · n · k. Em ambos
os princ¶³pios, devemos provar que a hip¶otese de indu»c~ao acarreta a validade de
A(n) para n = k + 1.
Antes de passarmos µa demonstra»c~ao dos dois princ¶³pios de indu»c~ao ¯nita, exibiremos um teorema cuja prova pode ser feita pelo segundo princ¶³pio.
Teorema 1.7 (Representa»c~
ao decimal de n¶
umeros naturais) Para cada inteiro n ¸ 1, existem n¶umeros naturais a0 ; : : : ; as , (s ¸ 0), com os \algarismos"
a0 ; : : : ; as , tomados no conjunto f0; 1; 2; : : : ; 9g, e as 6
= 0, tais que
n=
s
X
i=0
ai ¢ 10i = as 10s + ¢ ¢ ¢ + a0 100
14
~o Finita
Inteiros e Induc
»a
Observa»c~
ao 1.9 Ilustrando o teorema acima com um exemplo, quando escrevemos, por exemplo, 50 237, queremos dizer 5 ¢ 104 + 2 ¢ 102 + 3 ¢ 101 + 7 ¢ 100 .
Prova do teorema 1.7.
Se n = 1, podemos tomar n = a0 = 1.
Seja k ¸ 1 um inteiro e suponhamos que o resultado do teorema seja verdadeiro para cada inteiro n, com 1 · n · k. Mostraremos que isto acarreta a
validade da mesma propriedade para n = k + 1.
Com efeito, realizando a divis~ao euclidiana de k + 1 por 10,
k + 1 10
r
q
obtemos um quociente q 2 N e um resto r 2 N, satisfazendo k + 1 = 10q + r,
com 0 · r < 10, conforme o teorema 1.5.
Se q = 0, ent~ao k + 1 = r = a0 , com a0 2 f0; 1; 2; : : : ; 9g.
Se q > 0, ent~ao q · k, pois se q > k, ent~ao k+1 = 10q+r > 10k+r ¸ 10k,
e assim k + 1 > 10k e ent~ao 1 > 9k ¸ 9, o que ¶e imposs¶³vel.
Sendo ent~ao 1 · q · k, pela hip¶otese de indu»c~ao,
q = bt ¢ 10t + ¢ ¢ ¢ + b0 ¢ 100
para certos algarismos bt ; : : : ; b0 , todos em f0; 1; 2; : : : ; 9g.
Ent~ao,
k + 1 = 10q + r
= 10(bt ¢ 10t + ¢ ¢ ¢ + b0 ¢ 100 ) + r
= bt ¢ 10t+1 + ¢ ¢ ¢ + b0 ¢ 101 + r
com bt ; : : : ; b0 e r todos em f0; 1; 2; : : : ; 9g.
Logo, pelo segundo princ¶³pio de indu»c~ao ¯nita, a representa»c~ao decimal de
n ¶e poss¶³vel para cada inteiro n ¸ 1.
1.3.1
Demonstra»c~
ao dos Princ¶³pios de Indu»c~
ao Finita
Veremos agora que ambos os princ¶³pios de indu»c~ao ¯nita s~ao conseqÄu^encias do
Princ¶³pio do Menor Inteiro (teorema 1.2, item 1).
Prova do Primeiro Princ¶³pio da Indu»c~ao Finita.
Suponhamos que estejam estabelecidas as hip¶oteses do teorema 1.4 e que
as condi»c~oes 1 e 2 l¶a enumeradas estejam ocorrendo.
Suponhamos que, al¶em disso, contrariamente µa tese do teorema, exista um
inteiro s ¸ n0 tal que a a¯rma»c~ao A(s) ¶e falsa.
~o Finita
Inteiros e Induc
»a
15
Seja S = fn 2 Z j n ¸ n0 e A(n) ¶e falsag.
S ¶e n~ao vazio, pois s 2 S.
Sendo S ½ Z, e limitado inferiormente por n0 , pelo Princ¶³pio do Menor
Inteiro, proposi»c~ao 1.2, item 1, S possui um menor elemento s0 .
Como n0 · s0 e A(n0 ) ¶e verdadeira, temos n0 < s0 , e ent~ao n0 · s0 ¡ 1.
Seja k = s0 ¡ 1. Ent~ao A(k) ¶e verdadeira, pois k < s0 e s0 ¶e o menor inteiro
n com A(n) falsa.
Mas como k ¸ n0 e A(k) ¶e verdadeira temos ent~ao A(k + 1) verdadeira.
Por¶em k + 1 = s0 e A(s0 ) ¶e falsa.
Assim, temos uma contradi»c~ao decorrente do fato de existir um inteiro s ¸ n0
para o qual A(s) ¶e falsa.
Portanto A(n) ¶e verdadeira para cada inteiro n ¸ n0 .
Prova do Segundo Princ¶³pio da Indu»c~ao Finita.
Salvo ligeiras modi¯ca»c~oes, a prova do Segundo Princ¶³pio da Indu»c~ao Finita,
teorema 1.6, ¶e id^entica µa prova apresentada acima.
A u¶nica diferen»ca se d¶a nas u¶ltimas linhas da demonstra»c~ao.
Considere S e s0 tal como na demonstra»c~ao do primeiro princ¶³pio de indu»c~ao.
Suponha agora que est~ao satisfeitas as condi»c~oes 1 e 2 da hip¶otese do teorema
1.6.
Tal como na demonstra»c~ao acima, teremos n0 · s0 ¡ 1. Como s0 ¶e o
menor inteiro n com A(n) falsa, temos ent~ao A(n) verdadeira para cada n tal
que n0 · n · s0 ¡ 1. Tomando k = s0 ¡ 1, temos ent~ao A(n) verdadeira para
cada n satisfazendo n0 · n · k. Pelo item 2 da hip¶otese, isto acarreta A(k + 1)
verdadeira. Mas k + 1 = s0 e novamente temos uma contradi»c~ao.
1.3.2
Problemas Complementares
..
1. °
^ Mostre, por indu»c~ao sobre n, que, se n ¸ 1 ent~ao:
n(n+1)
;
2
n2 = n(n+1)(2n+1)
;
6
n3 = [ n(n+1)
]2 ;
2
(a) 1 + 2 + ¢ ¢ ¢ + n =
(b) 12 + 22 + ¢ ¢ ¢ +
(c) 13 + 23 + ¢ ¢ ¢ +
2. Mostre tamb¶em que:
..
(a) °
^ Para cada inteiro n ¸ 0, n2 + n ¶e par. [Um inteiro ¶e par se ¶e da
forma 2m para algum inteiro m].
..
(b) °
^ (aqui admita familiaridade com os n¶umeros reais) Para cada n¶umero real positivo a e cada inteiro n ¸ 0, tem-se (1 + a)n ¸ 1 + na.
16
~o Finita
Inteiros e Induc
»a
. . Para cada inteiro m, m3 ¡ m ¶e divis¶³vel por 3.
(c) °
. . 42n+1 + 3n+2 ¶e um m¶ultiplo de 13 (isto ¶e, ¶e da forma 13 ¢ a com a
(d) °
inteiro), para cada n ¸ 0;
. . Todo conjunto de n elementos possui 2n subconjuntos.
(e) °
. . Aponte o erro na seguinte \demonstra»c~ao" de que 1 = : : : = n para
3. °
cada inteiro n ¸ 1:
A a¯rma»c~ao ¶e verdadeira se n = 1.
Supondo que ela ¶e v¶alida para n = k, com k ¸ 1, temos 1 = : : : = k, e
portanto 1 + 1 = : : : = k + 1.
Por hip¶otese de indu»c~ao, 1 = 2 = : : : = k. Como tamb¶em 2 = : : : = k + 1,
por transitividade teremos 1 = 2 = : : : = k + 1.
Assim, pelo primeiro princ¶³pio de indu»c~ao ¯nita, 1 = : : : = n, para cada
inteiro n ¸ 1.
..
4. °
^ Para cada a 2 Z e cada n 2 N, de¯ne-se a pot^encia de base a e
expoente n (ou n-¶esima pot^encia de a) como sendo o inteiro denotado por
an e de¯nido pelas leis:
(i) Se n = 0, ent~ao an = a0 = 1;
(ii) Para cada k ¸ 0, ak+1 = ak ¢ a.
A partir das duas leis de¯nidas acima, prove, por indu»c~ao sobre n, que se m
e n s~ao n¶umeros naturais e a ¶e um inteiro, ent~ao
(a) am+n = am ¢ an [Sugest~ao: Assuma que m ¶e um n¶umero natural ¯xado
e fa»ca a prova por indu»c~ao sobre n];
(b) (am )n = amn ;
(c) Se a 6
= 1 ent~ao 1 + a + a2 + ¢ ¢ ¢ + an =
an+1 ¡1
a¡1
5. Sendo n¡ e¢ p n¶umeros naturais, com n ¸ p, de¯ne-se o n¶umero binomial
Cn;p = np ,
µ ¶
n
n!
=
p!(n ¡ p)!
p
sendo 0! = 1! = 1, 2! = 2 ¢ 1 = 2, 3! = 3 ¢ 2 ¢ 1 = 6, etc. De um modo
geral, se n ¸ 1, n! = n ¢ (n ¡ 1)!
. . Prove a rela»c~ao de Stifel: sendo n e p n¶umeros naturais, se n ¸
(a) °
p + 1,
µ ¶ µ
¶ µ
¶
n
n
n+1
+
=
p
p+1
p+1
. . Prove a f¶ormula chamada bin^omio de Newton: sendo a e b n¶umeros
(b) °
reais e n um n¶
umero natural, n ¸ 1,
¡n¢ n¡r r
Pn ¡n¢ n¡k k ¡n¢ n ¡n¢ n¡1
n
(a + b)
=
a
b
=
a
+
a
b
+
¢
¢
¢
+
a b +
k=0 ¡ k¢
0
1
r
¡ ¢
¢ ¢ ¢ + n1 abn¡1 + n0 bn
17
~o Finita
Inteiros e Induc
»a
. . Prove que, sendo n ¸ p ¸ 1, ¡n¢ ¶e o n¶umero de subconjuntos
(c) °
p
(\combina»c~oes"), com p elementos, de um conjunto contendo n elementos. [Sugest~ao: Fa»ca a demonstra»c~ao por indu»c~ao sobre n, usando
o primeiro princ¶³pio de indu»c~ao ¯nita e a rela»c~ao de Stifel.]
..
6. °
_ A seqÄu^encia de Fibonacci ¶e um exemplo de uma seqÄu^encia de inteiros
de¯nida indutivamente. Ela ¶e de¯nida como a0 ; a1 ; a2 ; : : :, sendo
a0 = 0; a1 = 1 e, an+1 = an + an¡1 para cada n ¸ 0
Assim, ela come»ca como 0; 1; 1; 2; 3; 5; 8; 13; : : :
(a) Prove por indu»c~ao sobre n que
p
p
[(1 + 5)=2]n ¡ [(1 ¡ 5)=2]n
p
an =
5
[Sugest~ao: Use o segundo
princ¶
³pio da indu»c~ao. Provavelmente lhe ser¶a
p
p
1+ 5 2
3+ 5
¶util saber que ( 2 ) = 2 ]
(b) (para experts em C¶alculo I) Mostre que lim ( an+1
)=Á=
an
n!1
p
1+ 5
.
2
(J¶a
ouviu falar deste n¶umero, a \raz~ao ¶aurea"?)
. . Mostre que os n¶umeros naturais q (quociente) e r (resto) no enunciado
7. °
do teorema do algoritmo da divis~ao em N (teorema 1.5, p¶agina 12), s~ao
u¶nicos. [Sugest~ao: mostre que sendo n e d n¶umeros naturais, com d 6
= 0, se
n = dq1 +r1 = dq2 +r2 para certos naturais q1 ; q2 ; r1 ; r2 , com 0 · r1 ; r2 < d,
ent~ao djq1 ¡ q2 j = jr1 ¡ r2 j < d e logo jq1 ¡ q2 j = 0.]
..
8. °
_ (Para experts) Mostre que os algarismos a0 ; : : : ; as utilizados na representa»c~ao decimal de um n¶umero natural n s~ao determinados de maneira
u¶nica. [Sugest~ao: Mostre que se a0 + a1 10 + : : : + an 10n = 0, sendo os
coe¯cientes a0 , a1 , : : :, an , todos tomados no conjunto de inteiros f¡9; ¡8;
: : : ; ¡1; 0; 1; 2; : : : ; 9g, ent~ao an 10n = ¡a0 ¡a1 10 ¡ : : : ¡an¡1 10n¡1 )
jan j10n · ja0 j + ja1 j10 + : : : + jan¡1 j10n¡1 · 9 + 9 ¢ 10 + : : : + 9 ¢ 10n¡1 =
10n ¡ 1 < 10n ) jan j10n < 10n ) an = 0. ConseqÄuentemente, se
a0 + a1 10 + : : : + an 10n = 0, e a0 , a1 , : : :, an , est~ao todos no conjunto de
d¶³gitos f¡9; ¡8; : : : ; ¡1; 0; 1; 2; : : : ; 9g ent~ao an = an¡1 = : : : = a0 = 0].
..
9. °
^ Considere a igualdade
2 + 4 + 6 + ¢ ¢ ¢ + 2n = n2 + n + 100
Mostre que tal igualdade ¶e falsa. Mostre por¶em que, sendo k um inteiro,
supondo-a verdadeira para n = k podemos demonstrar que tamb¶em ¶e verdadeira para n = k + 1.
..
10. °
^ Considere a a¯rma»c~ao
n2 ¡ n + 5 ¶e primo
~o Finita
Inteiros e Induc
»a
18
(Um inteiro p ¶e primo se p 6
= 0, p 6
= §1, e seus ¶unicos fatores inteiros s~ao
§1 e §p)
Mostre que essa a¯rma»c~ao ¶e verdadeira se n 2 f1; 2; 3; 4g, mas ¶e falsa se
n = 5.