Teoria dos Números - Livro de Edgard de Alencar - Cap 2

Prévia do material em texto

Livro de Edgard de Alencar Filho - CAP. 2
1 Indução Matemática
1.1 Elemento Mı́nimo de um Conjunto de Inteiros
Definição 2.1 Seja A um conjunto de inteiros. Chama-se elemento mı́nimo de A um
elemento a ∈ A tal que a ≤ x para todo x ∈ A.
Representa-se pela notação “mı́nA”, que se lê: “mı́nimo de A”. Portanto, simbolica-
mente:
mı́nA = a⇔ (a ∈ A e (∀x ∈ A)(a ≤ x)).
Teorema 2.1 Se a é elemento mı́nimo de A, então este elemento é único.
Demonstração: Com efeito, se existisse um outro elemento mı́nimo b de A, teŕıamos:
(i) a ≤ b, porque a = mı́nA
(ii) b ≤ a, porque b = mı́nA
Logo, pela propriedade anti-simétrica da relação de ordem natural “≤”em Z, temos
a = b.
O elemento mı́nimo de A, se existe, denomina-se também primeiro elemento de A ou
menor elemento de A.
Exemplo 2.1 O conjunto N = {1, 2, 3, ...} dos inteiros positivos tem o elemento
mı́nimo, que é 1 (mı́nN = 1), porque 1 ∈ N e 1 ≤ n para todo n ∈ N.
Exemplo 2.2 O conjunto A = {x ∈ Z|x > 12} tem o elemento mı́nimo, que é 13
(mı́nA = 13), porque 13 ∈ A e 13 ≤ x para todo x ∈ A.
Exemplo 2.3 O conjunto Z− = {0,−1,−2,−3, ...} dos inteiros não positivos não tem
o elemento mı́nimo, porque não existe a ∈ Z− tal que a ≤ x para todo x ∈ Z−.
Exemplo 2.4 O conjunto A = {x ∈ N|3 divide x2} tem o elemento mı́nimo 3 (mı́nA =
3), porque 3 ∈ A (3 divide 9) e 3 ≤ x para todo x ∈ A (1��∈A e 2��∈A).
1.2 Prinćıpio da Boa Ordenação
Todo conjkunto não vazio A de inteiros não negativos possui o elemento mı́nimo.
Em outros termos, todo subconjunto não vazio A do conjunto
Z+ = {0, 1, 2, 3, ...}
dos inteiros não negativos (∅ 6= A ⊂ Z+) possui o elemento mı́nimo, isto é, simbolica-
mente:
(∀A ⊂ Z+, A 6= ∅)⇒ ∃ mı́nA
Exemplo 2.5 O conjunto A = {1, 3, 5, 7, 11, ...} dos inteiros positivos ı́mpares é sub-
conjunto não vazio de Z+(∅ 6= A ⊂ Z+).
Logo, pelo “prinćıpio da boa ordenação”, A possui o elemento mı́nimo (mı́nA = 1).
1
Exemplo 2.6 O conjunto P = {2, 3, 5, 7, 11, ...} dos inteiros primos é um subconjunto
não vazio de Z+(∅ 6= P ⊂ Z+).
Logo, pelo “prinćıpio da boa ordenação”, P possui o elemento mı́nimo (mı́nP = 2).
Teorema 2.2 (de Archimedes) Se a e b são dois inteiros positivos quaisquer, então
existe um inteiro positivo n tal que na ≥ b.
Demonstração:
Suponhamos que a e b são dois inteiros positivos para os quais na < b para to inteiro
positivo n. Então, todos os elementos do conjunto:
S = {b− na|n ∈ N
são inteiros positivos e, pelo “Prinćıpio da boa ordenação”, S possui o elemento mı́nimo,
digamos mı́nS = b− ka.
E como b− (k + 1)a pertence a S, porque S contém todos os inteiros positivos desta
forma, temos:
b− (k + 1)a = (b− ka)− a < b− ka
isto é, b− ka não é elemento mı́nimo de S, o que é uma contradição. Logo, a propriedade
archimediana é verdadeira.
Assim, por exemplo:
(i) se a = 2 e b = 11, então n = 6, porque 6 · 2 > 11.
(ii) se a = 9 e b = 5, então n = 1, porque 1 · 9 > 5.
1.3 Prinćıpio de Indução Finita
Teorema 2.3 Seja S um subconjunto do conjunto N dos inteiros positivos (S ⊂ N)
que satisfaz as duas seguintes condições:
(i) 1 pertence a S (1 ∈ S);
(ii) para todo inteiro, positivo k, se k ∈ S, então k + 1 ∈ S.
Nestas condições, S é o conjunto N dos inteiros positivos: S = N.
Demonstração:
Suponhamos, por absurdo, que S não é o conjunto N dos inteiros positivos (S 6= N) e
seja X o conjunto de todos os inteiros positivos que não pertencem a S, isto é:
X = {x|x ∈ N e x��∈S} = N− S.
Então, X é o subconjunto não vazio de N(∅ 6= X ⊂ N) e, pelo Prinćıpio da boa
ordenação existe o elemento mı́nimo x0 de X(mı́nX = x0).
Pela condição (i), 1 ∈ S, de modo que x0 > 1 e, portanto, x0 − 1 é um inteiro
positivo que não pertence a X. Logo, x0 − 1 ∈ S e, pela condição (ii), segue-se que
(x0 − 1) + 1 = x0 ∈ S, o que é uma contadrição, pois, x0 ∈ X = N − S, isto é, x0��∈S.
Assim sendo, X = ∅ e S = N.
Consoante este Prinćıpio de indução finita, o único subconjunto de N que satisfaz às
condições (i) e (ii) é o próprio N.
1.4 Indução Matemática
Teorema 2.4 Seja P (n) uma proposição associada a cada inteiro positivo n e que
satisfaz as duas seguintes condições:
(i) P (1) é verdadeiro;
2
(ii) para todo inteiro positivo k se P (k) é verdadeira, então P (k + 1) tambám é
verdadeira.
Nestas condições a proposição P (n) é verdadeira para todo inteiro positivo n.
Demonstração:
Seja S o conjunto de todos inteiros positivos n para os quais a proposição P (n) é
verdadeira, isto é:
S = {n ∈ N|P (n) é verdadeira }
Pela condição (i), P (1) é verdadeira e, portanto 1 ∈ S. Pela condição (ii), para todo
inteiro positivo k, se k ∈ S, então k + 1 ∈ S. Logo, o conjunto S satisfaz as condições
(i) e (ii) do “Prinćıpio de indução finita”e, portanto, S = N, isto é, a proposição P (n) é
verdadeira para todo inteiro positivo n.
NOTA: O teorema 2.4 é geralmente denominado “Teorema da indução matemática”ou
“Prićıpio de indução matemática”, e a demonstração de uma proposição usando-se este
teorema chama-se “demonstração por indução matemática”ou “demonstração por indução
sobre n”.
Na “demonstração por indução matemática” de uma dada proposição P (n) é obri-
gatório verificar que as duas condições (i) e (ii) são ambas satisfeitas. A verificação
da condição (i) e geralmente muito fácil, mas a verificação da condição (ii) implica em
demonstrar o teorema auxiliar cuja hipótese é:
H : proposição P (k) é verdadeira , k ∈ N
denominada “hipótese de indução”, e cuja tese ou conclusão é;
T : proposição P (k + 1) é verdadeira.
1.5 Exemplos de Demonstração por Indução Matemática
Exemplo 2.7 Demonstrar a proposição:
P (n) : 1 + 3 + 5 + ... + (2n− 1) = n2, ∀n ∈ N
Demonstração:
(i) P (1) é verdadeira, visto que 1 = 12.
(ii) A hipótese de indução é que a proposição:
P (k) : 1 + 3 + 5 + ... + (2k − 1) = k2, ∀k ∈ N
é verdadeira.
Adicionando 2k + 1 em ambos os membros desta igualdade, obtemos:
1 + 3 + 5 + ... + (2k − 1) + (2k + 1) = k2 + (2k + 1) = (k + 1)2
isto significa que a proposição P (k + 1) é verdadeira. Logo, pelo “Teorema da indução
matemática”, a proposição P (n) é verdadeira para todo inteiro positivo n.
Exemplo 2.8 Demonstrar a proposição:
P (n) :
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ ... +
1
n(n + 1)
=
n
n + 1
,∀n ∈ N.
Demonstração:
(i) P (1) é verdadeira, visto que 1
1·2 =
1
1+1
.
3
(ii) A hipótese de indução é que a proposição:
P (k) :
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ ... +
1
k(k + 1)
=
k
k + 1
, k ∈ N
é verdadeira.
Adicionando 1
(k+1)(k+2)
em ambos os membros desta igualdade, obtemos:
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ ... +
1
k(k + 1)
+
1
(k + 1)(k + 2)
=
k
k + 1
+
1
(k + 1)(k + 2)
=
k2 + 2k + 1
(k + 1)(k + 2)
=
k + 1
k + 2
.
isto significa que a proposição P (k + 1) é verdadeira. Logo, pelo ”Teorema da indução
matemática”, a proposição P (n) é verdadeira para todo inteiro positivo n.
Exemplo 2.9 Demonstrar a proposição:
P (n) : 3|(22n − 1),∀n ∈ N
Demonstração:
(i) P (1) é verdadeira, visto que 3|(22 − 1).
(ii) A hipótese de indução é que a proposição:
P (k) : 3|(22k − 1), k ∈ N
é verdadeira. Portanto:
22k − 1 = 3q, com q ∈ Z
o que implica:
22(k+1) − 1 = 22 · 22k − 1
= 4 · 22k − 1
= 4 · 22k − 4 + 4− 1
= 4 · (22k − 1) + 3
= 4 · 3q + 3
= 3(4q + 1)
isto significa que a proposição P (k + 1) é verdadeira. Logo, pelo “Teorema da indução
matemática”, a proposição P (n) é verdadeira para todo inteiro positivo n.
Exemplo 2.10 Desmonstrar a proposição:
P (n) : 2n > n,∀n ∈ N
Demonstração:
(i) P (1) é verdadeira, visto que 21 = 2 > 1.
(ii) A hipótese de indução é que a proposição:
P (k) : 2k > k, k ∈ N
é verdadeira. Portanto:
2 · 2k > 2k ou 2k+1 > k + k ≥ k + 1
o que implica: 2k+1 > k + 1, isto é, a proposição P (k + 1) é verdadeira. Logo, pelo “Teo-
rema da indução matemática”, a proposição P (n) é verdadeira para todo inteiro positivon.
4
1.6 Outras Formas da Indução Matemática
Teorema 2.5 Seja r um inteiro positivo fixo e seja P (n) uma proposição associada a
cada inteiro n ≥ r e satisfaz às duas seguintes condições:
(i) P (r) é verdadeira.
(ii) para todo inteiro k ≥ r, se P (k) é verdadeiro, então P (k+1) também é verdadeira.
Nestas condições, P (n) é verdadeira para todo inteiro n ≥ r.
Demonstração:
Seja S o conjunto de todos inteiros positivos n para os quais a proposição P (r+n−1)
é verdadeira, isto é:
S = {n ∈ N|P (r + n− 1) é verdadeira }
Pela condição (i), P (r) = P (r + 1 − 1) é verdadeira, isto é, 1 ∈ S. E, pela condição
(ii), se P (r + k − 1) é verdadeira, então:
P ((r + k − 1) + 1) = P (r + (k + 1)− 1)
também é verdadeira, isto é, se k ∈ S, então k + 1 ∈ S. Logo, pelo “Teorema da indução
finita”, se S é o conjunto dos inteiros positivos: S = N, isto é, a proposição P (r + n− 1)
é verdadeira para todo n ∈ N, ou seja, o que é a mesma coisa, a proposição P (n) é ver-
dadeira para todo inteiro n ≥ r.
Exemplo 2.11 Demonstrar a proposição:
P (n) : 2n < n!, ∀n ≥ 4.
Demonstração:
(i) P (4) é verdadeira, visto que 24 = 16 < 4! = 24.
(ii) Suponhamos, agora, que é verdadeira a proposição:
p(k) : 2k < k!, k ≥ 4
Então, por ser 2 < k + 1 para k ≥ 4, temos:
2k+1 < k! · (k + 1) ou 2k+1 < (k + 1)!
isto é, a proposição p(k + 1) é verdadeira. Logo, pelo Teorema 2.5, a proposição P (n) é
verdadeira para todo inteiro positivo n ≥ 4.
Obeserve que a proposição P (n) é falsa para n = 1, 2, 3, pois, temos:
21 > 1!, 22 > 2!, 23 > 3!
Exemplo 2.12 Demonstrar a proposição:
P (n) : n2 > 2n + 1,∀n ≥ 3.
Demonstração:
(i) P (3) é verdadeira, visto que 32 = 9 > 2 · 3 + 1 = 7.
(ii) Suponhamos, agora, que é verdadeira a proposição:
P (k) : k2 > 2k + 1,∀k ≥ 3.
5
Então, temos:
k2 + (2k + 1) > (2k + 1) + (2k + 1)
(k + 1)2 > 2(k + 1) + 2k ≥ 2(k + 1) + 6
e, portanto:
(k + 1)2 > 2(k + 1) + 1
isto é, a proposição p(k + 1) é verdadeira. Logo, pelo Teorema 2.5, a proposição P (n) é
verdadeira para todo inteiro positivo n ≥ 3.
Obeserve que a proposição P (n) é falsa para n = 1 e n = 2, pois, temos:
12 < 2 · 1 + 1 e 22 < 2 · 2 + 1.
Teorema 2.6 Seja P (n) uma proposição associada a cada inteiro n e satisfaz às duas
seguintes condições:
(i) P (r) é verdadeira.
(ii) para todo inteiro k, se P (1), P (2), ..., P (k) são todas verdadeiras, então P (k + 1)
também é verdadeira.
Nestas condições, a proposição P (n) é verdadeira para todo inteiro n.
Demonstração:
Seja S o conjunto de todos inteiros positivos n para os quais a proposição P (n) é
verdadeira, isto é:
S = {n ∈ N|P (n) é verdadeira }
Suponhamos, por absurdo, que S 6= N e seja X o conjunto de todos os inteiros positivos
que não pertencem a S, isto é:
X = {x|x ∈ N e x��∈S} = N− S
Então, X é o subconjunto não vazio de N e, pelo ”Prinćıpio da boa ordenação”, existe o
elemento mı́nimo j de X (mı́nX = j).
Pela condição (i), 1 ∈ S, de modo que j > 1, e como j é o menor inteiro positivo que
não pertence a S, segue-se as proposições P (1), P (2), ..., P (j − 1) são todas verdadeiras
. Então, pela condição (ii), a proposição P (j) é verdadeira e j ∈ S, o que é uma con-
tradição, pois, j ∈ X, isto é, j��∈S. Assim sendo, S = N e a proposição P (n) é verdadeira
para todo inteiro positivo n.
Teorema 2.7 Seja r um inteiro positivo fixo e seja P (n) uma proposição associada a
cada inteiro n ≥ r e satisfaz às duas seguintes condições:
(i) P (r) é verdadeira.
(ii) para todo inteiro k ≥ r, se P (m) é verdadeiro para todo m tal que r ≤ m < k,
então P (k) é verdadeira.
Nestas condições, a proposição P (n) é verdadeira para todo inteiro n ≥ r.
Demonstração:
Seja S o conjunto de todos inteiros n ≥ r para os quais a proposição P (n) é falsa, isto
é:
S = {n ∈ N|n ≥ r e P (n) é falsa }.
Suponhamos, por absurdo, que S é não vazio (S 6= ∅). Então, pelo “Prinćıpio da boa
ordenação”existe o elemento mı́nimo j de S (mı́nS = j).
6
Pela condição (i), r��∈S, de modo que j > r, e por conseguinte P (m) é verdadeira para
todo inteiro m tal que r ≤ m < j. Assim sendo, pela condição (ii), P (j) é verdadeira
e j��∈S, o que é uma contradição, pois j ∈ S. Logo o conjunto S é vazio (S = ∅), e a
proposição P (n) é verdadeira para todo inteiro n ≥ r.
7
EXERCÍCIOS
1. Demonstrar por “indução matemática”:
(a) 12 + 22 + 32 + ... + n2 =
n
6
(n + 1)(2n + 1),∀n ∈ N;
(b) 13 + 23 + 33 + ... + n3 =
n2
4
(n + 1)2,∀n ∈ N;
(c) 12 + 32 + 52 + ... + (2n− 1)2 = n
3
(4n2 − 1),∀n ∈ N;
(d) 13 + 33 + 53 + ... + (2n− 1)3 = n2(2n2 − 1),∀n ∈ N;
(e) 1 · 2 + 2 · 3 + 3 · 4 + ... + n(n + 1) = n
3
(n + 1)(n + 2)∀n ∈ N;
(f) 1 +
1
4
+
1
9
+ ... +
1
n2
≤ 2− 1
n
;
(g) a + aq + aq2 + ... + aqn =
a(qn+1 − 1)
q − 1
, (q 6= 1)∀n ∈ N.
2. Demonstrar por “indução matemática”:
(a) 2n < 2n+1,∀n ∈ N;
(b) 2n > n2,∀n ≥ 5;
(c) 2n > n3,∀n ≥ 10;
(d) 4n > n4,∀n ≥ 5;
(e) n! > n2,∀n ≥ 4;
(f) n! > n3,∀n ≥ 6.
3. Demonstrar por “indução matemática”:
(a) 2|(3n − 1),∀n ∈ N;
(b) 6|(n3 − n),∀n ∈ N;
(c) 5|(3n − 3n),∀n ∈ N;
(d) 24|(52n − 1),∀n ∈ N;
(e) 7|(23n − 1),∀n ∈ N;
(f) 8|(32n + 7),∀n ∈ N.
4. Demonstrar que 10n+1− 9n+ 10 é um múltiplo de 81 para todo inteiro positicvo n.
5. Demonstrar que
n3
3
+
n5
5
+
7n
15
é um inteiro positivo para todo n ∈ N.
8
SOLUÇÃO DOS EXERCÍCIOS
1. a) Solução:
Seja P (n) = 12 + 22 + 32 + ... + n2 =
n
6
(n + 1)(2n + 1),∀n ∈ N.
P (1) é verdadeira pois,
1
6
(1 + 1)(2 · 1 + 1) = 6
6
= 1 = 12.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 12 + 22 + 32 + ...+k2 =
k
6
(k+ 1)(2k+ 1),∀k ∈ N: “Hipótese de Indução”.
Então P (k + 1) = 12 + 22 + 32 + ... + k2 + (k + 1)2 =
k + 1
6
(k + 2)(2k + 3),∀k ∈ N:
“Tese”.
De fato,
12 + 22 + 32 + ... + k2 + (k + 1)2 =
k
6
(k + 1)(2k + 1) + (k + 1)2
=
k(k + 1)(2k + 1) + 6(k + 1)2
6
=
(k + 1)[k(2k + 1) + 6(k + 1)]
6
=
(k + 1)(2k2 + 7k + 6)
6
=
(k + 1)(k + 2)(2k + 3)
6
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo inteiro positivo n.
b) Solução:
Seja P (n) = 13 + 23 + 33 + ... + n3 =
n2
4
(n + 1)2,∀n ∈ N.
P (1) é verdadeira pois,
12
4
(1 + 1)2 =
4
4
= 1 = 13.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 13 + 23 + 33 + ... + k3 =
k2
4
(k + 1)2,∀k ∈ N: “Hipótese de Indução”.
Então P (k + 1) = 13 + 23 + 33 + ... + k3 + (k + 1)3 =
(k + 1)2
4
(k + 2)2,∀k ∈ N:
“Tese”.
De fato,
13 + 23 + 33 + ... + k3 + (k + 1)3 =
k2
4
(k + 1)2 + (k + 1)3
=
(k2)(k + 1)2 + 4(k + 1)3
4
=
(k + 1)2(k2 + 4k + 4)
4
=
(k + 1)2(k + 2)2
4
9
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo inteiro positivo n.
c) Solução:
Seja 12 + 32 + 52 + ... + (2n− 1)2 = n
3
(4n2 − 1), ∀n ∈ N.
P (1) é verdadeira pois,
1
3
(4 · 12 − 1) = 3
3
= 1 = 12.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 12 +32 +52 + ...+(2k−1)2 = k
3
(4k2−1),∀k ∈ N: “Hipótese de Indução”.
Então P (k+1) = 12+32+52+...+(2k−1)2+(2k+1)2 = (k + 1)
3
(4(k+1)2−1),∀k ∈ N:
“Tese”.
“Antes de tudo, note que (4n2 − 1) = (2n + 1)(2n− 1).”
De fato,
12 + 32 + 52 + ... + (2k − 1)2 + (2k + 1)2 = (k)
3
(4k2 − 1) + (2k + 1)2
=
(k)
3
(2k + 1)(2k − 1) + (2k + 1)2
=
(k)(2k + 1)(2k − 1) + 3(2k + 1)2
3
=
(2k + 1)[k(2k − 1) + 3(2k + 1)]
3
=
(2k + 1)[2k2 − k + 6k + 3]
3
=
(2k + 1)[2k2 + 5k + 3]
3
=
(2k + 1)(k + 1)(2k + 3)
3
=
(k + 1)(4k2 + 8k + 4− 1)
3
=
(k + 1)[4(k + 1)2 − 1]
3
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo inteiro positivo n.
d) Solução:
Seja P (n) = 13 + 33 + 53 + ... + (2n− 1)3 = n2(2n2 − 1),∀n ∈ N.
P (1) é verdadeira pois, 12(2 · 12 − 1) = 1 · 1 = 1 = 13.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 13+33+53+ ...+(2k−1)3 = k2(2k2−1),∀k ∈ N: “Hipótese de Indução”.Então P (k+1) = 13+33+53+...+(2k−1)3+(2k+1)3 = (k+1)2(2(k+1)2−1),∀k ∈ N:
“Tese”.
10
De fato,
13 + 33 + 53 + ... + (2k − 1)3 + (2k + 1)3 = k2(2k2 − 1) + (2k + 1)3
= 2k4 − k2 + 8k3 + 12k2 + 6k + 1
= 2k4 + 8k3 + 11k2 + 6k + 1
= (k + 1)2(2n2 + 4n + 1)
= (k + 1)2[2(n + 1)2 − 1]
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo inteiro positivo n.
e) Solução:
Seja P (n) = 1 · 2 + 2 · 3 + 3 · 4 + ... + n(n + 1) = n
3
(n + 1)(n + 2)∀n ∈ N.
P (1) é verdadeira pois, 1 · 2 = 1·2·3
3
.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 1 · 2 + 2 · 3 + 3 · 4 + ...+ k(k + 1) = k
3
(k + 1)(k + 2)∀k ∈ N: “Hipótese de
Indução”.
Então P (k+1) = 1·2+2·3+3·4+...+k(k+1)+(k+1)(k+2) = (k + 1)(k + 2)(k + 3)
3
∀k ∈
N: “Tese”.
De fato,
1 · 2 + 2 · 3 + 3 · 4 + ... + k(k + 1) + (k + 1)(k + 2) = k
3
(k + 1)(k + 2) + (k + 1)(k + 2)
=
k(k + 1)(k + 2) + 3(k + 1)(k + 2)
3
=
(k + 1)(k + 2)(k + 3)
3
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo inteiro positivo n.
2. a) Solução:
Seja P (n) = 2n < 2n+1,∀n ∈ N.
P (1) é verdadeira pois, 21 = 2 < 4 = 2(1+1).
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 2k < 2k+1,∀k ∈ N: “Hipótese de Indução”.
Então P (k + 1) = 2(k+1) < 2k+2,∀k ∈ N: “Tese”.
Por hipótese temos:
2k < 2k+1, multiplicando por 2 em ambos os lados temos:
2 · 2k < 2 · 2k+1 ⇒ 2(k+1) < 2(k+2)
11
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
b) Solução:
Seja P (n) = 2n > n2,∀n ≥ 5.
P (5) é verdadeira pois, 25 = 32 > 25 = 52.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 2k > k2, ∀k ≥ 5: “Hipótese de Indução”.
Então P (k + 1) = 2(k+1) > (k + 1)2,∀k ≥ 5: “Tese”.
Para podermos provar essa proposição primeiro devemos provar que 2m > 2m +
1,∀m ≥ 5.
Seja P (m) = 2m > 2m + 1,∀m ≥ 5.
P (5) é verdadeira pois, 25 = 32 > 11 = 2 · 5 + 1.
Devemos mostrar que se P (k′) vale, então também vale P (k′ + 1), ou seja:
Se P (k′) = 2k
′
> 2k′ + 1,∀k′ ≥ 5: “Hipótese de Indução”.
Então P (k′ + 1) = 2(k
′+1) > 2(k′ + 1) + 1 = 2k′ + 3,∀k′ ≥ 5: “Tese”.
Por hipótese temos:
2k
′
> 2k + 1 e como 2k
′
> 2 para k′ > 1, então
2k
′
+ 2k
′
> 2k + 1 + 2⇒ 2 · 2k′ > 2k + 3⇒ 2(k+1) > 2k + 3
Com isso demonstrado podemos continuar com a questão inicial.
Ora, se por hipótese, 2k > k2, e pelo que acabamos de demonstrar, 2k > 2k + 1,
temos:
2k + 2k > k2 + 2k + 1⇒ 2 · 2k > (k + 1)2 ⇒ 2(k+1) > (k + 1)2
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo n ≥ 5 ∈ N.
c) Solução:
Seja P (n) = 2n > n3,∀n ≥ 10.
P (10) é verdadeira pois, 210 = 1024 > 1000 = 103.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 2k > k3, ∀k ≥ 10: “Hipótese de Indução”.
Então P (k + 1) = 2(k+1) > (k + 1)3,∀k ≥ 10: “Tese”.
Sabemos que (k + 1)3 = k3 + 3k2 + 3k + 1, como por hipótese 2k > k3 devemos
mostrar que 2k > 3k2 + 3k + 1,∀k ≥ 10.
P (10) é verdadeira pois, 210 = 1024 > 331 = 3 · 102 + 3 · 10 + 1.
Devemos mostrar que se P (m) vale, então também vale P (m + 1), ou seja:
Se P (m) = 2m > 3m2 + 3m + 1,∀m ≥ 10: “Hipótese de Indução”.
Então P (m + 1) = 2(m+1) > 3(m + 1)2 + 3(m + 1) + 1 = 3m2 + 9m + 7,∀m ≥ 10:
“Tese”.
12
Por hipótese temos 2m > 3m2 + 3m + 1 ⇒ 2m > 3m2, logo nos resta provar que
2m > 9m + 7.
P (10) é verdadeira pois, 210 = 1024 > 97 = 9 · 10 + 7.
Se P (k) = 2k > 9k + 7,∀k ≥ 10: “Hipótese de Indução”.
Então P (k + 1) = 2(k+1) > 9(k + 1) + 7 = 9k + 7 + 9,∀k ≥ 10: “Tese”.
Como por hipótese 2k > 9k + 7 e 2k > 9, para k ≥ 10, temos:
2k + 2k > 9k + 7 + 9⇔ 2(k+1) > 9k + 16.
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo n ≥ 10 ∈ N.
d) Solução:
Seja P (n) = 4n > n4,∀n ≥ 5.
P (5) é verdadeira pois, 45 = 1024 > 625 = 54.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = 4k > k4, ∀k ≥ 5: “Hipótese de Indução”.
Então P (k + 1) = 4(k+1) > (k + 1)4,∀k ≥ 5: “Tese”.
Mostramos no item b que 2k > k2,∀k ≥ 5, logo:
2k > k2 ⇔ (2k)2 > (k2)2
⇔ 22·k > k2·2
⇔ (22)k > k4
⇔ 4k > k4
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo n ≥ 5 ∈ N.
e) Solução:
Seja P (n) = n! > n2,∀n ≥ 4.
P (4) é verdadeira pois, 4! = 24 > 16 = 42.
Devemos mostrar que se P (m) vale, então também vale P (m + 1), ou seja:
Se P (m) = m! > m2,∀m ≥ 4: “Hipótese de Indução”.
Então P (m + 1) = (m + 1)! > (m + 1)2,∀m ≥ 4: “Tese”.
De fato,
(m + 1)! = m!(m + 1)
= m ·m! + m! para m ≥ 4
> m! + m! que por hipótese é
> m2 + m2
= m2 + m ·m para m ≥ 4
> m2 + 3m
= m2 + 2m + m para m ≥ 4
> m2 + 2m + 1
= (m + 1)2
13
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo n ≥ 4 ∈ N.
f) Solução:
Seja P (n) = n! > n3,∀n ≥ 6.
P (6) é verdadeira pois, 6! = 720 > 216 = 63.
Devemos mostrar que se P (k) vale, então também vale P (k + 1), ou seja:
Se P (k) = k! > k3,∀k ≥ 6: “Hipótese de Indução”.
Então P (k + 1) = (k + 1)! > (k + 1)3,∀k ≥ 6: “Tese”.
De fato,
(k + 1)! = k!(k + 1)
= k · k! + k! para m ≥ 6
> k! + k! que por hipótese é
> k3 + k3
= k3 + k · k2 para m ≥ 6
> k3 + 4k2
= k3 + 3k2 + k2
= k3 + 3k2 + k · k para m ≥ 6
> k3 + 3k2 + 4k
= k3 + 3k2 + 3k + k para m ≥ 6
> k+3k2 + 3k + 1
= (k + 1)3
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo n ≥ 6 ∈ N.
3. a) Solução:
Seja P (n) = 2|(3n − 1), ∀n ∈ N.
Devemos mostrar que 2 divide (3n − 1), mas mostrar isso é o mesmo que mostrar
que (3n − 1) = 2q, com q ∈ N.
P (1) é verdadeiro pois, 31 − 1 = 2.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja,
Se P (k) = (3k − 1) = 2q,∀k, q ∈ N, então P (k + 1) = (3(k+1) − 1) = 2q′,∀k, q′ ∈ N.
De fato,
3(k+1) − 1 = 3k · 31 − 1
= 3k · 31 − 1
= 2 · 3k + 3k − 1 usando a hipótese de indução
= 2 · 3k + 2q
= 2(3k + q)
= 2q′
14
Onde q e q’ são interios positivos.
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
b) Solução:
Seja P (n) = 6|(n3 − n), ∀n ∈ N.
Devemos mostrar que 6 divide (n3 − n), mas mostrar isso é o mesmo que mostrar
que (n3 − n) = 6q, com q ∈ N.
P (1) é verdadeiro pois, 13 − 1 = 0 e 0 divide 6.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
Se P (k) = (k3 − k) = 6q,∀k, q ∈ N, então P (k + 1) = [(k + 1)3 − (k + 1)] =
6q′′,∀k, q′′ ∈ N.
De fato,
[(k + 1)3 − (k + 1)] = k3 + 3k2 + 3k + 1− k − 1
= (k3 − k) + 3k(k + 1)
Por hipótese, (k3 − k) = 6q, e como k(k + 1) são dois inteiros consecutivos um dos
dois é par, por exemplo k = 2q′, onde q′ ∈ N, dessa forma podemos reescrever a
equação como:
(k3 − k) + 3k(k + 1) = 6q + 3 · 2q′(2q′ + 1)
= 6q + 6q′(2q′ + 1)
= 6[q + q′(2q′ + 1)]
= 6q′′
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
c) Solução:
Seja P (n) = 5|(8n − 3n),∀n ∈ N.
5|(8n − 3n)⇒ ∃q ∈ N; (8n − 3n) = 5q.
P (1) é verdadeiro pois, 81 − 31 = 5 = 5 · 1.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
Se P (k) = (8k−3k) = 5q,∀k, q ∈ N, então P (k+1) = (8k+1−3k+1) = 5q′,∀k, q′ ∈ N.
15
De fato,
8k+1 − 3k+1 = 8k · 81 − 3k · 31
= 8 · 8k − 3 · 3k
= 5 · 8k + 3 · 8k − 3 · 3k
= 5 · 8k + 3(8k − 3k)
= 5 · 8k + 3(5q)
= 5 · 8k + 5(3q)
= 5(8k + 3q)
= 5q′
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
d) Solução:
Seja P (n) = 24|(52n − 1), ∀n ∈ N.
24|(52n − 1)⇒ ∃q ∈ N; (52n − 1) = 24q.
P (1) é verdadeiro pois, 52·1 − 1 = 24 = 24 · 1.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
Se P (k) = (52k−1) = 24q,∀k, q ∈ N, então P (k+1) = (52(k+1)−1) = 24q′,∀k, q′ ∈ N.De fato,
52(k+1) − 1 = 52k+2 − 1
= 52k · 52 − 1)
= 25 · 52k − 1
= 25(52k + 1− 1)− 1
= 25(24q + 1)− 1
= 25 · 24q + 25− 1
= 25 · 24q + 24
= 24 · 25q + 24
= 24(25q + 1)
= 24q′
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
e) Solução:
Seja P (n) = 7|(23n − 1),∀n ∈ N.
7|(23n − 1)⇒ ∃q ∈ N; (23n − 1) = 7q.
P (1) é verdadeiro pois, 23·1 − 1 = 8− 1 = 7 = 7 · 1.
16
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
Se P (k) = (23k− 1) = 7q,∀k, q ∈ N, então P (k+ 1) = (23(k+1)− 1) = 7q′,∀k, q′ ∈ N.
De fato,
23(k+1) − 1 = 2(3k+3) − 1
= 23k · 23 − 1
= 8 · 23k − 1
= 7 · 23k + 23k − 1
= 7 · 23k + 7q
= 7(23k + q)
= 7q′
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
f) Solução:
Seja P (n) = 8|(32n + 7),∀n ∈ N.
8|(32n + 7)⇒ ∃q ∈ N; (32n + 7) = 8q.
P (1) é verdadeiro pois, (32·1 + 7) = 32 − 1 = 8 = 8 · 1.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeiro também
para (k + 1), ou seja:
Se P (k) = (32k + 7) = 8q,∀k, q ∈ N, então P (k+ 1) = (32(k+1) + 7) = 8q′,∀k, q′ ∈ N.
De fato,
32(k+1) + 7 = 32k+2 + 7
= 32k · 32 + 7
= 9 · 32k + 7
= 8 · 32k + 32k + 7
= 8 · 32k + 8q
= 8(32k + q)
= 8q′
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
4. Solução:
10n+1−9n−10 é um múltiplo de 81 se, e somente se, ∃q ∈ N; 10n+1−9n−10 = 81q.
P (1) é verdadeira pois, 101+1 − 9 · 1− 10 = 102 − 9− 10 = 100− 19 = 81 = 81 · 1.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
17
Se P (k) = 10k+1 − 9k − 10 = 81q com k e q interios positivos.
Então P (k + 1) = 10k+2 − 9(k + 1)− 10 = 81q4 com k e q4 interios positivos.
De fato,
10k+2 − 9(k + 1)− 10 = 10 · 10k+1 − 9(k + 1)− 10
= 9 · 10k+1 + 10k+1 − 9k − 9− 10
= 9 · 10k+1 − 9 + (10k+1 − 9k − 10)
= 9(10k+1 − 1) + 81q
Para continuar a desmonstração, mostremos que 10k+1 − 1 é múltiplo de 9.
10n+1 − 1 é um múltiplo de 9 se, e somente se, ∃q1 ∈ N; 10n+1 − 1 = 9q1.
P (1) é verdadeira pois, 101+1 − 1 = 102 − 1 = 100− 1 = 99 = 9 · 11.
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
Se P (k) = 10k+1 − 1 = 9q2 com k e q2 interios positivos.
Então P (k + 1) = 10k+2 − 1 = 9q3 com k e q3 interios positivos.
De fato,
10k+2 − 1 = 10 · 10k+1 − 1
= 9 · 10k+1 + 10k+1 − 1
= 9 · 10k+1 + 9q2)
= 9(10k+1 + q2)
= 9(q3)
Portanto:
9(10k+1 − 1) + 81q = 9(9q3) + 81q
= 81q3 + 81q
= 81(q3 + q)
= 81q4
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
5. Demonstrar que
n3
3
+
n5
5
+
7n
15
é um inteiro positivo para todo n ∈ N.
Solução:
Note que
n3
3
+
n5
5
+
7n
15
= 5n
3+3n5+7n
15
, portanto basta provar que o numerador é
múltiplo de 15, ou seja, demonstrar que 5n3 + 3n5 + 7n = 15q, com q ∈ N.
P (1) é verdadeira pois, 5 · 13 + 3 · 15 + 7 · 1 = 5 + 3 + 7 = 15 = 15 · 1.
18
Supondo ser verdadeira para um k qualquer, mostremos que é verdadeira também
para (k + 1), ou seja:
Se P (k) = 5k3 + 3k5 + 7k = 15q com k e q interios positivos.
Então P (k+1) = 5(k+1)3+3(k+1)5+7(k+1) = 15q1 com k e q1 interios positivos.
De fato,
P (k + 1) = 5(k + 1)3 + 3(k + 1)5 + 7(k + 1)
= 5(k3 + 3k2 + 3k + 1) + 3(k5 + 5k4 + 10k3 + 10k2 + 5k + 1) + 7k + 7
= 5k3 + 15k2 + 15k + 5 + 3k5 + 15k4 + 30k3 + 30k2 + 15k + 3 + 7k + 7
= (5k3 + 3k5 + 7k) + 15k4 + 30k3 + 45k2 + 30k + 15
= 15q + 15(k4 + 2k3 + 3k2 + 2k + 1)
= 15(q + k4 + 2k3 + 3k2 + 2k + 1)
= 15q1
Logo, pelo “Teorema da indução matemática”, a proposição P (n) é verdadeira para
todo ∀n ∈ N.
19