BCC 101 – Matemática Discreta I
Indução / Recursão
Indução Forte
1
Fibonacci
Considere a sequência de números de
Fibonacci, definida por:
F0 = 0 F1 = 1
Fn+2 = Fn+1 + Fn
Compare a sequência de Fibonacci com a
sequência de potências de 2:
{Fn } = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
{2n } = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
Podemos conjecturar que Fn < 2n para todo
nN. Como podemos provar isso?
2
Princípio de Prova por Indução
Para provar ∀n≥a. P(n):
Seja n arbitrário e suponha que P(k) é
true, para todo inteiro a ≤ k < n.
Prove que P (n) é true.
n. (a ≤ k < n. P(k))  P(n)
_____________________________{Ind}
n. P(n)
Indução
BCC101 - Matemática Discreta - DECOM/UFOP
Hipótese
de Indução
Indução
3
Fibonacci – solução
Prova.
Caso Base: (precisamos considerar os dois
seguintes casos (porque?))
n = 0: F0 = 0 < 1 = 20 
n = 1: F1 = 1 < 2 = 21 
Caso Indutivo: (queremos provar Fn < 2n)
Temos: Fn = Fn-1 + Fn-2
de indução
< 2n-1 + 2n-2 pela hipótese
= 2·2n-2 + 2n-2
= (2+1)·2n-2
< 22·2n-2 = 2n
Portanto, F < 2n
•
4
Mais erros em provas
Teorema Falso: Todo número de Fibonacci é par
Prova: A prova é por indução forte.
No caso base, verificamos que P(0) é par, pois F0 é 0.
No caso indutivo, para n0, supomos que F0,F1,…,Fn são
pares e usamos a definição da sequência de Fibonacci
para provar que Fn+1 = Fn-1 + Fn é par
Onde está o erro nessa prova?
5
Fibonacci de novo
Prove que, para todo n≥0, Fn é par se e
somente se n é múltiplo de 3.
Prova:
Devemos considerar 3 casos:
n=0: n é divisível por 3 e Fn é par
n=1: n não é divisível por 3 e Fn não é par
n≥2: existem 2 subcasos a considerar:
- n é divisível por 3
- n não é divisível por 3
6
Fibonacci de novo (continuação)
Prova (continuação): n≥2:
-n é divisível por 3:
Então (n-1) e (n-2) não são divisíveis por 3
e, portanto, Fn-1 e Fn-2 são impares. Como
Fn = Fn-1 + Fn-2 , temos que Fn é par.
-n não é divisível por 3:
Então exatamente um dentre (n-1) e (n-2)
é divisível por 3 e, portanto, exatamente
um entre Fn-1 e Fn-2é par. Como
Fn = Fn-1 + Fn-2 , temos que Fn é impar
7
Fatores Primos
Teorema: Todo nN, n>1, pode ser expresso
como um produto de números primos.
Prova: por indução sobre n
 Caso base (n=2): Trivial, já que 2 é primo
e portanto pode ser expresso como um
produto de primos consistindo apenas
dele próprio.
 Caso indutivo: … próximo slide
8
Fatores Primos (continuação)
 Caso indutivo:
 Pela hipótese de indução temos que todo 1<j<n
pode ser expresso como um produto de primos.
 Devemos mostrar que n pode ser expresso como
um produto de primos.
 Existem dois possíveis casos a considerar:
 n é primo: Trivial
 n não é primo. Então existem nos. naturais a
e b, tais que n = a.b e 1< a,b < n.
Pela hipótese de indução a e b podem ser
ambos expressos como produtos de primos.
Portanto, n pode ser expresso como um
produto de primos.
9
Cardinalidade do Conjunto Potência
Prove que, para todo conjunto S, e
todo número n N, se |S| = n então
|P (S)| = 2n
Prova:
 caso base:
- n=0: Então S=e P(S) ={}, e temos que
|P(S)| = 1 = 20.
- n=1: Então S={a},para algum a, e
P(S)={,{a}}, e temos que |P(S)| = 2 = 21.
10
Cardinalidade do Conjunto Potência
(continuação)
Prova:
 caso indutivo:
Suponha que |P(S)| = 2|S|, para todo conjunto
S tal que 1< |S| < n. Seja S tal que |S| = n > 1 e
seja a  S. Temos que |S-{a}|=n-1 e:
P(S) = P(S-{a}) ∪ {X∪{a} | X P(S-{a})}.
Então,
|P(S)| = |P(S-{a})| + | {X∪{a} | X P(S-{a})}|
= 2n-1 + 2n-1
pela H.I
= 2n
11
Exercícios
 Considere a sequência:
a1 = 0
a2 = 2
an = a n div 2 + 2, para n>2
 Encontre os 5 primeiros termos da sequência
 Prove que an é par, para todo n≥1
Considere a sequência:
b1 = 1 bn = 2 b n div 2, para n>2
 Encontre os 5 primeiros termos da sequência
 Prove que bn ≤ n, para todo n≥1
12
Coeficientes Binomiais (n,k)
Coeficientes binomiais ocorrem em
diversas aplicações:
 Combinatória/Probabilidade C (n,k) = número
de maneiras de escolher k elementos de um
conjunto com n elementos
 Algebra: C (n,k) = coeficiente do k esimo termo
na expansão binômio de grau n: (x + y )n
Notação usada comumente:
 n
C (n, k )   
k 
13
Coeficientes Binomiais (n,k)
A maneira mais eficiente de computar
todos os C (n,k) até um determinado n
é via o triângulo de Pascal.
O triângulo de Pascal é construído
colocando 1 no topo (inicialização) e
todo elemento seguinte é definido
recursivamente como a soma dos
números à direita e à esquerda desse
número, na linha anterior. Se tal
número não existe, é considerado 0.
14
combinação n k
e Triângulo Pascal
1
15
combinação n k
e Triângulo Pascal
1
1 1
16
combinação n k
e Triângulo Pascal
1
1 1
1 2 1
17
combinação n k
e Triângulo Pascal
1
1 1
1 2 1
13 31
18
combinação n k
e Triângulo Pascal
1
1 1
1 2 1
13 31
14 6 41
19
combinação n k
e Triângulo Pascal
1
1 1
1 2 1
13 31
14 6 41
1 5 10 10 5 1
20
combinação n k
e Triângulo Pascal
1
1 1
1 2 1
13 31
14 6 41
1 5 10 10 5 1
1 6 15 20 15 6 1
21
n = linha
0
1
2
3
4
5
6
combinação n k
e Triângulo Pascal
0 k = diagonal
1
1
1 1
2
1 2 1
3
1 3 31
1 4 6 4 14
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
Q: Fórmula recursiva para C (n,k)?
22
Coeficientes Binomiais (n,k)
Resposta: Use o triângulo de Pascal.
Base: O topo do triângulo é 1. Portanto,
C (0,0) = 1. Se falta um número, ele é
considerado 0. Isso dá origem a C
(n,k) = 0 se k < 0, ou k > n.
Recursão: Cada valor é a soma dos
números à direita e à esquerda na
linha anterior:
C (n,k) = C (n -1,k-1) + C (n -1,k )
23
Coeficientes Binomiais (n,k)
Resumindo:
ìï0, if k < 0 ou k > n
C(n, k) = í1, if k = 0 ou k = n
ïîC(n -1, k -1) + C(n -1, k), 0 < k < n
Prove que c(n,k) = n! / (k! (n-k)!):
24