BCC 101 – Matemática Discreta I
Recursão / Indução
BCC101 - Matemática Discreta - DECOM/UFOP
1
Progressão Aritmética
s(n) = 0 + 1 + 2 + 3 + … + n =
n
åi
i=0
Considere
as seguintes instâncias do
problema:
s(0) = 0
 Qual seria a solução, se n=0 ? s(1) = 0+1 = s(0) + 1
 Qual seria a solução, se n=1 ? s(2) = 0+1+2 = s(1) + 2
 Qual seria a solução, se n=2 ?
Como você escreveria a solução para o caso
geral?
s(0) = 0
base
s(n) =s(n-1) + n
recursão
BCC101 - Matemática Discreta - DECOM/UFOP
2
Progressão Aritmética
s(0) = 0
s(n) =s(n-1) + n

Podemos obter uma fórmula direta?
0 + 1 + 2 + 3 + … + (n-2) + (n-1) + n
n + (n-1) + (n-2) + (n-3) + … + 2 + 1
+ 0
--- ----- ----- ----- … -------- ---n + n + n + n + …+ n + n + n
s(n) = n(n+-1) /2
Como provar que as duas definições definem a mesma
função?
BCC101 - Matemática Discreta - DECOM/UFOP
3
Progressão Geométrica
n
s(n) =
20
+
Considere
21
+
22
+
23
+…+
2n
=
å2
i
i=0
as seguintes instâncias do
problema:
s(0) = 1
 Qual seria a solução, se n=0 ? s(1) = 1+2 = s(0) + 21
 Qual seria a solução, se n=1 ? s(2) = 1+2+4 = s(1) + 22
 Qual seria a solução, se n=2 ?
Como você escreveria a solução para o caso
geral?
s(0) = 1
base
s(n) =s(n-1) + 2n
recursão
BCC101 - Matemática Discreta - DECOM/UFOP
4
Progressão Aritmética
s(0) = 1
s(n) =s(n-1) + 2n

Podemos obter uma fórmula direta?
… cálculo …
s(n) = 2n+1 - 1
Como provar que as duas definições definem a mesma
função?
BCC101 - Matemática Discreta - DECOM/UFOP
5
Fatorial
 Fatorial: n! = 1x2x…x(n-1)xn
0!= 1
(base)
n!= (n -1)! x n (recursão)
recursão

EX: 5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2!
= 5 · 4 · 3 · 2 · 1! = 5 · 4 · 3 · 2 · 1 · 0!
=5·4·3·2·1·1
base
6
Exercício

Defina recursivamente
n
s(n) = å t(i)
s(0)= t(0)
s(n) = s(n-1) + t(n)
i=0
n
p(n) = Õ f (i)
i=1
p(0)= 1
p(n) = p(n-1) x f(n)
BCC101 - Matemática Discreta - DECOM/UFOP
7
Sequências

Sequência de potências de 2: an = 2n, n≥0
pode ser definida recursivamente como:
a0 = 1
an = 2 an-1

n>0
Sequência: 3 0 3 0 3 0 …
pode ser definida recursivamente como:
a0 = 3
a1 = 0
an = an-2 n>1
BCC101 - Matemática Discreta - DECOM/UFOP
8
Exercícios

Considere a definição recursiva:
f(0) = 1
f(n+1) = 3 f(n)
 Determine f(1), f(2), f(3), f(4)
Encontre uma fórmula direta para f(n)

Defina recursivamente as sequências:
1.an = 3n+2 n≥0
2.1 -1 1 -1 1 …
3.an = n2
BCC101 - Matemática Discreta - DECOM/UFOP
9
Travessia de Soldados
Um grupo de n soldados quer atravessar um
rio largo e fundo, mas vê apenas uma pequena
canoa, na margem onde estão, na qual estão
dois meninos. A canoa é tão pequena que nela
só cabem 2 meninos ou 1 soldado.
 É possível atravessar os n soldados para a
margem oposta, deixando, ao final, os 2 meninos
na margem onde se encontravam originalmente?
 Qual é o menor número de vezes que a canoa
deve atravessar de uma margem para a outra?
BCC101 - Matemática Discreta - DECOM/UFOP
10
Decrementar para conquistar

Considere as seguintes instâncias do
problema:
T(1) = 4 vezes
 Qual seria a solução, se n=1 T(2)
? = 4 + T(1) vezes
 Qual seria a solução, se n=2 T(3)
? = 4 + T(2) vezes
 Qual seria a solução, se n=3 ?
Como você escreveria a solução para o caso
de n soldados, supondo que você conhece a
solução para o caso de (n-1) soldados?
T(n) = 4 + T(n-1) vezes
BCC101 - Matemática Discreta - DECOM/UFOP
11
Solução recursiva
base
T(0) = 0
T(n) = 4 + T(n-1)
n>0
recursão
Podemos obter uma fórmula direta?
T(n) = 4 + T(n-1)
…
= 4 + (4 + T(n-2)) = 2x4 + T(n-2)
= 2x4 + (4 + T(n-3)) = 3x4 + T(n-3)
…
= k x 4 + T(n-k)
= n x 4 + T(0) = n x 4
BCC101 - Matemática Discreta - DECOM/UFOP
12
Exercício
Torres de Hanoi
(Edouard Lucas - 1883)
Um templo da cidade de Hanoi tem 3 torres de
diamante, em uma das quais foram empilhados n discos
de ouro, de maneira que os discos diminuem de
tamanho da base para o topo da torre. Os monges do
templo trabalham sem cessar para transferir os discos
da torre em que foram inicialmente colocados para uma
das outras duas torres --- mas nunca um disco de
maior raio pode ser colocado sobre outro de raio
menor.
Encontre uma definição recursiva para o número de
movimentos de discos que são necessários para
transferir n discos da torre A para a torre C, usando
a torre B.
13
Torres de Hanoi
mov(0) = 0
mov(n) = 2 mov(n-1) +1 n>0
Podemos obter uma fórmula direta?
T(n) = 2 T(n-1) + 1
…
= 2 (2 mov(n-2)+1) + 1 = 22 mov(n-2) + 2 + 1
= 22 (2 mov(n-3)+1) + 2 + 1 = 23 mov(n-3) + 22 + 2 + 1
…
= 2k mov(n-k) + 2k-1 +2k-2+ … + 22+21+20
= 2n mov(0) + ∑i=0..(n-1) 2i = ∑i=0..(n-1) 2i
= 2n-1
BCC101 - Matemática Discreta - DECOM/UFOP
14
Tamanho do problema

Considere um problema relativo a um tabuleiro de
xadrez com 64 quadrados.

Como esse problema pode ser generalizado?
 Uma classe de problemas com instâncias de
tamanho n; o problema dado é uma instância de
tamanho n = 64
 Uma classe de problemas em que uma instância é
um tabuleiro de tamanho n×n. O problema dado é
uma instância de tamanho n = 8
 Restringir a classe a problemas em que o
tamanho do tabuleiro é 2n. O problema dado é
uma instância de tamanho n = 3
BCC101 - Matemática Discreta - DECOM/UFOP
15
Triominós
Considere um tabuleiro com tamanho 2n x 2n
no qual exatamente um quadrado está
coberto.
um triominó de formato L é
feito de 3 quadrados:
Quantos triominós de formato L são necessários
para cobrir os quadrados restantes, sem que
triominós se sobreponham.
BCC101 - Matemática Discreta - DECOM/UFOP
16
Triominós - solução para 23 x 23
BCC101 - Matemática Discreta - DECOM/UFOP
17
Triominós

Caso base (n=0):
 O tabuleiro tem dimensão 20x20 = 1x1, isto é,
exatamente 1 quadrado, que já está coberto.
Portanto, são necessários 0 triominós para
cobrir os quadrados restantes: trio(0) = 0

Passo indutivo:
 Considere um tabuleiro de dimensões 2n+1x2n+1
 Suponha que é possível cobrir qq tabuleiro de
dimensões 2nx2n com trio(n) triominós
 Devemos mostrar como explorar essa hipótese
para obter a solução para o caso 2n+1x2n+1
BCC101 - Matemática Discreta - DECOM/UFOP
18
Triominós

Um tabuleiro 2n+1x2n+1 pode ser subdividido em 4
tabuleiros 2nx2n, traçando-se uma linha horizontal
e uma vertical que se cruzam no meio.

Em uma desses 4 tabuleiros, há um quadrado que já
está coberto. Pela nossa hipótese, os demais
quadrados desse tabuleiro podem ser cobertos
com k triominós.

Nenhum dos 3 outros tabuleiros 2nx2n tem um
quadrado coberto. Como aplicar a hipótese aos 3
outros tabuleiros?

A idéia é colocar um triominó na junção desses 3
BCC101 - Matemática Discreta - DECOM/UFOP
19
Triominós
trio(0) = 0
trio(n+1) = 4 trio(n) +1
Agora a hipótese pode ser aplicada para cobrir os
quadrados restantes de cada uma dos 3 outros
subtabuleiros. Então trio(n+1) = 4 trio(n) +1 (n>0).
BCC101 - Matemática Discreta - DECOM/UFOP
20
Triominós
trio(0) = 0
trio(n) = 4 trio(n-1) +1 se n>0
Podemos obter uma fórmula direta?
T(n) = 4 T(n-1) + 1
…
= 4 (4 T(n-2)+1) + 1 = 42 T(n-2) + 4 + 1
= 42 (4 + T(n-3)+1) + 4 + 1 = 43 T(n-3) + 42 + 4 + 1
…
= 4k T(n-k) + 4k-1 +4k-1+ … + 42+41+40
= 4n T(0) + ∑i=0..(n-1) 4i = ∑i=0..(n-1) 4i
= (4n-1)/3
21