BCC 101 – Matemática Discreta I
Indução / Recursão
BCC101 - Matemática Discreta - DECOM/UFOP
1
O outro lado da moeda

Como podemos calcular de 1+2+3+…+n, dado
o valor de n?
BCC101 - Matemática Discreta - DECOM/UFOP
2
Proque precisamos de uma prova?

1+2+3+…+n
Alguns resultados são mostrados na tabela:
Será que podemos garantir que, para qualquer n∈N
1 + 2 + 3 + … + n = n (n+1)/2 ?
BCC101 - Matemática Discreta - DECOM/UFOP
3
Indução

Combina raciocínio indutivo e dedutivo
 buscar um padrão a partir de observações
 formular esse padrão como uma conjectura
 testar se a conjectura pode ser deduzida
(provada) a partir de leis já conhecidas
 O último passo é necessário porque é muito
frequente que se façam conjecturas falsas.
BCC101 - Matemática Discreta - DECOM/UFOP
4
Porque precisamos de uma prova?

Se uma afirmação é verdadeira para todos os
valores que testamos, será que podemos concluir
que ela é verdadeira sempre?

Considere a seguinte proposição:
Proposição 3. Se p é primo, 2p − 1 também é primo.
Testando alguns casos:
Entretanto… 211 −1 = 2047 = 23×89.
A proposição 3 é falsa!
BCC101 - Matemática Discreta - DECOM/UFOP
5
Principio de Indução Matemática
Universo de discurso: N = {0, 1, 2, …}
 Predicado P

 P(n) é uma proposição (uma P(n) para cada nN )
 Queremos provar: n≥a. P(n)

Princípio de Indução
 Prove: P(a)
 Prove: n.(P(n)  P(n+1))
 Conclua: n≥a. P(n)
princípio
de
indução
Essa é uma idéia sutil. Apenas P(a) é provado diretamnente.
O resto da prova nos dá um padrão para construir uma prova de P(1) … ou
P(1000) ou …
Provar a implicação P(n)  P(n+1)The implication is T
 Significa provar P(n+1) supondo P(n) em algum passo da prova
6
Exemplo 1
Proposição:
n
åi = n(n +1)/ 2
para n ³1
i=1
Base: Se n = 1, a soma é 1 = 1(1+1)/2.
Indução:
Hipótese Indução: 1+2+3+···+n = n(n+1)/2
(1)
Queremos provar: 1+2+3+···+n+(n+1)= (n+1)(n+2)/2 (2)
Como podemos usar (1) para obter (2) ?
Note que: 1+2+3+···+n+(n+1) = (1+2+3+···+n) + (n+1)
= n(n+1)/2 + (n+1) (de 1)
= (n+1)(n+2) /2
BCC101 - Matemática Discreta - DECOM/UFOP
7
P(0) n.P(n)P(n+1)
{Ind}
n. P(n)
Exercícios
Inducão

Prove que a soma dos n primeiros números inteiros
positivos ímpares é n2.
n 1
r
1
i
r


r 1
i 0
n

Prove que
para todo n∈N.

Prove que n! < nn para todo inteiro n>1.

Prove que n3 – n é divisível por 3, para todo n≥0.

Prove que (1+x)m > 1 + mx, para todo inteiro m≥2.
BCC101 - Matemática Discreta - DECOM/UFOP
8
Erros comuns em provas

Considere a seguinte prova de que, em
qualquer conjunto de n1 cavalos, todos os
cavalos são da mesma cor.
 Caso base (n=1): Trivial
9

 Caso indutivo: Considere um conjunto de (n+1)
cavalos: 1,2,3,…,n,(n+1). Pela hipótese de
indução, os n primeiros cavalos são todos da
mesma cor e os n últimos cavalos são todos da
mesma cor. Como o conjunto dos n primeiros e
dos n últimos cavalos se sobrepõem, os (n+1)
cavalos são necessariamente da mesma cor.
Onde está o erro nessa prova?
Colorindo regiões do plano
Um determinado número de linhas retas são
Cut t ing t he P lane
desenhadas em um papel, de maneira que o papel
seja dividido em um determinado número de
regiões. Mostre que é possível colorir cada região
de preto ou de branco, de modo que regiões
adjacentes tenham cor distinta.

BCC101 - Matemática Discreta - DECOM/UFOP
10
Colorindo regiões do plano

O que é o “tamanho” do problema?
 o número de retas no plano

Caso base (0 retas):
Trivial. Basta colorir o plano todo de uma mesma
cor

Passo indutivo:
Resolver o problema no caso do plano ser cortado
por n+1 retas, supondo que se sabe a solução
para o caso do plano ser cortado por n retas
BCC101 - Matemática Discreta - DECOM/UFOP
11
Colorindo regiões do plano

Passo indutivo:
Suponha que
mais uma reta
é traçada
 Suponha que sabemos como colorir um plano
cortado por determinado no. de retas, de modo
que regiões adjacentes tenham cores distintas
hipótese de indução
BCC101 - Matemática Discreta - DECOM/UFOP
12
Colorindo regiões do plano

Passo indutivo:

QUIZ:
 Quantas colorações distintas são possíveis?
 Qual é o número de regiões?
BCC101 - Matemática Discreta - DECOM/UFOP
13
Exemplo 2
Proposição 2. Em um polígono convexo com n
vértices, o maior número de diagonais que podem
ser traçadas é n(n−3)/2, para n ≥ 4.
polígono convexo
polígono não convexo
BCC101 - Matemática Discreta - DECOM/UFOP
14
Exemplo 2 (continuação)
Base: Se n = 4, o polígono é um quadrilátero,
que tem 2 diagonais; e n(n − 3)/2=(4)(1)/2 = 2.
Indução:
Hipótese de indução: o no. de diagonais de um
polígono de n vértices é n(n−3)/2.
(1)
Queremos provar que o no. de diagonais de
um polígono com n+1 vértices é (n+1)(n-2)/2.
(2)
Discreta - DECOM/UFOP
Como obter BCC101
(2)- Matemática
a partir
de (1)?
15
Exemplo 2 (continuação)
A resposta é “adicione mais um vértice”. Quantas
diagonais podem ser traçadas agora?
poligono com k vérices
poligono com k+1 vérices
Quando adicionamos 1 vértice, todas as diagonais do
polígono original são ainda diagonais do novo polígono,
mas há ainda outras diagonais.
BCC101 - Matemática Discreta - DECOM/UFOP
16
Exemplo 2 (continuação)
A hipótese de indução nos dá que o no. de diagonais
do polígono original é n(n-3)/2.
Novas diagonais podem ser traçadas, do vértice
extra Pk+1 a cada um dos outros vértices não
adjacentes (P1 e Pk), dando (n−1) diagonais extras e
um dos lados do poligono de n vértices passa a ser
uma diagonal do polígono de n+1 vértices.
Isso dá um total de n(n−3)/2+(n−1) diagonais. Mas,
n(n−3)/2+(n−1) = [n(n−3)+2(n−1)]/2 = (n+1)((n+1)-3)/2
Isso completa o passo indutivo.
Portanto, a proposição é true para todo n ≥ 4.
BCC101 - Matemática Discreta - DECOM/UFOP
17
Exercício

Em uma festa entre amigos, cada um
cumprimenta cada um dos demais com um
aperto de mãos. Se a festa tem n amigos,
quantos apertos de mão ocorrem? Prove o
seu resultado usando o princípio de indução.

Prove que o número máximo de regiões em
que pode ser dividido um plano cortado por
n retas é (1/2) n2+n+2
BCC101 - Matemática Discreta - DECOM/UFOP
18