MA12 Unidade 3 O Princípio de Indução Matemática

Prévia do material em texto

3
1
O Princípio de Indução
Matemática
Sumário
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2
3.2 O Poder do Método de Indução . . . . . . . . . . . 2
3.3 Exercícios Recomendados . . . . . . . . . . . . . . . 12
3.4 Exercícios Suplementares . . . . . . . . . . . . . . . 13
3.5 Textos Complementares . . . . . . . . . . . . . . . . 14
Unidade 3
Introdução
3.1 Introdução
Nesta unidade e na próxima, mostraremos como utilizar o Axioma de Indução
para definir com rigor objetos matemáticos e também como utilizá-lo como
poderoso instrumento para demonstrar os mais variados resultados envolvendo
números naturais. Algumas das noções introduzidas nesta e na próxima unidade
serão retomadas de modo mais sistemático nas Unidades 5 a 8.
3.2 O Poder do Método de Indução
Comecemos com a pergunta:
O que significam expressões do tipo 1 + 2 + · · ·+ n e 1 · 2 · · · · n?
Note que as operações de adição e de multiplicação nos números naturais (ou em
qualquer sistema numérico) são binárias, isto é, elas relacionam dois elementos
de cada vez. Apesar disso, temos uma ideia bastante intuitiva do significado
das expressões acima, até mesmo no que diz respeito aos pontinhos que nelas
aparecem. Existe, contudo, um modo de tornar mais rigorosas definições desse
tipo por meio do Princípio de Indução Matemática, como veremos mais adiante.
Antes, porém, recordemos este princípio que demonstramos na Unidade 1.
Princípio de Indução Matemática Se P (n) é uma propriedade relativa ao
número natural n, tal que
i) P (1) é válida;
ii) Para todo n ∈ N, a validez de P (n) implica a validez de P (n+ 1).
Então P (n) é válida qualquer que seja o número natural n.
+ Para Saber Mais - Comentário - Clique para ler
+ Para Saber Mais - Indução Empírica vs Indução Matemática - Cli-
que para ler
2
Unidade 3
O Princípio de Indução Matemática
Para definir uma expressão En, para todo número natural n, basta definirmos
E1 e mostrar, para todo n ∈ N, como obter sem ambiguidade En+1 a partir de
En.
Nesse caso, dizemos que En foi definido por recorrência.
Vejamos como intervém o Princípio de Indução Matemática para justificar
este tipo de definição. Seja X o subconjunto de N, determinado pela condição:
n ∈ X ⇐⇒ En está definido.
Pela caracterização do conjunto X, temos que 1 ∈ X e, para todo n ∈ N,
n ∈ X ⇒ n+ 1 ∈ X. Portanto, X = N.
Definições por recorrência podem ser utilizadas para dar um significado a
expressões como no início da unidade.
Exemplo 1
Definimos S1 = 1. Em seguida, supondo Sn definido, pomos
Sn+1 = Sn + (n+ 1).
Damos assim, um sentido matemático preciso à expressão:
Sn = 1 + 2 + · · ·+ n.
Por outro lado, definindo 1! = 1 e pondo (n+1)! = n!(n+1), supondo que
n! esteja definido, damos também, neste caso, um sentido matemático para a
expressão:
n! = 1 · 2 · · ·n.
Para generalizar os exemplos acima, vamos introduzir a noção de sequência.
Teremos oportunidade de comprovar, ao longo do curso, o quanto é central este
conceito.
Definição 1Uma sequência de elementos de um conjunto A é uma função x : N→ A.
3
Unidade 3
O Poder do Método de Indução
Tendo em vista que uma função conhecida quando se sabe qual é a ima-
gem de todo elemento de seu domínio, uma sequência x : N → A pode ser
representada como
x(1), x(2), . . . , x(n), . . . ,
ou ainda, denotando x(n) por xn, podemos representá-la concisamente por
(xn).
Por motivo de economia, quando dissermos que um conjunto A possui uma
adição ou uma multiplicação satisfazendo às leis básicas da aritmética, esta-
remos supondo que em A estão definidas duas operações com propriedades
semelhantes às correspondentes operações nos naturais.
Seja agora (xn) uma sequência de elementos de um conjunto A que possui
duas operações, de adição e de multiplicação, satisfazendo às leis básicas da
aritmética.
Definição 2 Definem-se Sn e Pn em A, como se segue: S1 = P1 = x1 e
Sn+1 = Sn + xn+1 e Pn+1 = Pn · xn+1.
Isto dá sentido às seguintes expressões:
Sn = x1 + x2 + · · ·+ xn e Pn = x1 · x2 · · ·xn.
Somas e produtos, como acima, serão também escritos com as notações de
somatórios e produtórios:
Sn =
n∑
i=1
xi e Pn =
n∏
i=1
xi,
que se leem como �somatório quando i varia de 1 até n de xi� e �produto
quando i varia de 1 até n de xi�, respectivamente.
Note que a partir de uma sequência dada (xn), pudemos definir de modo
natural duas outras sequências, a saber: (Sn) e (Pn).
Dada uma sequência constante, x(n) = a, para todo n ∈ N, onde a ∈ A,
os termos da sequência Pn a ela associada são por definição as potências de a.
Pela sua importância, destacamos essa definição a seguir.
4
Unidade 3
O Princípio de Indução Matemática
Definição 3Seja a um elemento de um conjunto A munido de uma multiplicação sujeita
às leis básicas da aritmética. As potências an de a, com n ∈ N, são definidas
por recorrência como segue: a1 = a e an+1 = an · a.
Quando a 6= 0, convenciona-se definir a0 = 1. Isto será especialmente con-
veniente quando estendermos as potências para expoentes não necessariamente
números naturais. Isto se tornará bem mais claro na Unidade 13 de MA11.
Exemplo 2
Neste exemplo, queremos determinar uma fórmula para a soma dos n pri-
meiros números naturais: Sn = 1 + 2 + · · ·+ n.
Conta-se a seguinte história sobre o matemático alemão Carl Friedrich Gauss
(1777-1855), considerado um dos maiores gênios da matemática de todos os
tempos, quando ainda garoto. Na escola, o professor, para aquietar a turma de
Gauss, mandou os alunos calcularem a soma de todos os números naturais de
1 a 100. Qual não foi a sua surpresa quando, instantes depois, o menino deu
a resposta: 5050. Indagado sobre como tinha descoberto tão rapidamente o
resultado, Gauss, então, descreveu o método a seguir.
Sendo
Sn = 1 + 2 + · · ·+ n,
o objetivo é encontrar uma fórmula fechada
1
para Sn.
Somando a igualdade acima, membro a membro, com ela mesma, porém
com as parcelas do segundo membro em ordem invertida, temos que
Sn = 1 + 2 + · · · + n
Sn = n + (n− 1) + · · · + 1
2Sn = (n+ 1) + (n+ 1) + · · · + (n+ 1)
Daí segue-se que 2Sn = n(n+ 1) e, portanto,
Sn =
n(n+ 1)
2
.
1
Uma fórmula fechada para Sn, a grosso modo, é uma função de n que permite calcular
diretamente os valores de Sn fazendo um pequeno número de cálculos.
5
Unidade 3
O Poder do Método de Indução
Vamos ser críticos com relação à prova acima. Para a maioria das pessoas,
essa prova parece impecável, mas se alguém nos perguntasse o que está escon-
dido atrás dos pontinhos, talvez nos sentíssemos embaraçados. Também, como
ter absoluta certeza de que nada acontece fora do nosso controle, exatamente
na imensa região coberta pelos pontinhos?
Para não pairar nenhuma dúvida sobre o nosso resultado, vamos provar a
fórmula utilizando o Princípio de Indução Matemática.
Considere a sentença sobre os naturais:
P (n) : 1 + 2 + · · ·+ n = n(n+ 1)
2
. (3.1)
Note que
P (1) : 1 =
1(1 + 1)
2
é verdadeira.
Observe também que
P (n+ 1): 1 + 2 + · · ·+ n+ (n+ 1) = (n+ 1)(n+ 2)
2
.
Agora, suponhamos que para algum n ∈ N, tenhamos P (n) verdadeira, isto
é, a fórmula (1.1) é válida para tal valor de n. Somando n+1 a ambos os lados
dessa igualdade, temos que é verdadeira a igualdade
1 + 2 + · · ·+ n+ (n+ 1) = n(n+ 1)
2
+ n+ 1 =
n(n+ 1) + 2(n+ 1)
2
=
(n+ 1)(n+ 2)
2
,
o que estabelece a veracidade de P (n+ 1).
Pelo Princípio de Indução, tem-se que a fórmula P (n) é verdadeira para
todo n ∈ N.
+ Na Sala de Aula - Considerações sobre o Rigor - Clique para ler
Exemplo 3
Queremos validar a fórmula
P (n) : 12 + 22 + · · ·+ n2 = n(n+ 1)(2n+ 1)
6
. (3.2)
6
Unidade 3
O Princípio de Indução Matemática
Note que
P (1) : 12 =
1(1 + 1)(2+ 1)
6
é verdadeira.
Suponha que, para algum n ∈ N, se tenha que P (n) é verdadeira, isto é,
(1.2) é válida. Somando (n + 1)2 a ambos os lados da igualdade (1.2), temos
que
12 + 22 + · · ·+ n2 + (n+ 1)2 = n(n+ 1)(2n+ 1)
6
+ (n+ 1)2 =
n(n+ 1)(2n+ 1) + 6(n+ 1)2
6
=
(n+ 1)[n(2n+ 1) + 6(n+ 1)]
6
=
(n+ 1)[(n+ 1) + 1][2(n+ 1) + 1]
6
,
estabelecendo assim a veracidade de P (n+ 1).
Portanto, a fórmula é válida para todo n ∈ N.
Exemplo 4
Vamos provar que é verdadeira, para todo n ∈ N, a fórmula:
P (n) :
1
1.2
+
1
2.3
+ · · ·+ 1
n(n+ 1)
=
n
n+ 1
. (3.3)
Observemos inicialmente que
P (1) :
1
1.2
=
1
1 + 1
é verdadeira.
Suponhamos que, para algum n, tem-se que P (n) é verdadeira, ou seja,
que a fórmula (1.3) seja verdadeira para esse valor de n. Somando a ambos os
lados dessa igualdade
1
(n+ 1)(n+ 2)
, temos que
1
1.2
+
1
2.3
+ · · ·+ 1
n(n+ 1)
+
1
(n+ 1)(n+ 2)
=
n
n+ 1
+
1
(n+ 1)(n+ 2)
=
n+ 1
n+ 2
,
mostrando, assim, que P (n+ 1) é verdadeira.
7
Unidade 3
O Poder do Método de Indução
Portanto, pelo Princípio de Indução Matemática, temos que a fórmula vale
para todo n ∈ N.
A seguir, vamos estabelecer, por meio de indução, as propriedades usuais
das potências.
Proposição 4 Sejam a, b ∈ A e m,n ∈ N. Então,
i) am · an = an+m.
ii) (am)n = amn.
iii) (a · b)n = an · bn.
Demonstração
Provaremos (i), deixando o restante como exercício.
Fixemos a ∈ A e m ∈ N, arbitrariamente. Demonstremos a propriedade
por indução sobre n.
Para n = 1, a propriedade é válida, pois, pelas definições,
am · a1 = am · a = am+1.
Por outro lado, supondo que am · an = am+n, temos que
am · an+1 = am · (an · a) = (am · an) · a = am+n · a = am+n+1.
Isso, pelo Princípio de Indução Matemática, prova a nossa propriedade.
Exemplo 5
Utilizando a noção de potência e de suas propriedades, mostraremos que 3
divide 5n + 2 · 11n nos inteiros, para todo n ∈ N.
De fato, para n = 1, temos que 3 divide 51 + 2 · 111 = 27.
Suponha, agora, que, para algum n ≥ 1, saibamos que 3 divide 5n+2 ·11n.
Logo, existe um número inteiro a tal que
5n + 2 · 11n = 3a.
Mutiplicando por 5 ambos os lados da igualdade acima, temos
5 · 3a = 5n+1 + 5 · 2 · 11n = 5n+1 + 2 · 11 · 11n − 12 · 11n.
8
Unidade 3
O Princípio de Indução Matemática
Daí segue-se a igualdade
5n+1 + 2 · 11n+1 = 5 · 3a+ 12 · 11n,
cujo segundo membro é divisível por 3, por ser igual a 3(5a+ 4 · 11n).
Assim, provamos que 3 divide 5n+1 + 2 · 11n+1, o que, pelo Princípio de
Indução Matemática, acarreta que 3 divide 5n + 2 · 11n, para todo número
natural n.
Pode ocorrer que uma determinada propriedade seja válida para todos os
números naturais a partir de um determinado valor a, mas não necessariamente
para valores menores. Como proceder nesses casos? Por exemplo, como provar
que a desigualdade 2n > n2 é verdadeira para todo valor de n natural maior ou
igual do que 5? Fazemos isso baseados na seguinte pequena generalização do
Princípio de Indução Matemática:
Teorema 1
Seja P (n) uma sentença sobre N, e seja a ∈ N. Suponha que:
(i) P (a) é verdadeira, e
(ii) qualquer que seja n ∈ N, com n ≥ a, sempre que P (n) é verdadeira,
segue-se que P (n+ 1) é verdadeira.
Então, P (n) é verdadeira para todo número natural n ≥ a.
Demonstração
Defina o conjunto
S = {m ∈ N; P (m+ a− 1) }.
Por (i) temos que 1 ∈ S. Por outro lado, se m ∈ S, temos que P (m + a −
1) é verdadeira. Logo, por (ii), P (m + 1 + a − 1) é verdadeira. Portanto,
m+ 1 ∈ S. Em vista do Princípio de Indução Matemática, temos que S = N.
Consequentemente, P (n) é verdadeira para todo n ≥ a.
Exemplo 6
Vamos mostrar que a desigualdade na sentença P (n) : 2n > n2 é verdadeira,
para todo número natural n ≥ 5.
9
Unidade 3
O Poder do Método de Indução
Note que P (1) : 21 > 12 é verdadeira, P (2) : 22 > 22 é falsa, P (3) : 23 > 32
é falsa e P (4) : 24 > 42 é falsa. Tudo isso não importa, pois queremos verificar
a veracidade dessa desigualdade para n ≥ 5.
De fato, temos que P (5) : 25 > 52 é verdadeira. Seja n ≥ 5 tal que
2n > n2. Multiplicando ambos os lados da desigualdade acima por 2, obtemos
2n+1 > 2n2. Note que 2n2 > (n + 1)2, se n ≥ 3, pois tal desigualdade é
equivalente a n(n − 2) > 1. Daí, deduzimos que 2n+1 > (n + 1)2, o que
significa que P (n + 1) é verdadeira, estabelecendo o resultado em vista do
Teorema 1.
Exemplo 7
Um banco tem um suprimento ilimitado de notas de 3 e de 5 (unidades de
moeda). Mostre que ele pode pagar qualquer quantia (de unidades de moeda)
maior do que 7.
Para isto, basta mostrar que a sentença:
P (n) : A equação 3x+ 5y = n tem solução em (N ∪ {0})× (N ∪ {0}),
é verdadeira para todo n ≥ 8.
De fato, ela é verdadeira para n = 8, pois a equação 3x+ 5y = 8 admite a
solução (x, y) = (1, 1).
Suponha agora que a equação 3x + 5y = n tenha uma solução (a, b) para
algum n ≥ 8; isto é, 3a + 5b = n. Note que, para qualquer solução (a, b),
devemos ter a ≥ 1 ou b ≥ 1.
Se b ≥ 1, observando que 3× 2− 5× 1 = 1, segue que
3(a+ 2) + 5(b− 1) = 3a+ 5b+ 3× 2− 5× 1 = 3a+ 5b+ 1 = n+ 1,
o que mostra que a equação 3x + 5y = n + 1 admite a solução (a + 2, b− 1)
em (N ∪ {0})× (N ∪ {0}).
Se, por acaso, b = 0, então, a ≥ 3; usando a igualdade −3× 3+5× 2 = 1,
temos
3(a− 3) + 5× 2 = 3a− 3× 3 + 5× 2 = 3a+ 5b+ 1 = n+ 1,
o que mostra que a equação 3x + 5y = n + 1 admite a solução (a− 3, b + 2)
em (N ∪ {0})× (N ∪ {0}).
10
Unidade 3
O Princípio de Indução Matemática
Mostramos assim, que, em qualquer caso, a equação 3x+5y = n+1 admite
solução, sempre que a equação 3x+5y = n, para algum n ≥ 8, tenha solução.
Como o resultado vale para n = 8, segue a conclusão desejada pelo Teorema 1.
Note que n0 = 8 é o menor valor de n para o qual a equação tem solução
para todo n ≥ n0.
11
Unidade 3
Exercícios Recomendados
3.3 Exercícios Recomendados
1. Mostre, por indução, a validez das seguintes fórmulas:
(a) 1.20 + 2.21 + 3.22 + · · ·+ n.2n−1 = 1 + (n− 1)2n;
(b)
(
1 +
1
1
)(
1 +
1
2
)2
· · ·
(
1 +
1
n− 1
)n−1
=
nn−1
(n− 1)! ,
(c) 1.1! + 2.2! + 3.3! + · · ·+ n.n! = (n+ 1)!− 1.
2. Sejam a e b números reais distintos. Mostre que, para todo n ∈ N, vale
a igualdade:
bn + abn−1 + a2bn−2 + · · ·+ an−1b+ an = b
n+1 − an+1
b− a .
3. Se senα 6= 0, mostre que, para todo n ∈ N, vale a igualdade:
cosα · cos 2α · cos 22α · · · cos 2nα = sen 2
n+1α
2n+1 senα
.
Sugestão: Use a fórmula sen 2β = 2 sen β cos β.
4. Para todo n ∈ N, mostre que, nos inteiros,
(a) 80 divide 34n − 1;
(b) 9 divide 4n + 6n− 1;
(c) 8 divide 32n + 7;
(d) 9 divide n4n+1 − (n+ 1)4n + 1.
5. Mostre que
(a) n! > 2n, se n ≥ 4;
(b) n! > 3n,se n ≥ 7;
(c) n! > 4n, se n ≥ 9.
6. Prove que, para todo n natural, vale a desigualdade:
1
2
· 3
4
· 5
6
· · · 2n− 1
2n
≤ 1√
3n+ 1
.
12
Unidade 3
O Princípio de Indução Matemática
7. Mostre que o número de diagonais de um polígono convexo de n lados é
dado por
dn =
n(n− 3)
2
.
3.4 Exercícios Suplementares
1. Mostre que n0 = 32 é o menor valor para o qual a equação 5x+ 9y = n
possui solução em (N ∪ {0})2 para todo n ≥ n0.
2. Prove que, para qualquer número natural n:
a) n3 + (n+ 1)3 + (n+ 2)3 é divisível por 9;
b) 32n+2 + 8n− 9 é divisível por 16;
c) 4n + 15n− 1 é divisível por 9;
d) 11n+2 + 122n+1 é divisível por 133;
e) 23
n
+ 1 é divisível por 3n+1.
3. Prove que:
a) 2n > n, onde n é um número natural arbitrário;
b)
1 · 3 · 5 · · · (2n− 1)
2 · 4 · 6 · · · 2n ≤
1√
2n+ 1
, para qualquer n ∈ N;
c)
1
n+ 1
+
1
n+ 2
+ · · ·+ 1
2n
>
13
24
, se n ∈ N e n ≥ 2.;
d) 2n > 1 + n
√
2n−1, se n ∈ N e n ≥ 2.
4. Suponha que x+ 1
x
seja um número natural. Prove que xn+ 1xn
é também
um número natural, qualquer que seja o número natural n.
5. Mostre que o número 111 . . . 1 (formado por 3n algarismos iguais a 1) é
divisível por 3n.
Sugestão: Para o passo indutivo, divida o número escrito com 3n+1
algarismos iguais a 1 pelo número formado por 3n algarismos iguais a 1
e verifique que o resultado é um número divisível por 3.
13
Unidade 3 Textos Complementares
3.5 Textos Complementares
Para Saber Mais Comentário
Note que, na argumentação acima, poderia parecer que estamos usando
o fato de P (n) ser verdadeira para deduzir que P (n + 1) é verdadeira para
em seguida concluir que P (n) é verdadeira. O que está ocorrendo? Estamos
usando a tese para provar o resultado?
A resposta é não! Preste bem atenção, pois essa é a parte mais delicada de
toda a trama.
Dado um número natural n, temos duas possibilidades:
(a) P (n) é verdadeira, ou (b) P (n) é falsa.
A hipótese (ii) do Princípio não exige em absoluto que assumamos P (n)
verdadeira para todo n ∈ N, podendo eventualmente ser falsa para algum valor
de n, ou mesmo para todos os valores de n. O que a hipótese (ii) exige é
que sempre que algum n pertença à categoria (a), acima, então n+1 também
pertença a essa mesma categoria; não exigindo nada quando n pertencer à
categoria (b).
Por exemplo, a sentença P (n) : n = n+1 satisfaz (por vacuidade) a hipótese
(ii) do Princípio, já que nenhum n ∈ N pertence à categoria (a). O que falha
para que o Princípio de Indução nos garanta que P (n) é verdadeira para todo
n é que a hipótese (i) não é verificada, pois P (1) : 1 = 2 é falsa!
14
Unidade 3
O Princípio de Indução Matemática
Para Saber MaisIndução Empírica vs Indução Matemática
É preciso ter clareza que a Indução Matemática é diferente da indução
empírica das ciências naturais, em que é comum, após um certo número de
experimentos, necessariamente finito, enunciar leis gerais que governam o fenô-
meno em estudo. Essas leis são tidas como verdades, até prova em contrário.
Na matemática, não há lugar para afirmações �verdadeiras até prova em con-
trário�. A Prova por Indução Matemática trata de estabelecer que determinada
sentença sobre os naturais é sempre verdadeira.
A indução empírica foi batizada, de modo irônico, pelo matemático, filósofo
e grande humanista inglês do século passado, Bertrand Russel (1872-1970), de
indução galinácea, com base no seguinte conto:
Havia uma galinha nova no quintal de uma velha senhora. Diariamente,
ao entardecer, a boa senhora levava milho às galinhas. No primeiro dia, a
galinha, desconfiada, esperou que a senhora se retirasse para se alimentar. No
segundo dia, a galinha, prudentemente, foi se alimentando enquanto a senhora
se retirava. No nonagésimo dia, a galinha, cheia de intimidade, já não fazia
caso da velha senhora. No centésimo dia, ao se aproximar a senhora, a galinha,
por indução, foi ao encontro dela para reclamar o seu milho. Qual não foi a
sua surpresa quando a senhora pegou-a pelo pescoço com a intenção de pô-la
na panela.
15
Unidade 3 Textos Complementares
Na Sala de Aula Considerações sobre o Rigor
Neste curso, o nosso objetivo é mostrar como se pode estabelecer um maior
padrão de rigor no tratamento de problemas matemáticos que ocorrem no En-
sino Médio, mas isso não deve ser tomado ao pé da letra na sua prática docente.
Certos argumentos informais, quando acompanhados de um raciocínio correto,
são corriqueiramente aceitos. Por exemplo, o argumento utilizado por Gauss
para somar os n primeiros números naturais é perfeitamente aceitável. Por-
tanto, um conselho: use o formalismo para ajudar e não para atrapalhar e
nunca o deixe se sobrepor à criatividade, pois, via de regra, primeiro vem a
descoberta para depois vir a formalização. Procure estimular sempre os seus
alunos a serem criativos. Num primeiro momento, deixe as ideias fluirem, só
depois preocupe-se com a sua organização e formalização.
16
	O Princípio de Indução Matemática
	Introdução
	O Poder do Método de Indução
	Exercícios Recomendados
	Exercícios Suplementares
	Textos Complementares