Aula 2.

O Principio de Indução Finita

2.1 Principio e sua prova

A indução é uma técnica para provar uma afirmação — um teo-

rema ou uma fórmula — que é afirmada sobre cada número natu-
ral. Por exemplo,
y n
n · ( n + 1)
i a nt
1+2+3+···+n =
2
.

os t
Isso afirma que a soma dos números consecutivos de 1 a n é dada
pela fórmula à direita. Queremos provar que isso será verdade para
f . K
n = 1, n = 2, n = 3 e assim por diante. Agora podemos testar a
fórmula para qualquer número, digamos n = 3:
Pro
3·4
f t ) .
1+2+3 =
2
=6
r a
0 4·5
(D
– que é verdade. Isso também é verdadeiro para n = 4:

0 1 2
1+2+3+4 =
2
= 10.

AT
Mas como provar essa regra para cada valor de n?

M
O método de prova é o seguinte. Mostramos que se a afirmação
s
ç õe
for verdadeira para qualquer número específico k (por exemplo,
104), ela também será verdadeira para seu sucessor, k + 1 (por

o t a
exemplo, 105). Em seguida, mostramos que a afirmação será ver-

A n dadeira para 1. Segue-se então que o afirmação será verdadeira

para 2. Portanto, será verdade para 3. Assim por diante é ver-
dadeiro para qualquer número natural. Isso é chamado de princípio
de indução finita.
Theorem 2.1: (Principio de Indução Finita, PIF)

Seja a um inteiro positivo dado. Suponhamos que para cada inteiro n ≥ a está dada uma afirmação
A(n) de forma que:

(i) A( a) é verdadeira.

(ii) Se para um inteiro k ≥ a, A(k) é verdadeira, então A(k + 1) é verdadeira.

Então a afirmação A(n) é verdadeira para todo inteiro n ≥ a.

 2

Prova

Seja S o conjunto dos inteiros m tais que A(m) seja falsa. Suponhamos que a afirmação A(n) seja
falsa para algum inteiro. Então, o conjunto S é não-vazio.
Conforme o Principio da Boa Ordem (veja Aula 1) existe elemento minimal m0 = min S. Como
m0 − 1 ∈/ S (pois m0 é minimal) assim A(m0 − 1) é verdadeira. Conforme (ii), para k = m0 − 1 ter-
emos então que
A ( k + 1) = A ( m0 − 1 + 1) = A ( m0 )

é verdadeira. Mas isso é uma contradição, pois m0 é elemento em S ou seja A(m0 ) deve ser falso.
Assim S é conjunto vazio e A(n) é verdadeira para todo inteiro n ≥ a.

2.2 Exemplos
y n
Para aplicar o principio da indução finita nos exemplos precisamos

i a nt
fazer 3 coisas:

Base: Verificar a afirmação no menor caso possível.

os t
Hipótese: Assumir que a afirmação seja verdadeira no caso n = k.
f . K
Passo: Usando hipótese mostrar que a afirmação é verdadeira no caso
Pro
n = k + 1.

f t ) .
Exemplo 2.1
r a
Provaremos agora que a formula
0 (D
0 1 2 1+2+...+n =
n ( n + 1)

AT
é verdadeira para todo n ≥ 1.
2

s M
Base n=1 . A fórmula acima dá

ç õe 1(1 + 1)

o t a 1=
2
, ou seja , 1 = 1

A n Assim, a afirmação é verdadeira para n = 1. Deveremos mostrar agora que, se a afirmação é ver-
dadeira para n = k, então também é verdadeira para n = k + 1.
Hipótese n=k . Suponha que
k ( k + 1)
1+2+...+k = , (2.1)
2
e mostremos que
(k + 1)(k + 2)
1 + 2 + . . . + k + ( k + 1) = .
2
Passo n=k+1 . Somando k + 1 a ambos os lados da (2.1) temos

k ( k + 1) k ( k + 1) + 2( k + 1)
1 + 2 + . . . + k + ( k + 1) = + ( k + 1) =
2 2
isto é
(k + 1)(k + 2)
1 + 2 + . . . + k + ( k + 1) =
2
que é exatamente o que queríamos demonstrar.
 3

Exemplo 2.2

Provaremos agora que a formula

1 + 3 + . . . + (2n − 1) = n2

é verdadeira para todo n ≥ 1.

Base n=1 . Para n = 1, a fórmula acima dá

1 = 12 , ou seja , 1 = 1

Assim, a afirmação é verdadeira para n = 1. Deveremos mostrar agora que, se a afirmação é ver-
dadeira para n = k, então também é verdadeira para n = k + 1.
Hipótese n=k . suponha que
1 + 3 + . . . + (2k − 1) = k2 (2.2)
y n
e mostremos que
1 + 3 + . . . + (2k − 1) + (2k + 1) = (k + 1)2
i a nt
Passo n=k+1 . Somando 2k + 1 a ambos os lados da (2.2) temos
os t
f . K
1 + 3 + . . . + (2k − 1) + (2k + 1) = k2 + 2k + 1

isto é
Pro
) .
1 + 3 + . . . + (2k − 1) + (2k + 1) = (k + 1)2

f t
que é exatamente o que queríamos demonstrar.
r a
Exemplo 2.3
0 (D
Vamos mostrar que
0 1 2
AT n 3 < 2n

M
é verdadeira para todo n ≥ 10.
s
ç õe
Base n=10 . Para n = 10, temos

o t a 103 = 1000, 210 = 1028, ou seja , 103 < 210 .

An Assim, a afirmação é verdadeira para n = 10. Deveremos mostrar agora que, se a afirmação é ver-
dadeira para n = k, então também é verdadeira para n = k + 1.
Hipótese n=k . Assim, suponha que
k 3 < 2k . (2.3)

Passo n=k+1 . Temos

(k + 1)3 = k3 + 3k2 + 3k + 1
Pelo hipótese (2.5) k3 < 2k , além disso obviamente 3k < 3k2 e 1 < k2 . Assim

(k + 1)3 = k3 + 3k2 + 3k + 1 < 2k + 3k2 + 3k2 + k2 = 2k + 7k2 . (2.4)

Como k ≥ 10, assim 7k2 < k3 < 2k , portanto (2.4) escreva-se como

(k + 1)3 < 2k + 7k2 < 2k + 2k = 2k+1

que é exatamente o que queríamos demonstrar.

 4

Exemplo 2.4

Vamos mostrar que      

1 1 1 1 n+1
1− 1− 1− ··· 1− 2 =
4 9 16 n 2n
é verdadeira para todo n ≥ 2.
Base n=2 . Para n = 2, temos
 
1 3 2+1 3 3 3
1− = , = , ou seja , = .
4 4 2·2 4 4 4

Hipótese n=k . Suponha que

     
1 1 1 1 k+1
1− 1− 1− ··· 1− 2 = (2.5)
4 9 16 k 2k

y n
Passo n=k+1 . Devemos mostrar que

i a nt

1−
1
4

1−
1
9

1−
1
16
 

k
1
··· 1− 2

1−
1
( k + 1)2

=
k+2
2( k + 1) os t
Pelo hipótese o lado esquerdo pode ser escrito como
f . K
k+1

1

k + 1 ( k + 1)2 − 1
P
k2 + 2k + 1 − 1ro k+2
2k
· 1−
( k + 1) 2
=
2k
·
( k + 1) 2
=
)
2k(k + 1)
f t . =
2( k + 1)
,

que é exatamente o que queríamos demonstrar.

r a
2.3 0
Numeros de Fibonacci e Segunda forma da PIF
(D
0 1 2
AT
Você pode ter ouvido falar dos números de Fibonacci. Eles ocorrem
com frequência em matemática e ciências da vida. Pela primeira
M
vez eles ocorreram no livro Liber Abaci (1202) de Fibonacci, onde
s
ç õe
foi usada para calcular o crescimento das populações de coelhos.
Os números de Fibonacci formam uma sequência em que cada

o t a
termo, exceto os dois primeiros, é a soma dos dois números anteri-

An ores. Matematicamente, se denotarmos o n-th número de Fibonacci

Fn , então
Fn = Fn−1 + Fn−2

Isso é chamado de relação de recorrência para Fn .

A relação de recorrência implica que precisamos começar com
dois valores iniciais. Frequentemente, começamos com F0 = 0 e
F1 = 1. Combinamos a relação de recorrência para Fn e seus valores
iniciais juntos em uma definição:
Livro Liber Abaci (1202)
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 , para n ≥ 2

Temos que especificar que a relação de recorrência é válida ape-

nas quando n ≥ 2, porque este é o menor valor de n para o qual
podemos usar a relação de recorrência.
A soma do zero e dos primeiros números de Fibonacci nos dá o
 5

segundo número de Fibonacci:

F2 = F1 + F0 = 1 + 0 = 1

Continuando desta forma, encontramos

F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, ...

Os números de Fibonacci têm muitas propriedades interessantes,

e existem vários resultados relativos aos números de Fibonacci.
Para começar, considere a propriedade

Fn < 2n , n≥1

Como o provaríamos por indução? Visto que queremos provar que

a desigualdade é válida para todos os n ≥ 1, devemos verificar o
y n
nt
caso de n = 1 no passo base. Quando n = 1, temos F1 = 1 que é,
obviamente, menor que 21 = 2. Na hipótese indutiva, assumimos

t i a
os
que a desigualdade se mantém quando n = k para algum inteiro
k ≥ 1; isto é, nós assumimos

Fk < 2k
f . K
para algum inteiro k ≥ 1. Em seguida, queremos provar que a
Pro
t ) .
desigualdade ainda é válida quando n = k + 1. Então, precisamos
f
provar que
Fk+1 < 2k+1 r a
(D
Para fazer uso da hipótese indutiva, precisamos aplicar a relação
0
0 1 2
de recorrência dos números de Fibonacci. Ele nos diz que Fk+1 é a
soma dos dois números de Fibonacci anteriores; isso é,

AT Fk+1 = Fk + Fk−1

s M
ç õe
A única coisa que sabemos da hipótese indutiva é Fk < 2k . Portanto,
do jeito que está, não nos diz muito sobre Fk+1 . Um remédio é

o t a
assumir na hipótese indutiva que a desigualdade também é válida

An quando n = k − 1; ou seja, também assumimos que

Fk−1 < 2k−1

Portanto, ao contrário de todos os problemas que vimos até agora,

a etapa indutiva neste problema depende dos dois últimos valores
de n em vez de apenas um. Em termos de dominó, imagine que
eles são tão pesados que precisamos do peso combinado de dois
dominós para derrubar o próximo. Então

Fk+1 = Fk + Fk−1 < 2k + 2k−1 = 2k−1 (2 + 1) < 2k−1 · 22 = 2k+1

que irá completar a indução. Essa indução modificada é conhecida

como a segunda forma forte de indução matemática.
 6

Theorem 2.2: (Principio da Indução Finita 2)

Suponhamos que para cada inteiro n ≥ a está dada uma afirmação A(n) de forma que

(i) A( a) é verdadeira;

(i) Se A(m) é verdadeira para todo inteiro m tal que a ≤ m ≤ k então A(k + 1) é verdadeira.

Então A(n) e verdadeira para todo inteiro n ≥ a.

O termo geral Fn da sequencia de Fibonacci cumpre a fórmula

recebida de Binet (em 1843). A fórmula vincula diretamente os
números de Fibonacci e a Numero √ de Ouro (Razão áurea), veja
aqui aqui, onde razão áurea φ = 1+2 5 é a raiz positiva da equação
quadrática
y n
nt
x2 − x − 1 = 0
√
A segunda raiz da equação é negativa: 1−2 5 . e denotado por τ
t i a
Com essas preliminares, a fórmula de Binet é:

K os
φn − τ n
of .
Fn = √
5
Pr
Para provar o formula vamos precisar o seguinte lema:
f t ) . Jacques Philippe Marie Binet (1786–

r a 1856)

(D
Lemma 3.1

1 2 0
Para qualquer solução x de x2 − x − 1 = 0, temos

T0
x n = xFn + Fn−1 , n ≥ 1.

M A
Prova
e s
a ç õ
A prova é por indução. Por definição, F1 = 1 e F0 = 0 de modo que, de fato, x1 = x · 1 + 0 = x. Para

o tn = 2, F2 = F1 = 1, e

An x · xF2 + F1 = x · 1 + 1 = x + 1 = x2
Suponha agora que, para algum n, x n = xFn + Fn−1 e vamos provar que x n+1 = xFn+1 + Fn . Para
isso, multiplique o hipotese identidade por x:

x n+1 = x2 Fn + xFn−1
= ( x + 1) Fn + xFn−1
= x ( Fn + Fn−1 ) + Fn
= xFn+1 + Fn .

Assim recebemos exatamente o que gostariamos de provar.

Agora, por Lemma,

φn = φFn + Fn−1
τ n = τFn + Fn−1 .
 7

Subtraindo um do outro resulta φn − τ n = (φ − τ ) Fn . Segue que

φn − τ n
Fn =
φ−τ
√
Para obter a fórmula de Binet, observe que φ − τ = 5.

2.4 Dominó e Indução

Tem a certa analogia entre o princípio da indução é o efeito dom-

inó. O efeito dominó é o reação em cadeia que consiste em uma
fileira de dominós caindo.
Se você colocasse dez mil dominós na fila em uma mesa muito
longa e quisesse deixá-los cair apenas deixando o primeiro dominó
cair, como o faria?
y n
nt
A melhor ideia provavelmente é colocá-los em uma fila de forma
que:

t i a
(i) Quando o primeiro dominó cair, ele atingirá o segundo dominó.

Kos
(ii) Certifique-se de que cada dominó atingirá o dominó próximo a
ele e que cada dominó atingido cairá.
of .
Pr
f t
cairão. Compare estes condições com as condições na (PIF). .
Se as condições (i) e (ii) forem satisfeitas, todos os dominós
)
r a
0 (D
0 1 2
AT
s M
ç õe
o t a
An
 8

Na verdade, não importa quantos dominós colocamos na mesa,

desde que as condições (1) e (2) sejam satisfeitas, temos certeza de
que todos os dominós cairão.

y n
i a nt
os t
f . K
Pro
f t ) .
r a
0 (D
0 1 2
AT
s M
ç õe
o t a
An
 9

Exercício 2.1: (Trabalho p/ casa)

Mostre que

1 1 1 n
+ +···+ = ,
1·2 2·3 n · ( n + 1) n+1

para todos n ≥ 1.

Exercício 2.2: (Trabalho p/ casa)

Mostre que 2n3 > 3n2 + 3n + 1 para todos n ≥ 3.

y n
nt
Exercício 2.3: (Trabalho p/ casa)

t i a
os
Mostre que na sequencia de Fibonacci F5n sempre é um multiplo
de 5.

f . K
Exercício 2.4: (Trabalho p/ casa)
Pro
f t ) .
Mostre que ( PIF ) ⇒ ( PBO), ou seja por indução, mostre que todo

r a
conjunto não-vazio dos inteiros positivos contém elemento min-
imal.

0 (D
0 1 2
AT
s M
ç õe
o ta
An