Princípio da Indução Matemática

Prévia do material em texto

Estruturas Matemáticas para Computação
Princípio da Indução - Aula 01
Vinicius Rispoli
29 de outubro de 2012
1 Introdução
Nesta seção faremos uma breve introdução do que se tratará essa primeira parte do curso de Estruturas
Matemáticas para Computação.
1.1 O que é Teoria dos Números?
Teoria dos Números, um ramo da matemática pura, é dedicada primeiramente ao estudo das propriedades
do números inteiros, como por exemplo: paridade, divisibilidade, primalidade, aditividade e multiplicabilidade
e etc. Certamente é um dos ramos mais antigos da matemática, tendo sido encontrado trabalhos e referências
que datam de 1800 a.C.
1.2 Pra que serve a Teoria dos Números afinal?
Se a Teoria dos Números é um ramo da matemática pura e abstrata, por que, afinal, o estudante de Engenharia
de Software precise estudar isso? Começemos, então, com um exemplo simples da aplicabilidade da Teoria dos
Números na Computação.
Talvez um dos conceitos mais enraizados nas nossas cabeças seja o da multiplicação. Além disso, aprendemos
desde criança que dado um número inteiro positivo n > 1 é possível escrevê-lo na forma fatorada
n = pα11 p
α2
2 · · · pαll ,
em que p1 < p2 < · · · < pl são número primos e a1, · · · , αl são inteiros positivos. Todos nós sabemos o tanto
que é fácil fatorar um número inteiro que não seja muito grande. Já fizemos isso diversas vezes na nossa vida
escolar. Entretanto, fazer essa mesma operação pode ser muito difícil se o número inteiro em questão for muito
grande.
Um algoritmo relativamente recente e um dos mais velozes para fatorar números inteiros contendo muitos
dígitos é conhecido como Number Field Sieve (NFS). Este algoritmo é capaz de fatorar um inteiro N em
aproximadamente
exp
(
c(logN)1/3(log logN)2/3
)
operações de bits, em que c é uma constante real positiva (cujo um valor admissível é c ≈ 1.9). Imagine agora
fatorar um número inteiro que é produto de dois números primos com 100 dígitos cada. Não parece ser uma
tarefa simples, e pelo fato de não ser, um dos algoritmos mais famosos de criptografia, o RSA, utiliza este
conceito na produção de suas chaves de segurança o produto de números primos com grandes quantidades de
dígitos.
O exemplo acima é apenas uma das aplicações possíveis da Teoria dos Números na Computação, mas é fácil
encontrar aplicações na química, biologia, na teoria das telecomunicações e etc.
Espero que este pequeno texto sirva para motivá-los para um curso com muita abstração e algumas aplicações
na computação proporcionados por esta bonita área da matemática. Na seção a seguir começamos o conteúdo
do nosso curso tratando do Princípio da Indução, uma ótima ferramenta para demonstrar fórmulas e teoremas.
1
2 Princípio da Indução
O Princípio da Indução Matemática é um poderoso método de prova que é frequentemente usado para
estabelecer a validade de afirmações que são dadas em termos dos números naturais. Embora a sua utilidade
está restrita a este contexto especial, a Indução Matemática é uma ferramenta indispensável em todas as
áreas da matemática. Nesta seção, iremos mostrar a uma das formas do princípio e também diversos exemplos
de como as provas por indução procedem.
Estamos assumindo que todos estão familiarizados com o conjunto dos números naturais
N = {1, 2, 3, 4, · · ·},
com as operações aritméticas usuais de adição e multiplicação. Então estabelecemos o princípio da indução.
Princípio da Indução Matemática
Suponha que S ⊆ N e que ambas as afirmações (a) e (b) abaixo sejam verdade.
(a) 1 ∈ S, e
(b) Para todo n ∈ N, se n− 1 ∈ S, então n ∈ S.
Então temos que S = N.
Em outras palavras, oPrincípio da Indução Matemática diz que dado qualquer subconjunto dos números
naturais contendo o número 1, e que pode ser mostrado que contém o número n > 1 dado que contém o número
n − 1, então este subconjunto deverá ser todo o conjunto dos números naturais N. A parte (a) será chamada
de passo de indução, e a hipótese que n − 1 ∈ S, parte (b), será chamada de hipótese de indução. Primeiro,
estabelecemos o passo de indução, então assumimos que a hipótese de indução seja verdadeira e, finalmente,
provamos a conclusão de que n ∈ S. Assim, dizemos que por indução n ∈ S para todo n ∈ N.
O Princípio da Indução Matemática é normalmente utilizado em uma situação em que se possui alguma
proposição sobre números naturais. Se P (n) é uma afirmação sobre n ∈ N, então P (n) pode ser verdade para
alguns valores de n e falsa para outros. Por exemplo, se P1(n) é a afirmação: "n2 = n”, então P1(1) é verdade
equanto P1(n) não é para todo n > 1, n ∈ N. Por outro lado, se P2(n) é a afirmação "n2 > 1", então P2(1)
é falso, enquanto P2(n) é verdade para todo n > 1. Neste contexto, o Princípio da Indução Matemática
pode ser reformulado como sendo:
Para cada n ∈ N, seja P (n) uma afirmação sobre n. Suponha que:
(a’) P (1) seja verdade.
(b’) Para cada k ∈ N, se a afirmação P (k) é verdadeira, então P (k + 1) é verdadeira.
Então, a afirmação P (n) é verdadeira para todo n ∈ N.
Consire agora os seguintes exemplos de como utilizar o princípio da indução para validar algumas fórmulas
e afirmações.
Exemplo 1: A fórmula da soma de Gauss
Para qualquer n ∈ N,
n∑
i=1
i =
n(n+ 1)
2
.
Demonstração. Se n = 1, então
∑1
i=1 i = (1)(1 + 1)/2, e o passo de indução é assegurado. Assuma agora que a
hipótese de indução
n−1∑
i=1
i =
(n− 1)(n− 1 + 1)
2
=
(n− 1)n
2
,
seja verdade para algum n− 1 . Considere, então
n∑
i=1
i = n+
n−1∑
i=1
i
= n+
(n− 1)n
2
,
pela hipótese de indução. Logo,
n∑
i=1
i =
2n+ (n− 1)n
2
2
=
(n2 + n)
2
=
n(n+ 1)
2
,
como queríamos mostrar. Portanto, por indução, esta sentença deve ser verdade para todo n ∈ N.
�
Exemplo 2: A Soma Geométrica
Se a, r ∈ R, r 6= 1, n ∈ N, então
n∑
i=0
ari =
a(rn+1 − 1)
r − 1 .
Demonstração. Se n = 1, então
1∑
i=0
ari = a+ ar
= a(r + 1)
=
a(r + 1)(r − 1)
r − 1
=
a(r1+1 − 1)
r − 1 ,
que é o passo de indução. Considere que a hipótese de indução
n∑
i=0
ari =
a(rn+1 − 1)
r − 1
seja verdade para algum n. Assim, pela hipótese de indução, temos
n+1∑
i=0
ari = arn+1 +
n∑
i=0
ari
= arn+1 +
a(rn+1 − 1)
r − 1
=
a(rn+2 − 1)
r − 1 ,
como queríamos mostrar. Portanto, pelo princípio de indução
n∑
i=0
ari =
a(rn+1 − 1)
r − 1 ,
é verdade para todo n ∈ N.
�
Antes de partimos para o próximo exemplo, faremos a definição do coeficiente binomial.
Definição 1: Coeficiente Binomial
Sejam k, n ∈ N com 0 ≤ k ≤ n, então o símbolo
(
n
k
)
é dado por
(
n
k
)
=
n!
k!(n− k)! ,
em que i! = 1.2. · · · .i e 0! = 1.
Exemplo 3: Teorema Binomial
Seja x, y ∈ R, e n ∈ N. Então
(x+ y)n =
n∑
i=0
(
n
i
)
xn−iyi.
3
Demonstração. Usaremos o princípio da indução para provar esse teorema. Se n = 1, então
(x+ y)n = (x+ y)1
=
1∑
i=0
(
1
i
)
x1−iyi
=
(
1
0
)
x1y0 +
(
1
1
)
x0y1,
o que assegura o passo de indução. Assuma que para algum n ∈ N valha a fórmula
(x+ y)n =
n∑
i=0
(
n
i
)
xn−iyi.
Então, considere
(x+ y)n+1 = (x+ y) · (x+ y)n
= (x+ y)
n∑
i=0
(
n
i
)
xn−iyi.
Pela lei distributiva, e pelas as propriedades do somatório, podemos reescrever a fórmula acima como
=
n∑
i=0
(
n
i
)
xn+1−iyi +
n∑
i=0
(
n
i
)
xn−iyi+1,
e, fazendo a mudança de índices j = i+ 1 no somatório a direita, temos
=
n∑
i=0
(
n
i
)
xn+1−iyi +
n+1∑
j=1
(
n
j − 1
)
xn+1−jyj .
Fazendo a retirada do primeiro termo, i = 0, do somatório a esquerda, tirando o último termo, j = n + 1, do
somatório a direita e introduzindo o novo índice do somatório k, temos
xn+1 + yn+1 +
n∑
k=0
[(
n
k
)
+
(
n
k − 1
)]
xn+1−kyk.
Considere agora os dois coeficientes binomiais do somatório acima, então(
n
k
)
+
(
n
k − 1
)
=
n!
k!(n− k)! +
n!
(k − 1)!(n− k + 1)!
=
n!
(k − 1)!(n− k)!
[
1
k
+
1
(n− k + 1)
]
=
n!
(k − 1)!(n− k)!
[
n− k + 1 + k
k(n− k + 1)
]
=
n!
(k − 1)!(n− k)! ·
n+ 1
k(n− k + 1)
=
(n+ 1)!
k!(n+ 1− k)!
=
(
n+ 1
k
)
,
ou seja, podemos reescrever a última expressão do somatório como sendo
(x+ y)n+1 = xn+1 + yn+1 +
n∑
k=0
[(
n
k
)
+
(
n
k − 1
)]
xn+1−kyk
= xn+1 + yn+1 +
n∑
k=0
(
n+ 1
k
)
xn+1−kyk
=
n+1∑k=0
(
n+ 1
k
)
xn+1−kyk.
Portanto, pelo princípio da indução este resultado vale para todo n ∈ N.
4
�
Exemplo 4:
O número na forma 11n − 7n pode ser dividido por 4, para todo n ∈ N.
Demonstração: Para n = 1, temos que 111 − 71 = 4 que é um número que pode ser dividido por 4. Assuma
agora que para algum k ∈ N o número 11k − 7k possa ser divido por 4. Então
11k+1 − 7k+1 = 11k+1 − 11.7k + 11.7k − 7k+1
= 11(11k − 7k) + 7k(11− 7).
Pela hipótese de indução, o número 11k−7k é divisível por 4, mas 11−7 também. Logo, a soma 11(11k−7k)+
7k(11 − 7) é divisível por 4. Portanto, por indução temos que o número 11n − 7n é divisível por 4 para todo
n ∈ N.
�
Pode acontecer da afirmação P (n) ser falsa para alguns números naturais, mas ser verdade para todo n ≥ n0
para algum valor particular n0. O Princípio da Indução Matemática pode ser modificado para lidar com
esse tipo de situação.
Princípio da Indução Matemática Segunda Versão
Seja n0 ∈ N e seja P (n) uma afirmação para cada n ≥ n0. Suponha que:
(a) A afirmação P (n0) seja verdadeira.
(b) Para todo k ≥ n0, a validade da afirmação P (k) implica na validade da afirmação P (k + 1).
Então, a afirmação P (n) é verdade para todo n ≥ n0.
Exemplo 5:
Para todo n ≥ 3, a inequação 2n > 2n+ 1 é válida.
Demonstração. Se n = 1, temos 21 < 2.1+ 1. Além disso, para n = 2, 22 < 2.2+ 1. Considere agora, n = 3,
temos então 23 > 2.3 + 1. Assuma agora que 2k > 2k + 1, para algum k > 1 ∈ N, e então multiplicando essa
desigualdade por 2, temos
2k+1 > 2(2k + 1)
= 4k + 2
= 2k + (2k + 2)
> 2k + 3
= 2(k + 1) + 1.
Como 2k + 2 > 3 para todo k > 1, então a desiguldade é válida para todo k > 1. Portanto, com a base n0 = 3,
temos pelo princípio da indução que a inequação é válida para todo n ≥ 3.
�
3 Exercícios
1. Prove as afirmações utilizando o princípio da indução.
(a) 1/(1.2) + 1/(2.3) + · · ·+ 1/[n(n+ 1)] = n/(n+ 1) para todo n ∈ N.
(b) 13 + 23 + · · ·+ n3 =
[
n(n+1)
2
]2
para todo n ∈ N.
(c) 3 + 11 + · · ·+ (8n− 5) = 4n2 − n para todo n ∈ N.
(d)
n∑
k=1
(−1)k+1k2 = (−1)n+1n(n+ 1)
2
para todo n ∈ N.
(e)
n∑
k=1
(2k − 1)2 = (4n
3 − n)
3
para todo n ∈ N.
(f) n3 + 5n pode ser dividido por 6 para todo n ∈ N.
(g) 52n − 1 pode ser dividido por 8 para todo n ∈ N.
(h) 5n − 4n− 1 pode ser dividido por 16 para todo n ∈ N.
(i) n3 + (n+ 1)3 + (n+ 2)3 pode ser dividido por 9 para todo n ∈ N.
(j)
n∑
k=1
1√
k
>
√
n para todo n ∈ N, n > 1.
5
4 Referências
• Bartle, R.G., Sherbert, D. R., Introduction to Real Analisys. Fourth Edition. John Wiley & Sons,
Inc. Illinois, USA, 2010.
• Mollin, R. A., Fundamental Number Theory With Applications. Second Edition. Chapman &
Hall. Calgary, Canada, 2008.
• Santos, J. P. O., Introdução à Teoria dos Números. Terceira Edição. Coleção Matemática Univer-
sitária. IMPA, Rio de Janeiro, Brasil, 2011.
6