A maior rede de estudos do Brasil

Grátis
198 pág.
Um convite à matemática Daniel C Filho.pdf

Pré-visualização | Página 47 de 50

P (k + 1) e´ va´lido, ou seja, que
(1 + x)k+1 ≥ 1 + (k + 1)x.
Ora, por hipo´tese, x ≥ −1, donde (1 + x) ≥ 0. Portanto, desse fato e do fato que P (k) vale, temos
(1 + x)(1 + x)k ≥ (1 + x)(1 + kx)⇒
(1 + x)k+1 ≥ 1 + kx+ x+ kx2 = 1 + (1 + k)x+ kx2 ≥ 1 + (1 + k)x,
ja´ que kx2 ≥ 0 para qualquer x. C.Q.D.
EXEMPLO 3:
P (n) : Se n ≥ 3, enta˜o a soma dos aˆngulos internos de um polı´gono regular de n-lados e´ (n−2)180◦.
i) (Atenc¸a˜o: nesse caso n0 = 3)
A propriedade para n = 3 diz respeito a um triaˆngulo, que sabemos da Geometria Elementar, ter a
soma dos aˆngulos internos igual a (3− 2)180◦ = 180◦. Logo, P (3) e´ va´lida.
ii) Suponha que P (k) vale para todo k ≥ 3, isto e´, que
“A soma dos aˆngulos internos de um polı´gono regular de k-lados e´ (k − 2)180◦”(hipo´tese de
induc¸a˜o).
Usando esse fato, vamos mostrar que “A soma dos aˆngulos internos de um polı´gono regular de
(k+1)-lados e´ [(k + 1)− 2]180◦.”
Com efeito, consideremos um polı´gono regular R de k+1 lados. Escolhendo dois ve´rtices apropria-
dos, esse polı´gono pode ser decomposto em um triaˆngulo T e noutro polı´gono S de k lados. Ora, a soma
dos aˆngulos internos de T vale 180◦ e, como pela hipo´tese de induc¸a˜o, a soma dos aˆngulos internos de S
vale (k−2)180◦, tem-se a soma dos aˆngulos internos deR valendo (k−2)180◦+180◦ = [(k+1)−2]180◦.
C.Q.D.
A Induc¸a˜o se tambe´m se presta com bastante efica´cia para fazer algumas definic¸o˜es que usam
recorreˆncia. Chamamos definic¸a˜o recursiva ou definic¸a˜o indutiva a esse tipo de definic¸a˜o.
Por exemplo:
DEFINIC¸A˜O 1: Se a ∈ R, a 6= 0 e n ∈ N, definimos
a0 = 1 e an = a.an−1.
174
15.1. Princı´pio de Induc¸a˜o: Vale para um, se valer para k implicar que vale para k + 1, enta˜o vale
sempre! (O raciocı´nio indutivo)
DEFINIC¸A˜O 2: Se n ∈ N, definimos
0! = 1 e n! = n(n− 1)!
E´ importante observar que nem todos os resultados que se referem a nu´meros naturais podem ou
devem ser provados por Induc¸a˜o. Esse exemplo e´ um destes: A soma de um nu´mero ı´mpar com um
nu´mero par, ambos naturais, e´ um nu´mero ı´mpar.
Tambe´m cabe-nos alertar para usar o Princı´pio da Induc¸a˜o com prudeˆncia. Seria um desperdı´cio de
esforc¸o utiliza´-lo para provar, por exemplo, que um nu´mero da forma 8n+ 1 e´ ı´mpar!
EXERCI´CIOS:
1. Seguem abaixo alguns exercı´cios cujas resoluc¸o˜es envolvem a utilizac¸a˜o do Princı´pio de Induc¸a˜o.
Antes de comec¸ar a aplicar o Princı´pio de Induc¸a˜o, que tal testa´-los com alguns exemplos?
(a) Prove o caso geral do corola´rio do Exercı´cio 9 (c) da Sec¸a˜o 4.1.
(b) Prove: O nu´mero 32n+1 e´ divisı´vel por 7, ∀n ∈ N.
(c) Prove as desigualdades a seguir. Uma de cada vez
13 + 23 + . . .+ (n− 1)3 < n
4
4
< 13 + 23 + . . .+ n3.
(d) Prove as fo´rmulas das somas dos n primeiros quadrados e dos n primeiros cubos:
12 + 22 + . . .+ n2 =
n(n+ 1)(2n+ 1)
6
13 + 23 + . . .+ n3 = (1 + 2 + . . .+ n)2.
(e) Voltando aos nu´meros poligonais dos pitago´ricos, mostre a expressa˜o da soma dos primeiros
nu´meros pentagonais:
1 + 4 + 7 + . . .+ (3n− 2) = n(3n− 1)
2
.
Fac¸a o mesmo para os nu´meros hexagonais
1 + 5 + 9 + . . .+ (4n− 3) = 2n2 − n.
(f) Demonstre a identidade usada no Exercı´cio 3 da Subsec¸a˜o 7.3.8
1 + 2 + 4 + . . .+ 2n−1 = 2n − 1, n ≥ 1.
(g) Considere n retas no plano que se intersectam de forma que
i. duas delas na˜o sejam paralelas;
ii. duas delas sempre se intersectam;
iii. treˆs delas na˜o podem se intersectar no mesmo ponto.
Dessa forma, mostre que essas retas se intersectam em
n2 − n
2
pontos.
(h) Prove a observac¸a˜o da Subsec¸a˜o 2.2.1, que uma tabela verdade de uma proposic¸a˜o composta
P (R1, R2, ..., Rk) possui 2k linhas.
175
Capı´tulo 15. O me´todo indutivo
2. Suponha que P (n) seja a proposic¸a˜o (falsa)
1 + 2 + 3 + . . .+ (n− 1) + n = 1
8
(2n+ 1)2
(a) Mostre que se P (k) for va´lido para algum k, enta˜o P (k + 1) e´ va´lido.
(b) Ora, isso garante uma demonstrac¸a˜o para a identidade acima? O que esta´ havendo?
3. Suponha que tenha sido provado o seguinte resultado
“O produto de dois nu´meros terminados em 6 tambe´m termina em 6”.
Usando esse resultado e o Princı´pio de Induc¸a˜o, mostre que se o nu´mero a termina em 6, enta˜o an,
para todo n ∈ N, tambe´m termina em 6.
4. Um algoritmo para se encontrar valores aproximados de pi e´ dado pelas sequ¨eˆncias abaixo
xn−1 =
1
2
[√
xn +
1√
xn
]
yn+1 =
yn
√
xn +
1√
xn
yn + 1
e
pin+1 =
xn + 1
yn + 1
pin,
onde as condic¸o˜es iniciais sa˜o dadas por
x0 =
1√
2
, y0 = 0 e pi0 = 2.
Esse algoritmo converge muito rapidamente. Com 4 passos voceˆ pode verificar que
pi4 = 3, 14159265358976
uma aproximac¸a˜o com 14 casas decimais corretas! Que tal verificar a u´ltima igualdade?
[Bongiovanni, 1991].
5. INTERESSANTE PROVA DE QUE EXISTEM INFINITOS PRIMOS.
Euclides, ja´ nos Elementos, deu uma demonstrac¸a˜o de que existem infinitos primos. Agora, vamos
a partir de uma identidade provada por induc¸a˜o, demonstrar que existem infinitos nu´meros primos.
Ao final da demonstrac¸a˜o voceˆ podera´ escolher qual delas podera´ se tornar a sua preferida. (Em
[Ribenboim, 2001], os interessados podera˜o encontrar 8 demonstrac¸o˜es diferentes de que existem
infinitos primos.)
Siga os passos:
i) Prove, usando Induc¸a˜o, que os nu´meros de Fermat Fn = 22
n
+1 gozam da seguinte propriedade
(*) F0F1F2 . . . Fn−1 + 2 = Fn+1.
176
15.2. Raciocı´nio indutivo, generalizac¸o˜es
ii) Mostre que quaisquer dois nu´meros distintos de Fermat Fm e Fn, m > n sa˜o sempre primos
entre si.
Dica: Da identidade (*), se existir algum nu´mero diferente de 1 que divida dois nu´meros distintos
de Fermat Fm e Fn, enta˜o esse nu´mero deve ser 2. Mas isso na˜o pode ocorrer.
iii) Ora, nas decomposic¸o˜es de dois nu´meros distintos primos entre si, aparecera˜o nu´meros primos
distintos (Por queˆ?). Como o conjunto {Fm; m ∈ N} e´ infinito (deˆ um argumento plausı´vel para
este fato) conclua, pela parte (ii) acima, que existem infinitos primos.
15.2 Raciocı´nio indutivo, generalizac¸o˜es
Nos va´rios exemplos e exercı´cios que demos na sec¸a˜o anterior, apareceram va´rias expresso˜es para
serem provadas usando-se o Princı´pio da Induc¸a˜o Finita. Ora, e´ natural que surja a pergunta: “Como se
encontrou aquelas expresso˜es?”. Na verdade, chegar a`quelas expresso˜es envolvendo nu´meros naturais,
decorre do que chamamos raciocı´nio indutivo, que funciona assim: vemos que um resultado vale para
n = 1, verificamos se continua va´lido para n = 2, n = 3 e, ate´ um nu´mero natural n que nos deˆ a
sensac¸a˜o de certeza que o resultado vale para todos os nu´meros naturais 3. O processo divide-se em duas
etapas: a descoberta do resultado e sua justificativa, que e´ uma demonstrac¸a˜o.
Este e´ o raciocı´nio indutivo que, para que seja aplicado eficazmente, depende muito da experieˆncia
e da observac¸a˜o. Apo´s a formalizac¸a˜o do resultado, resta apenas prova´-lo ou, caso na˜o seja possı´vel,
tentar encontrar um contra-exemplo para ele. Como ja´ vimos ao longo do texto, deve-se ter cuidado para
na˜o ser tentado a generalizar resultados que valem apenas para certos casos particulares.
Os exercı´cios abaixo lhe ajudara˜o a treinar seu raciocı´nio indutivo.
EXERCI´CIOS:
1. Das figuras do Exercı´cio 2 do Capı´tulo 14, deduza as seguintes fo´rmulas para a soma dos n
primeiros nu´meros inteiros positivos, e para a soma dos n primeiros nu´meros ı´mpares positivos:
1 + 2 + 3 + . . .+ (n− 1) + n = n(n+ 1)
2
e 1 + 3 + 5 + . . .+ (2n− 1) = n2
Demonstre essas fo´rmulas.
2. Encontre uma lei de formac¸a˜o para as identidades abaixo e as prove
(a) 1− 1
2
=
1
2
,
(
1− 1
2
)(
1− 1
3
)
=
1
3
,
(
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
=
1
4
, . . . .
3Esta e´ a maneira usual de pensar sobre problemas desse tipo, infelizmente, na˜o