Indução e Recursão na Matemática Discreta

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Matemática Discreta
Indução e Recursão
Eric Araújo
19 de Maio de 2014
Conteúdo
Indução Matemática
Indução Forte, ou Segundo Princípio da Indução
Definições Recorrentes e Recursividade
Indução e Recursão
Indução Matemática
Suponha que exista uma escada infinita, e queremos saber como podemos alcançar
todos os degraus dessa escada. Sabemos duas coisas:
1. Podemos alcançar o primeiro degrau da escada.
2. Se pudermos alcançar um determinado degrau da escada, então poderemos
alcançar o próximo degrau.
Eric Araújo | UFLA – Departamento de Ciência da Computação 3/75
Indução e Recursão
Podemos concluir que nós podemos alcançar todos os degraus?
Eric Araújo | UFLA – Departamento de Ciência da Computação 4/75
Indução e Recursão
Sim! Por meio da indução matemática.
A indução matemática é uma técnica de demonstração que pode ser utilizada
para apresentar declarações neste formato.
• Qual é a fórmula para a soma dos primeiros n inteiros ímpares positivos?
• Observando os resultados para um n pequeno, encontra-se um resultado
n2
• É necessário provar que essa suposição é verdadeira.
• Indução matemática é uma ferramenta importante para provar assertivas
como essa.
Eric Araújo | UFLA – Departamento de Ciência da Computação 5/75
Indução e Recursão
Indução matemática é usada para provar resultados em uma grande variedade de
objetos discretos:
• Complexidade de algoritmos
• Corretude de alguns tipos de programas de computador
• Teoremas sobre grafos e árvores
• E uma grande quantidade de inequações
Eric Araújo | UFLA – Departamento de Ciência da Computação 6/75
Indução e Recursão
Indução Matemática
Em geral, a indução matemática é usada para demonstrar proposições
que afirmam que P (n) é verdadeira para todos os números inteiros
positivos n, em que P (n) é uma função proposicional.
A demonstração da indução matemática tem duas partes, um Passo
Base, em que mostramos que P (1) é verdadeira, e um Passo de
Indução, em que mostramos que para todos os números inteiros k,
se P (k) for verdadeira, então P (k + 1) é verdadeira.
Eric Araújo | UFLA – Departamento de Ciência da Computação 7/75
Indução e Recursão
PRINCÍPIO DA INDUÇÃO MATEMÁTICA: Para demonstrar
que P (n) é verdadeira para todos os números inteiros n, em que P (n)
é uma função proposicional, completamos dois passos:
PASSO BASE: Verificamos que P (1) é verdadeira.
PASSO DE INDUÇÃO: Mostramos que a proposição condicional
P (k)→ P (k+1) é verdadeira para todos os números inteiros positivos
k.
Eric Araújo | UFLA – Departamento de Ciência da Computação 8/75
Indução e Recursão
Eric Araújo | UFLA – Departamento de Ciência da Computação 9/75
Indução e Recursão
Regra de Inferência: o princípio da indução matemática pode ser
expresso pela regra de inferência:
[P (n0) ∧ ∀k(P (k)→ P (k + 1))]→ ∀nP (n)
Observação: Numa prova por indução matemática não é assumido que P (k) é
verdadeiro para todos os inteiros. É mostrado que se for assumido que P (k) é
Eric Araújo | UFLA – Departamento de Ciência da Computação 10/75
Indução e Recursão
verdadeiro, então P (k + 1) também é verdadeiro.
Eric Araújo | UFLA – Departamento de Ciência da Computação 11/75
Indução e Recursão
Exemplo 1
Mostre que se n for um número inteiro positivo, então
1 + 2 + . . .+ n = n(n+ 1)2 .
Solução: Considere P (n) como a proposição que afirma que a soma
dos primeiros n números inteiros positivos é n(n+ 1)/2. Devemos
fazer duas coisas para demonstrar que P (n) é verdadeira para n =
1, 2, 3, . . .. Ou seja, precisamos mostrar que P (1) é verdadeira e que
a proposição condicional P (k) implica que P (k+ 1) é verdadeira para
k = 1, 2, 3, . . ..
Eric Araújo | UFLA – Departamento de Ciência da Computação 12/75
Indução e Recursão
Exemplo 1 (cont.)
Passo Base
P (1) é verdadeira, pois 1 = 1(1+1)2 .
Passo de Indução
Para a hipótese indutiva, assumimos que P (k) é verdadeira para um número inteiro
positivo arbitrário k, ou seja, assumimos que
1 + 2 + 3 + . . .+ k = k(k + 1)2 .
Considerando essa hipótese, mostramos que P (k + 1) é verdadeira, ou seja, que
1 + 2 + . . .+ k + (k + 1) = (k + 1)[(k + 1) + 1]2 =
(k + 1)(k + 2)
2
Eric Araújo | UFLA – Departamento de Ciência da Computação 13/75
Indução e Recursão
também é verdadeira.
Eric Araújo | UFLA – Departamento de Ciência da Computação 14/75
Indução e Recursão
Exemplo 1 (cont.)
1 + 2 + . . .+ k + (k + 1) = k(k+1)2 + (k + 1)
= k(k+1)+2(k+1)2
= (k+1)(k+2)2 ∴
Eric Araújo | UFLA – Departamento de Ciência da Computação 15/75
Indução e Recursão
Exemplo 2
Prove que para todos inteiros positivos,
0 + 1 + 2 + . . .+ n = n(n+ 2)2
Passo Base
P (0), para n0 = 0, é verdadeira, pois 0 = 0(0+2)2 = 0.
Passo de Indução
Se a fórmula é verdadeira para n = k então deve ser verdadeira para
n = k + 1, ou seja, P (k)→ P (k + 1).
Eric Araújo | UFLA – Departamento de Ciência da Computação 16/75
Indução e Recursão
Exemplo 2 (cont.)
Supondo que a fórmula é verdadeira para n = k
P (k) : 0 + 1 + 2 + . . .+ k = k(k + 2)2 =
k2 + 2k
2
Deve-se mostrar que:
P (k+1) : 0+1+2+. . .+k+(k+1) = (k + 1)(k + 3)2 =
k2 + 4k + 3
2
Eric Araújo | UFLA – Departamento de Ciência da Computação 17/75
Indução e Recursão
Exemplo 2 (cont.)
Desenvolvendo os termos:
0 + 1 + 2 + . . .+ k + (k + 1) = k2+2k2 + (k + 1)
= k
2+2k+2(k+1)
2
= k2+4k+22
Eric Araújo | UFLA – Departamento de Ciência da Computação 18/75
Indução e Recursão
Exemplo 2 (cont.)
P (k+1) : 0+1+2+. . .+k+(k+1) = k
2 + 4k + 3
2 6=
k2 + 4k + 2
2
Portanto, a prova é falsa.
Eric Araújo | UFLA – Departamento de Ciência da Computação 19/75
Indução e Recursão
Exemplo 3
Use a indução para mostrar que
1 + 2 + 22 + . . .+ 2n = 2n+1 − 1
Solução: Considere P (n) como a proposição 1 + 2 + 22 + . . .+ 2n =
2n+1 − 1.
Eric Araújo | UFLA – Departamento de Ciência da Computação 20/75
Indução e Recursão
Exemplo 3 (cont.)
Passo Base
P (0) é verdadeira, pois 20 = 1 = 21 − 1.
Passo de Indução
Assumimos a hipótese de P (k) verdadeira,
1 + 2 + 22 + . . .+ 2k = 2k+1 − 1.
Usamos essa hipótese para mostrar que P (k+1) também é verdadeira.
1 + 2 + 22 + . . .+ 2k + 2k+1 = 2(k+1)+1 − 1 = 2k+2 − 1
Eric Araújo | UFLA – Departamento de Ciência da Computação 21/75
Indução e Recursão
Exemplo 3 (cont.)
1 + 2 + 22 + . . .+ 2k + 2k+1 = (1 + 2 + 22 + . . .+ 2k) + 2k+1
= (2k+1 − 1) + 2k+1
= 2 · 2k+1 − 1
= 2k+2 − 1 ∴
Eric Araújo | UFLA – Departamento de Ciência da Computação 22/75
Indução e Recursão
Exemplo 4
Prove que
P (n) :
n∑
i=0
ri = r
n+1 − 1
r − 1
para todos inteiros n ≥ 0 e para todos números reais r, r 6= 1.
Eric Araújo | UFLA – Departamento de Ciência da Computação 23/75
Indução e Recursão
Exemplo 4 (cont.)
Passo Base
P (0), para n0 = 0, tem-se r0 = 1 = (r0 + 1 − 1)/(r − 1) =
(r − 1)/(r − 1) = 1.
A fórmula é verdadeira para n0 = 0.
Eric Araújo | UFLA – Departamento de Ciência da Computação 24/75
Indução e Recursão
Exemplo 4 (cont.)
Passo de Indução
A hipótese indutiva assume que P (k) é verdadeira:
P (k) :
k∑
i=0
ri = r
k+1 − 1
r − 1
Deve-se mostrar que
P (k + 1) :
k+1∑
i=0
ri = r
k+2 − 1
r − 1 .
Eric Araújo | UFLA – Departamento de Ciência da Computação 25/75
Indução e Recursão
Exemplo 4 (cont.)
k+1∑
i=0
ri =
k∑
i=0
ri + rk+1
= rk+1−1
r−1 + r
k+1
= rk+1−1
r−1 +
rk+1(r−1)
r−1
= rk+1−1+rk+2−rk+1
r−1
= rk+2−1
r−1 ∴
Eric Araújo | UFLA – Departamento de Ciência da Computação 26/75
Indução e Recursão
Exemplo 5
Prove que P (n) : 22n − 1 é divisível por 3, para n ≥ 1.
Faça.
Eric Araújo | UFLA – Departamento de Ciência da Computação 27/75
Indução
e Recursão
Indução Forte, ou Segundo Princípio da Indução
A Indução Forte é outra forma de se aplicar a Indução Matemática.
Consiste em dois passos:
1. Passo Base: Provar que P(1) é V
2. Passo Indutivo: provar que P (1)∧P (2)∧ . . .∧P (k)⇒ P (k+1)
Eric Araújo | UFLA – Departamento de Ciência da Computação 28/75
Indução e Recursão
Indução Forte: Introdução
Uma vez que a hipótese indutiva pode assumir P (1), P (2), . . . , P (k)
para provar P (k + 1), a indução forte é uma técnica mais flexível do
que a indução simples.
Pode-se mostrar que qualquer uma é uma técnica válida assumindo
que a outra é válida.
É bem mais trabalhoso converter uma prova por indução forte em
uma prova por indução simples.
Eric Araújo | UFLA – Departamento de Ciência da Computação 29/75
Indução e Recursão
Note que toda prova que usa indução simples pode ser considerada uma prova
por indução forte, pois:
• a hipótese indutiva de uma prova por indução simples é parte da hipótese
indutiva de uma prova por indução forte
• ou seja, se podemos completar o passo indutivo de uma indução simples
mostrando que P (k + 1) decorre de P (k):
– P (k + 1) também decorre de todos os P (1), P (2), . . . , P (k)
– neste caso, temos garantia de que “mais do que” P (k) é V
Eric Araújo | UFLA – Departamento de Ciência da Computação 30/75
Indução e Recursão
A Indução Forte e a Escada
A indução forte também permite uma analogia com a escada infinita.
Ela diz que podemos alcançar todos os degraus se:
• pudermos alcançar o primeiro degrau
• para todo inteiro k, se pudermos alcançar todos os primeiros k degraus,
então poderemos alcançar o (k + 1)-ésimo degrau
O exemplo a seguir ilustra o uso da indução forte em um caso que não pode ser
provado facilmente utilizando indução simples.
Eric Araújo | UFLA – Departamento de Ciência da Computação 31/75
Indução e Recursão
Exemplo 1: Suponha que:
• podemos alcançar o 1o e o 2o degraus de uma escada infinita
• sabemos que, uma vez estando em um degrau, podemos alcançar
dois degraus acima
Prove que podemos alcançar qualquer degrau da escada usando:
(a) o princípio da indução matemática
(b) indução forte
Eric Araújo | UFLA – Departamento de Ciência da Computação 32/75
Indução e Recursão
Exemplo 1(a): usando indução simples
Solução:
Passo básico: vale, pois podemos alcançar o primeiro degrau
Passo indutivo (tentativa):
hipótese indutiva: podemos alcançar o k-ésimo degrau da escada. Precisamos
mostrar que, se assumirmos esta hipótese, então poderemos alcançar o (k + 1)-
ésimo degrau
Eric Araújo | UFLA – Departamento de Ciência da Computação 33/75
Indução e Recursão
Exemplo 1(a): usando indução simples
Mas não existe modo evidente de completar este passo, pois:
• não sabemos, a partir da informação dada, que podemos alcançar o degrau
(k + 1) a partir do k-ésimo
• só o que sabemos é: se podemos alcançar um degrau, então poderemos
alcançar o degrau dois níveis acima...
Eric Araújo | UFLA – Departamento de Ciência da Computação 34/75
Indução e Recursão
Exemplo 1(b): usando indução forte
Solução:
Passo básico: vale, pois podemos alcançar o primeiro degrau
Passo indutivo:
Hipótese: podemos alcançar cada um dos primeiros k degraus
Precisamos mostrar que, assumindo esta hipótese, poderemos alcançar o (k + 1)-ésimo
degrau.
Eric Araújo | UFLA – Departamento de Ciência da Computação 35/75
Indução e Recursão
Exemplo 1(b): usando indução forte
Já sabemos que podemos alcançar o segundo degrau:
• à medida em que k > 2, sempre poderemos alcançar o degrau (k + 1) a partir
do degrau (k − 1)
• pois sabemos que podemos escalar dois degraus a partir de um degrau que já
tenhamos atingido
Isto completa a prova por indução forte. ∴
Eric Araújo | UFLA – Departamento de Ciência da Computação 36/75
Indução e Recursão
Exemplo 2: Números Primos
Prove que todo inteiro positivo n > 1 pode ser escrito unicamente como
pa11 × pa22 × . . . pass ,
onde os pi são primos e p1 < p2 < . . . < ps .
Eric Araújo | UFLA – Departamento de Ciência da Computação 37/75
Indução e Recursão
Exemplo 2 (cont.): Números Primos
Passo básico:
P (2) é V , uma vez que 2 é primo.
Passo indutivo:
Vamos usar P (2), P (3), . . . , P (k) para mostrar P (k + 1):
“k + 1 pode ser escrito unicamente como pa11 × pa22 × . . . pass ,”
Eric Araújo | UFLA – Departamento de Ciência da Computação 38/75
Indução e Recursão
Exemplo 2 (cont.): Números Primos
Todo inteiro positivo n > 1 pode ser escrito unicamente como pa11 × pa22 × . . . pass ,.
Solução:
Passo indutivo: há dois casos a considerar:
(1) k + 1 é primo: então P (k + 1) é V .
Eric Araújo | UFLA – Departamento de Ciência da Computação 39/75
Indução e Recursão
Exemplo 2 (cont.): Números Primos
(2) k + 1 não é primo: então k + 1 = l.m, onde: 2 ≤ l ≤ k e 2 ≤ m ≤ k
usando P (l) e P (m), temos:
k = l ·m = qb11 × qb22 × . . .× qbtt · rc11 × rc22 × . . .× rcvv = pa11 × pa22 × . . .× pass
onde cada pi = (qj ou rk) e p1 < p2 < . . . < ps
Temos também: se qj = rk = pi, então ai = bj + ck
Caso contrário: pi = qj e ai = bj ou pi = rk e ai = ck, já que a fatoração de l e m
são únicas, a fatoração de k + 1 também o é.
Eric Araújo | UFLA – Departamento de Ciência da Computação 40/75
Indução e Recursão
Exemplo 3: Jogo de Remover peças
Considere um jogo em que dois jogadores se revezam removendo um
número qualquer que desejem de palitos de uma de duas pilhas. O
jogador que remover o último palito ganha o jogo.
Mostre que, se as duas pilhas contiverem o mesmo número de palitos
inicialmente, o segundo jogador sempre pode garantir uma vitória.
Eric Araújo | UFLA – Departamento de Ciência da Computação 41/75
Indução e Recursão
Exemplo 3 (cont.): Jogo de Remover peças
Solução: Seja n o número de palitos em cada pilha. Usaremos
indução forte para provar P (n): “o 2o pode ganhar quando houver,
inicialmente, n palitos em cada pilha”.
Passo básico:
quando n = 1, o 1o jogador só pode remover um palito de uma das
pilhas e sobra uma única pilha com um único palito...
Eric Araújo | UFLA – Departamento de Ciência da Computação 42/75
Indução e Recursão
Exemplo 3 (cont.): Jogo de Remover peças
Solução:
Passo indutivo:
Hipótese: P (j) é V , ∀j, com 1 ≤ j ≤ k
“o 2o jogador sempre pode ganhar se há inicialmente j palitos em cada pilha”
Precisamos provar que P (k + 1) (“o 2o jogador pode ganhar se o jogo começar
com (k + 1) palitos em cada pilha”) é V
Eric Araújo | UFLA – Departamento de Ciência da Computação 43/75
Indução e Recursão
Exemplo 3 (cont.): Jogo de Remover peças
Suponha que há (k + 1) palitos em cada uma das pilhas e que o 1o
jogador remove r palitos (1 ≤ r ≤ k) de uma das pilhas deixando
(k + 1− r) palitos nesta pilha
Ao remover o mesmo número da outra pilha, o 2o jogador cria a
situação onde há duas pilhas com (k + 1− r) palitos uma vez que
1 ≤ k + 1− r ≤ k, o 2o jogador pode ganhar pela hipótese indutiva.
Note que o 1o jogador sempre perde se remover todos os (k + 1)
palitos de uma das pilhas. �
Eric Araújo | UFLA – Departamento de Ciência da Computação 44/75
Indução e Recursão
Exemplo 4: Selos de postagem (Indução Fraca)
Prove que todo valor de postagem de 12 centavos ou mais pode ser
formada usando-se somente selos de 4 e de 5 centavos.
Solução: Usando indução simples:
Passo básico: 12 centavos = 3 X 4 centavos
Passo indutivo:
Hipótese: P (k) é V (“valores de k centavos podem ser formados
com selos de 4 e 5”)
Eric Araújo | UFLA – Departamento de Ciência da Computação 45/75
Indução e Recursão
Exemplo 4 (cont.): Selos de postagem (Indução Fraca)
Passo indutivo:
Suponha que pelo menos um selo de 4 foi usado para formar k: basta
substituir este selo por um de 5 para obter
k + 1 centavos.
Agora, se nenhum selo de 4 foi usado, k é formado só de 5’s:
Neste caso, foram necessários pelo menos 3 selos de 5 para formar k
(pois k ≥ 12). Daí, substituindo-se 3 selos de 5 centavos por 4 selos
de 4 centavos, pode-se formar (k + 1). �
Eric Araújo | UFLA – Departamento de Ciência da Computação 46/75
Indução e Recursão
Exemplo 4 (cont.): Selos de postagem (Indução Forte)
Solução: Usando indução forte:
Passo básico: P (12), P (13), P (14) e P (15) são V
Passo indutivo:
Hipótese: P (j) é V para 12 ≤ j ≤ k
Por esta hipótese, podemos assumir que P (k−3) é V , pois k−3 ≥ 12,
ou seja, podemos formar valores de (k−3) centavos utilizando apenas
selos de 4 e de 5.
Para formar (k + 1), só precisamos adicionar um selo de 4 aos selos
usados para formar (k − 3) centavos. �
Eric Araújo | UFLA – Departamento de Ciência da Computação 47/75
Indução e Recursão
Exemplo 5: Sequência
Considere a sequência an definida por:
an =

a0 = 1
a1 = 2
an = 4an−1 − 4an−2
Deseja-se mostrar, usando o segundo princípio da indução, que an =
2n, para qualquer n ∈ N0
Eric Araújo | UFLA – Departamento de Ciência da Computação 48/75
Indução e Recursão
Exemplo 5 (cont.): Sequência
an =

a0 = 1
a1 = 2
an = 4an−1 − 4an−2
Passo Base:
P (0) : para n = 0, tem-se a0 = 1 = 20
Eric Araújo | UFLA – Departamento de Ciência da Computação 49/75
Indução e Recursão
Exemplo 5 (cont.): Sequência
an =

a0 = 1
a1 = 2
an = 4an−1 − 4an−2
Passo Indutivo:
Assumimos que P (i) é verdadeiro, para 0 ≤ i ≤ k, ou seja, conside-
ramos que ai = 2i para 0 ≤ i ≤ k [hipótese indutiva]
Queremos mostrar que P (k + 1) é verdadeiro, ou seja, queremos
mostrar que ak+1 = 2k+1. [o que deve ser provado]
Eric Araújo | UFLA – Departamento de Ciência da Computação 50/75
Indução e Recursão
Exemplo 5 (cont.): Sequência
an =

a0 = 1
a1 = 2
an = 4an−1 − 4an−2
Prova:
ak+1 = 4ak − 4ak−1
= 4 · 2k − 4 · 2k−1
= 2k+2 − 2k+1
= 2k+1(2− 1)
= 2k+1
Eric Araújo | UFLA – Departamento de Ciência da Computação 51/75
Definições Recorrentes e
Recursividade
Indução e Recursão
Definições Recorrentes e Recursividade
Algumas vezes é difícil definir um objeto explicitamente.
Entretanto, ele pode ser mais facilmente definido em termos dele
próprio.
Esse processo é chamado de recursão.
Eric Araújo | UFLA – Departamento de Ciência da Computação 53/75
Indução e Recursão
Eric Araújo | UFLA – Departamento de Ciência da Computação 54/75
Indução e Recursão
Eric Araújo | UFLA – Departamento de Ciência da Computação 55/75
Indução e Recursão
Recursão: Introdução
Recursão pode ser usada para definir sequências, funções e conjuntos.
Exemplo:
Uma sequência com as potência de dois pode ser dada por an = 2n ,
para n = 0, 1, 2, . . ..
Entretanto, a mesma sequência pode ser definida recursivamente por
an =
{
a0 = 1
an+1 = 2an
Eric Araújo | UFLA – Departamento de Ciência da Computação 56/75
Indução e Recursão
Recursão: Introdução
São usados dois passos para definir uma função cujo domínio são os
inteiros não-negativos:
Passo Base:
Especifica o valor da função em zero
Passo Recursivo:
Especifica uma regra para encontrar o valor de um inteiro a partir de
seus valores de inteiros menores
Eric Araújo | UFLA – Departamento de Ciência da Computação 57/75
Indução e Recursão
Exemplo 1 (Recursão)
Suponha que f é definida recursivamente por:
{
f(0) = 3
f(n+ 1) = 2f(n) + 3
Encontre f(1), f(2), f(3) e f(4).
f(1) = 2f(0) + 3 = 2× 3 + 3 = 9,
f(2) = 2f(1) + 3 = 2× 9 + 3 = 21,
f(3) = 2f(2) + 3 = 2× 21 + 3 = 45,
f(4) = 2f(3) + 3 = 2× 45 + 3 = 93,
Eric Araújo | UFLA – Departamento de Ciência da Computação 58/75
Indução e Recursão
Exemplo 2 (Recursão)
Encontre uma definição recursiva para a função fatorial F (n) = n!.
Definição para o valor inicial: F (0) = 1.
Uma regra para encontrar F (n+ 1) a partir de F (n), sabendo que
(n+ 1)! é calculado por n! multiplicado por (n+ 1).
Assim, a regra é:
F (n+ 1) = (n+ 1)F (n)
Eric Araújo | UFLA – Departamento de Ciência da Computação 59/75
Indução e Recursão
Exemplo 3 (Recursão)
Encontre uma definição recursiva para
n∑
k=0
ak.
A primeira parte da definição recursiva é
0∑
k=0
ak = a0
A segunda parte da definição recursiva é
n+1∑
k=0
ak =
n∑
k=0
ak + an+1
Eric Araújo | UFLA – Departamento de Ciência da Computação 60/75
Indução e Recursão
Os números de Fibonacci
Definição:
Os números de Fibonacci, f0, f1, f2, . . . são definidos pelas equações
f0 = 0
f1 = 1
fn = fn−1 + fn−2, para n = 2, 3, 4, . . .
Eric Araújo | UFLA – Departamento de Ciência da Computação 61/75
Indução e Recursão
Exemplo 4
Mostre que quando n ≥ 3,
fn > α
n−2,
sabendo que α = (1 +
√
5)/2.
Seja P (n) a definição fn > αn−2.
Deseja-se mostrar que P (n) é verdadeira sempre que n for um inteiro
maior ou igual a 3.
Eric Araújo | UFLA – Departamento de Ciência da Computação 62/75
Indução e Recursão
Exemplo 4 (cont.)
Passo Base
α < 2 = f3
α2 = (3 +
√
5)/2 < 3 = f4
Assim, P (3) e P (4) são verdadeiros.
Passo Indutivo
Assumindo que P(j) é verdadeiro, para 3 ≤ j ≤ k, deve-se mostrar que P(k+1) é
verdadeiro.
P (j): fj > αj−2 para 3 ≤ j ≤ k. [hipótese indutiva]
P (k + 1): fk+1 > αk−1 [o que deve ser demonstrado]
Eric Araújo | UFLA – Departamento de Ciência da Computação 63/75
Indução e Recursão
Sabendo que α é a solução de x2 − x− 1 = 0, tem-se que α2 = α+ 1.
Eric Araújo | UFLA – Departamento de Ciência da Computação 64/75
Indução e Recursão
Exemplo 4 (cont.)
Assim,
αk−1 = α2 ·αk−3 = (α+ 1) ·αk−3 = α ·αk−3 +αk−3 = αk−2 +αk−3
Pela Hipótese da Indução,
fk−1 > αk−3
fk > α
k−2
Assim,
fk+1 = fk + fk−1 > αk−2 + αk−3 = αk−1 ∴
Eric Araújo | UFLA – Departamento de Ciência da Computação 65/75
Indução e Recursão
Exemplo 5: Conjuntos Definidos Recursivamente
Considere o subconjunto S de um conjunto de inteiros definido como:
Passo Base:
3 ∈ S
Passo Recursivo:
Se x ∈ S e y ∈ S então x+ y ∈ S
Eric Araújo | UFLA – Departamento de Ciência da Computação 66/75
Indução e Recursão
Exemplo 5 (cont.): Conjuntos Definidos Recursivamente
Os novos elementos encontrados em S são 3, pelo passe base, 3+3 =
6, na primeira aplicação do passo recursivo, 3 + 6 = 6 + 3 = 9 e
6 + 6 = 12, na segunda aplicação do passo recursivo, e assim por
diante.
Eric Araújo | UFLA – Departamento de Ciência da Computação 67/75
Indução e Recursão
Definição 1: Cadeias de Alfabeto
O conjunto Σ∗ de strings sobre o alfabeto Σ pode ser definido recur-
sivamente como
Passo Base
λ ∈ Σ∗ (λ é a string vazia)
Passo Recursivo
Se ω ∈ Σ∗ e x ∈ Σ então ωx ∈ Σ∗
Eric Araújo | UFLA – Departamento de Ciência da Computação 68/75
Indução e Recursão
Exemplo 1: Cadeias de Alfabeto
Considere Σ = {0, 1}, e suponha que as cadeias de strings encontradas
estão em Σ∗.
O conjunto de todas as cadeias, são λ, especificadas para pertencer
a Σ∗ no passo base, 0 e 1, formados durante a primeira aplicação
do passo recursivo, 00, 01, 10 e 11, formados durante a segunda
aplicação do passo recursivo, e assim por diante.
Eric Araújo | UFLA – Departamento de Ciência da Computação 69/75
Indução e Recursão
Definição 2: Cadeias de Alfabeto
Duas strings podem ser combinadas através do operador de concate-
nação.
Seja Σ o alfabeto e Σ∗ o conjunto de strings formados a partir dos
símbolos de Σ.
Passo Base
ω ∈ Σ∗, então ω · λ = ω (λ é a string vazia)
Passo Recursivo
Se ω1 ∈ Σ∗ e ω2 ∈ Σ∗ e x ∈ Σ então ω1 · (ω′2x) = (ω1 · ω′2)x
Eric Araújo | UFLA – Departamento de Ciência da Computação 70/75
Indução e Recursão
Exemplo 2: Comprimento de uma Cadeia
Dê uma definição
recursiva de l(ω), uma função que calcula o com-
primento ou a extensão da cadeia ω.
Solução:
A extensão de uma cadeia pode ser definida por:
Passo Base
l(λ) = 0;
Passo Recursivo
l(ω) = l(ω′x) = l(ω′) + 1, se ω ∈ Σ∗ e x ∈ Σ
Eric Araújo | UFLA – Departamento de Ciência da Computação 71/75
Indução e Recursão
Fórmulas Bem Formadas
É possível definir expressões aritméticas envolvendo números, variáveis
e operadores {+,−,×, /, ↑} (em que ↑ indica exponenciação).
Passo Base
0, 1 e x (variável) são fórmulas bem formadas (x é uma fórmula bem
formada se é um numeral ou variável)
Passo Recursivo
Se E e F são fórmulas bem formada então (E+F ), (E×F ), (E−F ),
(E/F ) e (E ↑ F ) são fórmulas bem formadas.
Eric Araújo | UFLA – Departamento de Ciência da Computação 72/75
Indução e Recursão
Fórmulas Bem Formadas (cont.)
Pelo passo base, vemos que x, y, 0 e 3 são fórmulas bem formadas.
Fórmulas bem formadas construídas a partir da aplicação do passo
recursivo uma vez incluem (x+ 3), (3 + y), (x− y), (3− 0), (x×
3), (x/y), (3 ↑ x).
Aplicando o passo recursivo duas vezes, temos fórmulas como ((x+
3) + 3) e (x− (3× y)).
Eric Araújo | UFLA – Departamento de Ciência da Computação 73/75
Indução e Recursão
Exercício
1 - Forneça uma definição recursiva do conjunto dos inteiros positivos
que são múltiplos de 5.
2 - Forneça uma definição recursiva de ωi onde ω é uma string e i é
um inteiro não negativo (Nota: aqui ωi representa a concatenação
de i cópias da string ω).
Eric Araújo | UFLA – Departamento de Ciência da Computação 74/75
Dúvidas?