7_INDUCAO_E_RECURSAO

Prévia do material em texto

1 
7) INDUÇÃO E RECURSÃO 
 
 
1. Introdução. 
2. Princípio da Indução Matemática. 
3. Prova Indutiva. Princípios da Indução Matemática. 
4. Definição Indutiva. 
5. Expressões regulares. 
6. Recursão. 
7. Propriedades. 
8. Recursão em linguagem de programação. 
 
1 – Introdução 
2 – Indução matemática 
3 – Princípios de indução finita 
4 – Definições indutivas 
5 – Recursão 
6 – Considerações algorítmicas da recursão 
7 – Relações de recorrência 
8 – Referências para o tópico 
 2 
1 – INTRODUÇÃO 
Como destacado por (LIMA, 2005), a indução matemática é uma eficiente metodologia 
para demonstrar proposições e fatos associados aos números naturais. E entender a 
indução matemática é praticamente o mesmo que entender os números naturais, visto 
que eles são especificados em termos de definições indutivas, como se verá 
oportunamente. 
 
Mais concretamente, no caso da Ciência da computação, a indução matemática é 
empregada para provar resultados relativos a uma grande variedade de objetos 
discretos como a complexidade de algoritmos, a Teoria da Computação, teoremas 
sobre grafos e árvores, inequações, entre outros tópicos de interesse direto do 
Cientista da computação. 
 
Além disso, e mais especificamente, também é necessário analisar o tempo de execução 
de um algoritmo ou o espaço ocupado na memória pelos dados, como freqüentemente 
realizado em disciplinas como Projeto e Análise da Complexidade de Algoritmos. A 
formulação decorrente duma análise do algoritmo pode recair em expressões 
denominadas equações de recorrência, cuja incógnita geralmente é uma função do 
tamanho do problema como, por exemplo, a quantidade de dados a ordenar se num 
algoritmo de ordenamento (POLLMAN, 2000). 
 
 
2– INDUÇÃO MATEMÁTICA 
Como tratado brevemente na unidade temática INTRODUÇÃO ÀS TÉCNICAS DE 
DEMONSTRAÇÃO a indução finita é aquela abordagem do método indutivo que é mais 
empregada, nas Ciências Exatas, para mostrar que, a partir de um enunciado particular 
Essas questões são por si suficientes para motivar o estudo da indução matemática e 
da recursão matemática pelo graduando em Ciência da Computação e são tópicos que 
são tratados nesta unidade temática. 
 3 
pode-se, sabendo-se a regra de inferência ou fórmula, mostrar que o resultado é sempre 
válido. 
 
Apresentou-se naquela oportunidade que apesar do princípio da indução finita ser a 
abordagem mais freqüente e mais empregada nas Ciências Exatas, na Lógica, pode-se 
definir um argumento indutivo como aquele cuja conclusão não é necessariamente 
verdadeira dada as premissas, existindo uma probabilidade (entre 0 e 1) de a conclusão 
ser verdadeira, em função da evidência ou inferência disponível. 
 
Também se mencionou que essas questões não são tratadas nestas Notas de Aulas. 
Apenas o princípio da indução finita seria abordado oportunamente, e um exemplo para 
ilustrar essa abordagem (a indução finita) é como: 
 
Exemplo 01: Prove que a soma dos n números inteiros ímpares é igual a n2, com n≥≥≥≥1. 
Solução: 
Apresentou-se, sem as pertinentes justificativas, que a idéia da prova, usando o princípio 
da indução finita, é como: 
1. Verificar por inspeção, que a fórmula é válida para o primeiro caso que é suposto ser 
válida a fórmula. Nesse exemplo é n=1 e a expressão é verdadeira, pois 1=12. 
2. Admitir que a fórmula é válida para um número n=k arbitrário de números ímpares, ou 
seja, que vale: ( )+ + + − = 21 3 ... 2k 1 k . 
3. Mostrar usando as condições anteriores que a fórmula é válida para n=k+1 números 
ímpares. E o no caso deste exemplo isso é verdadeiro, pois “adicionando o próximo 
número ímpar da seqüência aos dois lados da igualdade no item anterior” tem-se: 
( ) ( ) ( )
( )
+ + + − + + = + +
= +
2
2
1 3 ... 2k 1 2k 1 k 2k 1
k 1
 
4. Usar o princípio da indução finita para concluir que, como a proposição (fórmula) é 
verdadeira para n=1 e para um n arbitrário, então ela é sempre verdadeira, mostrando 
que a soma dos n primeiros números ímpares é sempre igual a n2. 
 
Usuario
Rectangle
 4 
Nessa seção objetiva-se discutir a indução matemática, como relevante método de 
demonstração e enfatizar a importância dos fundamentos que constituem o método de 
indução Matemática. 
 
O que é indução (http://pt.wikipedia.org/wiki/Indução)? 
• Indução em Filosofia é considerado o método de pensamento ou raciocínio com o 
qual se extraem de certos fatos conhecidos, mediante observação, alguma 
conclusão geral que não se acha rigorosamente relacionada com eles. 
• Indução pode ser considerada também a inferência conjectural que conclui, da 
regularidade de certos fatos, a existência de outros fatos ligados aos primeiros na 
experiência anterior. 
• Indução matemática é o raciocínio segundo o qual se estende uma propriedade a 
todos os termos de um conjunto. É o método por excelência do raciocínio 
matemático, lógico. 
• Este raciocínio consiste em provar que um enunciado é valido para um conjunto 
todo. Basta provar que um enunciado vale para o primeiro número do conjunto, e 
supor que por tanto valeria para qualquer n. A indução se concretiza por conseguir 
provar para n+1 genérico, assim independente do ponto de partida, o enunciado 
valeria para todo o conjunto. 
 
Considerando esses aspectos motivacionais e não sendo o escopo destas Notas de 
Aulas tratar profundamente dessa temática, um tratamento adequando pode ser visto 
em O PRINCÍPIO DA INDUÇÃO de Elon Lages Lima, (LIMA, 2005) ou em INDUÇÃO 
MATEMÁTICA, de Abramo Hefez (HEFEZ, 2007). E considerando o ponto de vista 
“conjuntista”, pode-se definir que: 
 
Definição 01 (Axioma da indução de Peano): Dada uma função s:N →→→→N, que associa a 
cada n ∈∈∈∈ N um elemento s(n) ∈∈∈∈ N, chamado o sucessor de n. Um subconjunto X ⊂⊂⊂⊂ N 
chama-se indutivo quando s(X) ⊂⊂⊂⊂ X, ou seja, quando se n ∈∈∈∈ X então s(n) ∈∈∈∈ X, ou ainda, 
quando o sucessor de qualquer elemento de X também pertence a X. 
 5 
 
3 – Princípios de indução finita 
A ação fundamental do axioma da indução na Matemática resulta do fato de que ele 
pode ser visto como um método de demonstração, chamado o Método de Indução 
Matemática, ou Princípio da Indução Finita, ou Princípio da Indução. 
 
Exemplo 02: Seja P uma propriedade que se refere aos números naturais. Um dado 
número natural pode atender ou não da propriedade P. Por exemplo, pelos axiomas de 
Peano se P é a propriedade de um número natural n ser sucessor de outro número 
natural, então 1 não atende a propriedade P, mas todos os demais números atende a P. 
 
Exemplo 03: Observe porque se deve ter cuidado não fazer generalizações apressadas 
relativamente a asserções sobre números naturais. 
a) Se n é um inteiro positivo, então p(n)=n2+n+41 é um número primo: Pode-se verificar 
por substituição direta que para n=1, n=2,...,n=39 tem-se que a expressão n2+n+41 
fornece, de fato, um número primo. Porém, para n=40 obtém-se 
402+40+41=40(40+1)+41=40.41+41=41(40+1)=41.41 que não é primo. Portanto a 
proposição é falsa. 
b) Semelhantemente, a expressão q(n)=n2–79n+1601 fornece primos para n=1,2,…,79, 
(confira!), mas q(80)=802–79.80+1601=1681 não é primo, pois é divisível por 41. 
 
É preciso ter clareza que a Indução Matemática é diferente da indução empírica das 
ciências naturais, em que é comum, após certo número de experimentos, enunciar leis 
gerais que governam o fenômeno em estudo. Essas leis são tidas como verdades, até 
prova em contrário. Na matemática, não há lugar para afirmações verdadeiras até 
A moral da história é: 
Só aceite que uma afirmação sobre os números naturais é realmente verdadeira 
para todos os naturais se issohouver de fato sido demonstrado (LIMA, 2005)! 
 6 
prova em contrário. A Prova por Indução Matemática trata de estabelecer que 
determinada sentença aberta sobre os naturais é sempre verdadeira (HEFEZ, 2007)! 
 
Definição 02 (Primeira forma da Indução Matemática ou indução fraca): Suponha que 
para cada natural n, se tenha uma propriedade P(n) que satisfaça as seguintes 
condições: 
1. P(a) é verdadeira, para a natural. 
2. Sempre que a afirmativa é verdadeira para um natural k qualquer e é verdadeira 
para o seu sucessor k+1. 
3. Então P(n) é verdadeira para todo n natural 
 
Para ver que o Princípio da Indução é verdadeiro, uma vez admitidos os axiomas de 
Peano, basta observar que dada a propriedade P cumprindo as condições estipuladas 
no enunciado do Princípio, o conjunto X dos números naturais que atendam a 
propriedade P contém o número 1 e é indutivo. Logo X = N, isto é, todo número natural 
atenda a propriedade. Veja discussões e detalhes em (LIMA, 2005). 
 
Observação 01: O Princípio da indução finita diz o seguinte (LIMA, 2005): Seja P uma 
propriedade referente a números naturais. Se a atende P (passo base) e se, além disso, 
o fato de o número natural n atende P implica que seu sucessor s(n) também atende 
(passo indutivo), decorre que todos os números naturais atendem a propriedade P. 
 
Observação 02: É importante destacar que a indução matemática é constituída de duas 
condições. 
• A primeira garante que estamos partindo de um fato verdadeiro para o primeiro 
número natural a. 
• A segunda garante que se a afirmação é verdadeira para um natural k ≥≥≥≥ a qualquer e 
implica em verdadeira para o seu sucessor, então é verdadeira para todo natural. A 
declaração “se a afirmação é verdadeira para um natural” é conhecida como 
hipótese da indução. 
 7 
 
Exemplo 04: Mostre que a soma dos n primeiros números inteiros ímpares pode ser 
expressa por n2. Ou seja, que vale a fórmula: 
( )+ + + − = ∀ ≥ ∈ℕ21 3 ... 2k 1 n , n 1 
Solução: Pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=1. E o é, pois: 
= 21 1 
 
2. Admitir, por hipótese, que a fórmula seja válida para uma quantidade n=k arbitrária 
de números naturais ímpares. Ou seja, que vale a igualdade, ∀ ≥ ∈ℕk 1 : 
( )+ + + − = 21 3 ... 2k 1 k 
 
3. Mostrar, usando a hipótese de indução, que a fórmula é válida para n=k+1 números 
ímpares. E o é, pois: 
( ) ( ) � ( )
( )
+ + + − + + = + +
= + +
= +
���������
2
2
HipInd
k
2
2
1 3 ... 2k 1 2k 1 k 2k 1
k 2k 1
k 1
 
Ou seja, para n=k+1 números ímpares, vale a fórmula: 
( ) ( ) ( )+ + + − + + − = +  
2
1 3 ... 2k 1 2 k 1 1 k 1 . 
Como a proposição (fórmula) é verdadeira para k=1 e, sendo verdadeira para n=k 
arbitrário, é também verdadeira para n=k+1. Conclui-se, pelo princípio da indução finita 
que a soma dos n primeiros números ímpares é igual a n2. Isto é, vale a fórmula: 
( )
=
− =∑
n
2
k 1
2k 1 n . 
 
Exemplo 05: Prove que >n2 n , ∀ ≥ ∈ℕn 1 . 
Solução: Pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=1. E o é, pois: 
= >12 2 1 . 
Usuario
Rectangle
Usuario
Rectangle
 8 
2. Admitir, por hipótese, que a fórmula seja válida para n=k. Ou seja, que vale a 
igualdade, ∀ ≥ ∈ℕk 1 : 
>k2 k 
3. Usando a hipótese de indução, mostrar que vale a propriedade P(k+1), isto é, 
quando n=k+1, vale + > +k 12 k 1. Para mostrar tal resultado faz-se: 
�
�
+
∀ = > ∈
= > =
= + > +
ℕ
k 1 k
HipInd
n k 1
2 2 .2 k.2 2k
k k k 1 
E, portanto, + > + ∀ ≥ ∈ℕk 12 k 1, n 1 . 
Como a proposição é verdadeira para k=1 e, sendo verdadeira para n=k arbitrário, é 
também verdadeira para n=k+1. Conclui-se, portanto, pelo princípio da indução finita que 
vale a fórmula >n2 n , ∀ ≥ ∈ℕn 1 . 
 
Exemplo 06: Prove que > +n2 2n 1 , ∀ ≥n 3 . 
Solução: Pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=3. E o é, pois: 
= > + =32 8 2.3 1 7 
 
2. Admitir, por hipótese, que a fórmula seja válida para uma quantidade n=k arbitrária. 
Ou seja, que vale a igualdade, { }∀ ∈ −ℕk 0,1,2 : 
> +k2 2k 1 
 
4. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que vale ( )+ > + + = +k 12 2 k 1 1 2k 3 . Para mostrar tal resultado faz-se: 
� ( )
( ) ( )
( )
+ = > + = +
= + + −
> +
k 1 k
HipInd
2 2 .2 2k 1 .2 4k 2
2k 3 2k 1
2k 3
 
Já que ( )− >2k 1 0 , pois ∀ ≥n 3 . Logo se tem que + > + > +k 12 4k 2 2k 3 , ou seja, + > +k 12 2k 3 , 
como se queria provar. 
Usuario
Rectangle
 9 
Como a proposição é verdadeira para k=3 e, sendo verdadeira para n=k arbitrário, é 
também verdadeira para n=k+1. Conclui-se, portanto, pelo princípio da indução finita que 
vale a fórmula > +n2 2n 1 , ∀ ≥n 3 . 
 
Exemplo 07: Mostre que 
( )( )+ +
+ + + =2 2 2
n n 1 2n 1
1 2 ... n
6
, ∀ ≥n 1 . 
Solução: Pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=1. E o é, pois: 
( )( )
=
+ +
= = =
21 1
1 1 1 2.1 1 1.2.3
1
6 6
 
 
2. Admitir, por hipótese, que a fórmula seja válida para uma quantidade n=k. Ou seja, 
que vale a igualdade, { }∀ ∈ −ℕk 0 : 
( )( )+ +
+ + + =2 2 2
k k 1 2k 1
1 2 ... k
6
 
 
3. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que vale ( )
( ) ( ) ( )( ) ( )( )( ) + + + + +  + + +   + + + + + = =22 2 2
k 1 k 1 1 2 k 1 1 k 1 k 2 2k 3
1 2 ... k k 1
6 6
. Para 
mostrar tal resultado faz-se: 
( ) ( )( ) ( )
( )( ) ( )
( ) ( ) ( )
( )
( )
( )( )( )
+ +
+ + + + + = + +
+ + + +
=
+ + + +  =
 + + + + =
 + + + =
+ + +
=
upsquarebracketleft�upsquarebracketrightHipInd
2 22 2 2
2
2
2
k k 1 2k 1
1 2 ... k k 1 k 1
6
k k 1 2k 1 6 k 1
6
k 1 k 2k 1 6 k 1
6
k 1 2k k 6k 6
6
k 1 2k 7k 6
6
k 1 k 2 2k 3
6
 
pois ( )( )+ + = + +22k 7k 6 k 2 2k 3 . 
Usuario
Rectangle
 10 
Como a proposição é verdadeira para k=1 e, sendo verdadeira para n=k arbitrário, é 
também verdadeira para n=k+1. Conclui-se, portanto, pelo princípio da indução finita que 
vale a fórmula 
( )( )+ +
+ + + =2 2 2
n n 1 2n 1
1 2 ... n
6
, ∀ ≥n 1 . 
 
Observação 03: Alguns textos tratam de modo elementar ou detalhadamente muitos 
exemplos relativos a indução. Exemplos são: 
 
 
Exemplo 08: Mostre que ≥ + ∀ ≥ ∈ℕn3 1 2n, n 1 . 
Solução: Pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=1. E o é, pois: 
≥ + =13 1 2.1 3 
 
2. Admitir, por hipótese, que a fórmula seja válida para uma quantidade n=k. Ou seja, 
que vale a igualdade: 
≥ +k3 1 2k 
Usuario
Rectangle
 11 
 
3. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que vale ( )+ ≥ + +k 13 1 2 k 1 Para mostrar tal resultado faz-se: 
� ( )
( )
+ = ≥ +
= +
> +
= + +
k 1 k
HipInd
3 3.3 3. 1 2k
3 6k
3 2k
1 2 k 1
 
Conclui-se, portanto, pelo princípio da indução finita que vale a fórmula especificada. 
 
Exemplo 09: Mostre que + += +n 2 2n 1np 11 12 , ∀ ≥n 1 , é divisível por 133. 
Solução: Para a boa resolução desse exemplo é necessário conhecer conceitos e um 
resultado clássico da Divisão de Inteiros. 
• Definição: Sejam ∈ℤa,b . Diz-se que a divide b, e denota-se por a b , se existe ∈ℤc 
tal que =b a.c . Nessa definição a divisão é de inteiros e, daí, o resto r é =r 0 . 
• Proposição: Sejam ∈ℤa,b,c,m,n tais que c a e c b , então ( )+c ma nb . 
 
Assim,pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=1. E o é, pois: 
+ += + = +
=
=
1 2 2.1 1 3 3
1p 11 12 11 12
3059
133.23
 
que é divisível por 133, pois na definição, =b a.c , b=133.23, a=133 e c=23. 
2. Admitir, por hipótese, que a fórmula seja válida para n=k. Ou seja, que a expressão: 
+ += +k 2 2k 1kp 11 12 seja divisível por 133, para 
∗= ∈ℕn k . 
 
3. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que ( ) ( )+ + + ++ = +
k 1 2 2 k 1 1
k 1p 11 12 é divisível por 133. E o é, pois: 
Usuario
Rectangle
 12 
( ) ( )
( )
( ) ( )
( )
+ + + +
+
+ +
+ +
+ +
+ + +
+ + +
= +
= +
= +
= + +
= + +
= + +
�������
k 1 2 2 k 1 1
k 1
k 3 2k 3
k 2 2k 1 2
k 2 2k 1
k 2 2k 1 2k 1
k 2 2k 1 2k 1
HipInd
p 11 12
11 12
11 .11 12 .12
11 .11 12 133 11
11 .11 12 .133 12 .11
11 11 12 12 .133
 
Assim, +k 1p é divisível por 133, pois tomando =m 11, 
+ += +k 2 2k 1a 11 12 , += 2k 1n 12 , =b 133 e 
=c 133 , então c a , pois pela hipótese de indução ( )+ ++k 2 2k 1133 11 12 e c b , pois 133 133 , por 
definição. Assim, se c a e c b pela proposição, ( )+c ma nb , isto é, +k 1133 p . 
 
Exemplo 10: Mostre que < ∀ > ∈ℕnn! n , n 1 . 
Solução: Pelo Princípio de indução finita deve-se: 
1. Verificar, por inspeção, que a fórmula é válida para k=2. E o é, pois: 
= < =22! 2 2 4 
 
2. Admitir, por hipótese, que a fórmula seja válida para uma quantidade n=k. Ou seja, 
que vale a igualdade, ∀ ≥ ∈ℕn 2 : 
< kk! k 
 
3. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que vale ( ) ( ) ++ < + k 1k 1 ! k 1 . Para mostrar tal resultado faz-se: 
( ) ( ) � ( )
( )( )
( ) +
+ = + < +
< + +
= +
def
k
HipInd
k
k 1
k 1 ! k 1 k ! k 1 k
k 1 k 1
k 1
 
Como a proposição é verdadeira para k=2 e, sendo verdadeira para n=k arbitrário, é 
também verdadeira para n=k+1. Conclui-se, portanto, pelo princípio da indução finita que 
vale a fórmula especificada. 
 
Usuario
Rectangle
 13 
Existe outra forma para a Indução Matemática, que é empregada nos casos onde a 
prova para o sucessor de k não puder ser obtida, mas puder ser obtida para algum m 
compreendido entre a e k, a ≤≤≤≤ m ≤≤≤≤ k. 
 
Definição 03 (Segunda forma do Princípio de indução ou indução completa ou forte): 
Seja a um número inteiro. Suponha que, para todo inteiro n ≥≥≥≥ a, se tenha uma 
afirmativa P(n) que satisfaça as seguintes condições: 
1. P(a) é verdadeira. 
2. P(m) verdadeira para todo natural m com a ≤≤≤≤ m ≤≤≤≤ k implica P(k+1) verdadeira. 
3. Então P(n) é verdadeira 
 
Observação 04: Igualmente a forma anterior (a fraca), essa abordagem é constituída de 
duas condições. 
• A primeira garante que estamos partindo de um fato verdadeiro para o número 
natural a. 
• A segunda garante que se a afirmação é verdadeira para um natural m com a ≤≤≤≤ m ≤≤≤≤ k 
qualquer e implica em verdadeira para o seu sucessor, então é verdadeira para todo 
natural. 
 
Teorema 01 (Primeiro Princípio de Indução Matemática – versão fraca): Seja P(n) uma 
sentença aberta sobre os números naturais N. Suponha que: 
1. P(a) é verdadeira. 
2. Qualquer que seja n ∈∈∈∈ N, sempre que P(n) é verdadeira, segue que P(n+1) é 
verdadeira. 
3. Então, P(n) é verdadeira para todo n ∈∈∈∈ N. 
Do ponto de vista lógico esse resultado é escrito como: 
( )∧∀ ⇒ + ⇒∀  P(a) k P(k) P(k 1) n,P(n) 
 
Teorema 02 (Segundo Princípio de Indução Matemática – versão forte): Seja P(n) uma 
sentença aberta sobre os números naturais N. Suponha que: 
 14 
1. P(a) é verdadeira. 
2. P(m) verdadeira para todo natural m com a ≤≤≤≤ m ≤≤≤≤ k implica P(k+1) verdadeira. 
3. Então P(n) é verdadeira para todo n ∈∈∈∈ N. 
Do ponto de vista lógico esse resultado é escrito como: 
( )∧∀ ≤ ⇒ + ⇒∀  P(a) m k P(m) P(k 1) n,P(n) 
De modo que o segundo Princípio de indução considera não apenas o resultado 
anterior, P(n=k), mas também os anteriores P(m) com m≤≤≤≤k para concluir P(n=k+1). 
 
Observação 05: Observe-se, como discutido anteriormente, que tais teoremas podem 
ser demonstrados utilizando-se da teoria dos números naturais elaborada por Peano 
(Giuseppe Peano, 1858–1932). Ou seja, a partir dos axiomas de Peano é possível 
mostrar a validade desses teoremas. 
 
Exemplo 11: Mostre que todo inteiro ∀ ≥ ∈ℕn 8 pode ser representado com soma dos 
números 3 e 5 (isto é, de 3’s e 5’s). 
Solução: 
1. Deve-se verificar, por inspeção, que essa propriedade ∀ ≥ ∈ℕn 8 é válida. E o é, pois: 
= +P(8) 3 5 
2. Pelo Primeiro Princípio de Indução o próximo passo é admitir, por hipótese, que a 
propriedade é válida para =n k . Nessa situação o próximo k é necessariamente 
8+3=11, ou seja, = + +P(11) (3 5) 3 , pois “3” é o menor dos números do enunciado. Mas 
então não se consegue provar os casos intermediários P(9) e P(10), abrindo “lacunas” 
no enunciado que assegura que para ∀ ≥ ∈ℕn 8 vale a propriedade. 
Obviamente tal enunciado pode ser falso não sendo possível provar sua veracidade. 
Acontece que o enunciado parece ser verdadeiro, como mostra uma inspeção! Como 
prova-lo? 
Note agora que usando a hipótese de indução que P(m) verdadeira para todo 
natural m com a≤≤≤≤m≤≤≤≤k do Segundo Princípio de Indução pode-se assegurar que os 
outros casos anteriores ao P(k+1), = + +P(9) 3 3 3 e = +P(10) 5 5 , vejam válidas. 
 
Usuario
Rectangle
 15 
3. Com efeito, a hipótese de indução agora é que para 8≤≤≤≤m≤≤≤≤k, P(m) é verdadeira. Isto é, 
P(m) é a sentença que resulta da soma de 3’s e 5’, e deve provar que k+1 também 
pode ser representado por somas de 3’s e 5’. Observe que k+1≥≥≥≥11, pois já se provou 
diretamente que P(m) vale para m=8, m=9 e m=10. Então como (k+1)−−−−3≥≥≥≥11−−−−3 tem-se 
k−−−−2≥≥≥≥8 e daí, pela hipótese de indução, ∀∀∀∀8≤≤≤≤m≤≤≤≤k , P(m) logo P(k−−−−2) é verdadeira. Ou 
seja, pode ser escrita como uma soma de 3’s e 5’s. Note que (k−−−−2)++++3=k++++1, que é o 
elemento seguinte a k. 
 
Exemplo 12: Mostre que ∀ ≥ ∈ℕn 2 , n é um número primo ou é um produto de números 
primos. 
Solução: Considerando a primeira forma e a segunda forma da indução finita (Teorema 
Fundamental da aritmética: Cada um dos números inteiros positivos maiores do que um, 
podem ser expressos de forma única como um produto de números primos, 
independentemente do rearranjo dos termos). 
 
USANDO A PRIMEIRA FORMA OU INDUÇÃO FRACA TEM-SE: 
1. Verificar, por inspeção, que a propriedade “todo inteiro ∀ ≥ ∈ℕn 2 é um número 
primo ou é um produto de números primos” é válida para k=2. E o é, pois: 
2 é primo, por definição. 
2. Admitir, por hipótese, que a propriedade seja válida para uma quantidade n=k. Ou 
seja, que vale a propriedade: 
k é primo ou produto de primos. 
3. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que vale que k+1 é primo ou produto de primos. Para mostrar tal resultado faz-se: 
• Se k é primo, o resultado se verifica. 
• Se k não é primo, então k é composto, ou seja, k=a.b, onde a e b são primos ou 
produtos de primos. Assim, os números a e b são tais que 1<a<k e 1<b<k, pois caso 
contrário, se 1≤≤≤≤a≤≤≤≤k e 1≤≤≤≤b≤≤≤≤k e k=a.b, então k é primo, o que é uma contradição com 
a suposição inicial de k não ser primo. Logo a<k e b<k. Isso significa que é 
Usuario
Rectangle
 16 
necessária uma hipótese indutiva que também valha para inteiros menores do que 
k, que é alcançado pela indução forte. 
 
USANDO A SEGUNDA FORMA OU INDUÇÃO FORTE TEM-SE: 
4. Verificar, por inspeção, que a propriedade “todo inteiro ∀ ≥ ∈ℕn 2 é um número 
primo ou é um produtode números primos” é válida para k=2. E o é, pois: 
2 é primo, por definição. 
5. Admitir, por hipótese, que a propriedade seja válida para uma quantidade ≤ ≤2 m k . 
Ou seja, que P(m) é verdadeira, ou seja: 
m é primo ou produto de números primos. 
6. Usando a hipótese de indução mostrar que vale a propriedade quando n=k+1, isto é, 
que vale que k+1 é primo ou produto de primos. Para mostrar tal resultado faz-se: 
• Se k+1 é primo o resultado se verifica. 
• Se k+1 não é primo, então ele é um número composto e pode ser escrito como 
k+1=a.b, com 1<a<k+1 e 1<b<k+1 ou seja 2≤≤≤≤a≤≤≤≤k e 2≤≤≤≤b≤≤≤≤k. Mas como se ≤ ≤2 m k m é 
primo ou é produto de números primos pela hipótese de indução, significa que 
P(a) e P(b) são verdadeiras. Isto é, ou a ou b são primos ou são produto de primos. 
O que mostra que é verdadeira P(k+1)=P(a.b). 
 
Observação 06: Portanto, quando desejarmos demonstrar que alguma propriedade é 
válida para qualquer inteiro positivo n, podemos tentar usar a indução matemática 
como técnica de demonstração. 
• A indução finita, apesar do nome, é uma técnica de demonstração dedutiva, isto é, 
uma forma de demonstrar uma conjectura que possivelmente foi formulada por 
um raciocínio indutivo. 
• A chave da demonstração por indução é encontrar um modo de relacionar o que se 
deseja mostrar P(k+1), com o que hipótese de indução da P(k). Assim o Princípio da 
Indução Matemática fraca é uma implicação, cuja tese é: “Uma sentença da forma 
P(n) é verdadeira para todos os inteiros n naturais”. 
 
 17 
Observação 07: Uma discussão pertinente sobre o Princípio de indução finita é como 
realizado por (HEFEZ, 2007). 
• Uma verificação descuidada pode mostrar que se usa o fato de P(n) ser verdadeira 
para deduzir que P(n+1) é verdadeira para em seguida concluir que P(n) é 
verdadeira. Isso significa que estamos usando a tese para provar o teorema? 
• A resposta é não, pois dado um número natural n, tem-se duas possibilidades: (a) 
P(n) é verdadeira ou (b) P(n) é falsa. 
• A hipótese de indução do Principio de indução finita não exige se que assuma que 
P(n) verdadeira para todo n ∈∈∈∈ N, podendo, eventualmente, ser falsa para algum 
valor de n, ou mesmo para todos os valores de n. O que a hipótese requer é que 
sempre que algum n pertença à categoria (a) então n+1 também pertença a essa 
categoria, não exigindo nada quando n pertencer à categoria (b) (HEFEZ, 2007). 
 
Observação 08: Outros textos que tratam com certos detalhes e que trazem exemplos 
de indução matemática são os de: 
 
E veja o link http://www.obmep.org.br/prog_ic_2010/apostila2010.html 
 18 
4 – DEFINIÇÕES INDUTIVAS 
Da hipótese de indução considerada nas demonstrações por indução, da propriedade P 
ser válida para o número natural n, decorre que a propriedade P também vale para s(n), 
onde s é a função “sucessor”. 
 
Observe-se, porém, que o Princípio da Indução não é apenas relevante como um 
método dedutivo de demonstração. Serve também para definir funções f:N →→→→Y que 
têm como domínio o conjunto N dos números naturais. 
 
Nessa abordagem considera-se para definir uma função f:N→→→→Y que seja dada uma regra 
bem determinada, que associe a cada elemento n ∈∈∈∈ N um único elemento y = f(n) ∈∈∈∈ Y. 
Importante nesse caso é destacar que quando o domínio da função é o conjunto N dos 
números naturais, a fim de definir uma função f:N→→→→Y não é necessário dizer, de uma só 
vez, qual é a receita que dá o valor f(n) para todo n ∈∈∈∈ N. Basta que se tenha 
conhecimento dos seguintes condições: 
(1) O valor f (1). 
(2) Uma regra que permita calcular f(s(n)) quando se conhece f(n). 
 
Essas duas condições permitem que se conheça f(n) para todo número natural n. Nessa 
situação diz-se que a função f foi definida por recorrência. 
 
Com efeito, chamando de X o conjunto dos números naturais n para os quais se pode 
determinar f(n), a condição (1) assegura que 1 ∈∈∈∈ X e a condição (2) assegura que se n∈∈∈∈X 
então s(n) ∈∈∈∈ X. Logo, pelo axioma da indução, tem-se que X = N. 
 
A partir dessas idéias desenvolve-se a n-ésima iterada nf de uma função f . Com efeito, 
pelo Princípio da definição por Indução (Teorema da definição por indução) pode-se 
especificar a n-ésima iterada nf como sendo a composição � � �f f ... f , n vezes. Deste 
modo a cada ∈ℕn pode-se associar unicamente uma função →ℕ ℕnf : tal que: 
=
def
1f f e = �
def
s(n) nf f f 
 19 
Exemplo 13: Assim, considerando-se a função sucessor, se =s(1) 2 e =s(2) 3 tem-se: 
1. 
=
=
=
�
�
s(1) 2
def
1
def
f f
f f
f f
. 
2. 
+
=
=
=
�
� �
s(2) 3
def
2
def 1)
f f
f f
f f f
. 
 
Esse resultado advém do Teorema da definição por indução, admitido que dada uma 
função →ℕ ℕnf : sabe-se associar de modo único, a cada ∈ℕn a esta função, chamada 
a n-ésima iterada de f de tal modo que =1f f e = �
def
s(n) nf f f Assim, pode-se usar a 
definição por indução para especificar as propriedades dos números naturais. 
 
Exemplo 14 (A adição e a multiplicação nos naturais): Usando as iteradas da função 
→ℕ ℕs : define-se a adição de números naturais como: 
1. Dados ∈ℕm,n sua soma + ∈ℕm n é definida por: 
+ ≡
def
nm n s (m) 
• Assim, por exemplo, a soma: 5 + 2 = s2(5) é escrito como ( )
=
���
7
s s(5) . 
2. Somar m com 1 é formar o sucessor de m enquanto que somar m com n é partir de 
m e iterar n vezes a operação de tomar o sucessor. Assim, tem-se que: 
 + ≡

 + ≡ +
def
def
m 1 s(m)
m s(n) s(m n)
 
• Assim, querendo, pode-se dispensar a notação s(n) para indicar o sucessor de n e 
usar a notação tradicional +n 1 para representar esse sucessor. Com essa notação, 
+ ≡ +
def
m s(n) s(m n) fica escrita como: 
+ + = + +m (n 1) (m n) 1 
 
 20 
Usando-se essa abordagem, mostrar-se (LIMA, 2005), que as propriedades de adição 
em ℕ são especificadas como abaixo. Porém é relevante destacar mais uma vez que 
essa apresentação decorre de uma abordagem axiomática sendo possível, no entanto, 
provar esses resultados a partir das definições básicas. Essas questões serão 
desenvolvidas na unidade temática pertinentes. 
 
Veja, como indicado, uma ampla discussão e exemplos sobre a indução matemática em 
(MORAIS FILHO, 2012) e (HEFEZ, 2012). 
 
 
 
5 – RECURSÃO 
A recursividade, em Matemática, é um processo ou metodologia empregada para se 
especificar procedimentos e funções cujos resultados futuros dependem dos resultados 
do presente e do passado, quando e se for o caso. 
 
Uma definição heurística para uma função recursiva pode ser “uma função recursiva é 
aquela definida em termos de si mesma”. Ou seja, dentro da função está presente uma 
 21 
chamada a ela própria. Essa especificação é muito comum em Áreas de pesquisas puras 
e aplicadas que utilizam programação ou, mesmo, na Ciência da Computação. 
 
Definição 04: Uma função f:N →→→→Y cujo domínio é o conjunto dos números naturais 
chama-se uma seqüência ou sucessão de elementos de Y. A notação usada para tal 
seqüência é (y1, y2,…,yn,…), onde se usa tradicionalmente yn em vez de f(n) para 
indicar o valor da função f no número n. 
 
Exemplo 15: Considere a função →ℕ ℝ*f : especificada por = +f(n) 3n 4 . Essa é uma 
seqüência numérica infinita que pode ser representada por { }⋯f(1), f(2), f(3), f(4), , ou 
especificamente como { }⋯7,11,15,19, . Ou, simbolicamente, por: 
{ } ∈ℕ*n nf 
onde nf é o termo geral. 
 
Os tipos de equações de recorrência que serão estudados nestas Notas de Aulas são 
aquelas em que as incógnitas é a sucessão f(n) , que tradicionalmente são denotadas 
por nx com ≥n 0 , e não comof(n). Nesse caso, são usualmente representadas pela 
seqüência numérica infinita { }⋯ ⋯1 2 nx ,x , ,x , , ou por { } ∈ℕn nx , onde nx é o termo geral, como 
o caso exemplificado anteriormente. 
 
Exemplo 16: A função →ℕ ℕP : que produz a sequência 20, 21, 22, 23,..., pode ser 
especificada como: 
=


 + = ∈ ℕ
P(0) 1
P(n 1) 2P(n); n
 
Pois nesse caso tem-se: 
P(0) = 1 = 20 
P(1) = 2P(0) = 2.1 = 21 
P(2) = 2P(1) = 2.2 = 22 
P(3) = 2P(2) = 2.4 = 23 
 22 
P(4) = 2P(3) = 2.8 = 24 
,..., 
 
Nesse exemplo P(0) = 1 é dito, como no caso da Indução, ser o passo base. E P(n+1) = 
2P(n) é dito ser o passo recursivo. Note que a função pode ser escrita como: 
 
Exemplo 17: Obter os primeiros valores da sequência T definida por: 
=


 = − + ≥ ∈ ℕ
T(1) 1
T(n) T(n 1) 3; n 2
 
Solução: 
Da especificação da sequência T tem-se: 
T(1) = 1 
T(2) = T(1) + 3 = 1 + 3 = 4 
T(3) = T(2) + 3 = 4 + 3 = 7 
T(4) = T(3) + 3 = 7 + 3 = 10 
T(5) = T(4) + 3 = 10 + 3 = 13 
,..., 
 
Observação 09: Em geral (mas nem sempre) métodos recursivos são especificados 
considerando-se que: 
1. O passo base de uma expressão f é especificado em zero ou um, ou seja, têm-se f(0) 
ou f(1) como passos bases. 
2. O passo recursivo de f é especificado em n+1 termos de f(n), f(n−1) ,..., f (0). 
 
Exemplo 18: A sequência F definida por: 
=

=
 = − + − > ∈ ℕ
F(1) 1
F(2) 2
F(n) F(n 1) F(n 2) ;n 2
 
é tal que: 
F(1) = 1 
 23 
F(2) = 2 
F(3) = F(2) + F(1) = 2 + 1 = 3 
F(4) = F(3) + F(2) = 3 + 2 = 5 
F(5) = F(4) + F(3) = 5 + 3 = 8 
,..., 
 
A recursão pode ser usada para definir sequências de objetos, operações sobre 
objetos, conjuntos e algoritmos. 
 
Exemplo 19 (Função Fatorial): A função fatorial pode ser definida recursivamente como: 
=

= 
 − > ∈ ℕ
1, se n 0
n!
n.(n 1)!, se n 0
 ou seja 
=


 = − >
0! 1
n! n.(n 1)!, n 0
 
Esta especificação recursiva mostra que o resultado do fatorial de n depende da 
informação de uma das etapas anteriores (n-1). Por esse motivo é designado de 
recursão com uma memória. 
 
Exemplo 20: A função fatorial, Fatorial(n), é avaliada no caso de n=4 como: 
Fatorial(4) = 4.Fatorial(3) 
= 4.3.Fatorial(2) 
= 4.3.2.Fatorial(1) 
= 4.3.2.1.Fatorial(0) 
= 4.3.2.1.1 
= 12.2.1.1 
= 24.1.1 
= 24.1 
= 24 
 
Exemplo 21 (Função Fibonacci) A função Fibonacci F (do exemplo 18) também pode ser 
definida recursivamente como: 
 24 
=

= =
 − + −
0, se n 0
F 1, se n 1
F(n 1) F(n 2),caso contrario
 ou seja 
=

=
 − + −
F(0) 0
F(1) 1
F(n 1) F(n 2), caso contrario
 
Esta especificação recursiva mostra que o resultado do Fibonacci de n depende da 
informação de duas das etapas anteriores (n-1) e (n-2). Por esse motivo é designado de 
recursão com duas memórias. Tem-se, mais geralmente, a seguinte definição. 
 
Definição 05: Chama-se de recursão qualquer expressão algébrica an cujo resultado 
presente seja função f dos resultados passados (ou precedentes) e do passo base. Tal 
expressão é definida como: 
( )− −= …n n 1 n 2 0a f a ,a , ,a 
 
No caso da função fatorial definida exemplo 19 como: 
=

= 
 − > ∈ ℕ
1, se n 0
n!
n.(n 1)!, se n 0
, pode-se 
notar que: 
 
1. A função é recursiva, já que se refere a si própria quando emprega (n-1)! 
2. O valor de n! é determinado explicitamente quando n=0 (0!=1) e, portanto, 0 é um 
valor base. 
3. O valor de n! para n ∈∈∈∈ℕ arbitrário é definido em termos de um valor menor do que n 
que está mais próximo do valor base, que é (n-1)!. 
Consequentemente a definição da função fatorial não é “circular”, estando bem 
definida. 
 
Observação 10: A função Fibonacci, denotada por F(n) tem uma história interessante. É 
um dos problemas propostos por Leonardo de Pisa, matemático da Idade Média. São 
várias as versões do enunciado do “problema da geração coelhos” que é utilizado para 
ilustrar a função de Fibonacci. 
 
 25 
Exemplo 22: Considerando que, por mês, cada par de coelhos adultos gera um novo par 
que se torna reprodutivo no segundo mês de vida, pergunta-se quantos pares de 
coelhos podem ser gerados a partir de um único par de crias ao final de um ano? 
Solução: 
Sendo F(n) o número total de pares de coelhos no mês n tem-se: 
F(1) = 1 Começamos com um par de coelhos. 
F(2) = 1 Somente no segundo mês os coelhos tornar-se-ão produtivos. 
F(3) = 1 + 1 = 2 O primeiro par gerará um novo par de coelhos. 
F(4) = 2 + 1 = 3 O primeiro par gerará outro par e o segundo par ainda não está 
produtivo 
F(5) = 3 + 2 = 5 Os dois primeiros pares geram novos pares e o terceiro par ainda não 
produz. 
 
Ao final de um ano existem 144 pares de coelhos, sendo 143 pares gerados (com 88 
pares de adultos e 55 pares de crias), mais um par de adulto, que é o par inicial. 
 
Pode-se notar que esta sucessão de F(n) continua “gerando coelhos” na quantidade 
especificada pela fórmula recursiva F(n) = F(n–1) + F(n–2), pois o número de novos 
pares de coelhos depende do número de pares de coelhos já produtivos, que são 
relativos aos dois últimos períodos, para cada nível de tempo. 
 
 26 
Do enunciado do problema observa-se que sequência é como {1, 1, 2, 3, 5, 8, 13, 21,...} e é 
conhecida como sequência de Fibonacci. Ela tem aplicações teóricas e práticas, na 
medida em que determinados padrões na natureza e de certas questões tecnologias 
parecem segui-la. 
 
Observa-se do exemplo 21 ou que, dependendo do enunciado do problema que envolve 
a sequência de Fibonacci, ela é representada como {0, 1, 1, 2, 3, 5, 8, 13, 21,...} ou como {1, 
2, 3, 5, 8, 13, 21,...}. 
 
Exemplo 23: Apresente os primeiros termos da expressão an especificada por: 
−
=

≥ ∈
 = +
ℕ
0
n n 1
a 0
;n 1
a a 1
 
Solução: De acordo com a expressão recursiva especificada tem-se: 
n an 
0 a0 = 0 
1 a1 = a0 + 1 = 0 +1 = 1 
2 a2 = a1 + 1 = 1 +1 = 2 
3 a3 = a2 + 1 = 2 +1 = 3 
4 a4 = a3 + 1 = 3 +1 = 4 
5 a5 = a4 + 1 = 4 +1 = 5 
………… ………… 
 
Exemplo 24: Avalie os primeiros termos da expressão Sn especificada por: 
−
=

≥ ∈
 = +
ℕ
0 0
n n 1 n
S t
;n 1
S S t
 
onde tn é uma sequência de termos qualquer. 
Solução: De acordo com a expressão recursiva especificada tem-se: 
n Sn 
 27 
0 S0 = t0 
1 S1 = S0 + t1 = t0 + t1 
2 S2 = S1 + t2 = t0 + t1+ t2 
3 S3 = S2 + t3 = t0 + t1+ t2+ t3 
4 S4 = S3 + t4 = t0 + t1+ t2+ t3+ t4 
5 S5 = S4 + t5 = t0 + t1+ t2+ t3+ t4+ t5 
………… ………… 
 
O exemplo 24 apresenta uma sequência formada através um somatório de termos. Os 
somatórios, devido a sua importância em diversas áreas têm uma notação especial. No 
caso do exemplo 24 designa-se a soma das parcelas (seu somatório) por: 
=
+ + + + + + + =∑
n
0 1 2 3 4 5 n j
j 0
t t t t t t ... t t 
Essas somas parciais ou essas sequências numéricas fornecem os fundamentos 
necessários às definições para séries de números, que simplesmente podem ser 
especificadas através de sequências das somas parciais, cujos termos são obtidos 
somando-se recursivamente os termos das sequências (numéricas ou de funções). 
 
 
6 – CONSIDERAÇÕES ALGORÍTMICAS DA RECURSÃO 
Das considerações precedentes pode-se dizer heuristicamente que um objeto 
matemático, um conjunto ou um algoritmo é denominado recursivo quando sua 
especificação é parcialmente feita em termos dele mesmo. Analogamente, um objeto 
matemático, um conjunto ou um algoritmo é denominado iterativo quando sua 
definição é realizada em ermos de uma estrutura de repetição. Ou seja, Um algoritmoiterativo usa estruturas de repetição (ciclos). 
 
Note, porém, que falando rigorosa e algoritmicamente a recursão não é uma função 
que chama a si própria, mas sim a função que chama ela mesma com diferentes 
 28 
argumentos pois se a estrutura de dados utilizada para a implementação for uma pilha 
alocada dinamicamente, então seus valores diferenciam cada instância da execução. 
 
E pode-se mostrar que qualquer função computável1 pode ser especificada por uma 
função recursiva. Ou seja, para todo algoritmo recursivo existe um outro 
correspondente iterativo (não recursivo), que executa a mesma tarefa. 
 
Observação 10: A recursividade (ou recursão) é encontrada em situações teóricas ou 
abstratas, mas pode estar presente em algumas situações materiais. Por exemplo, 
quando um objeto é colocado entre dois espelhos planos paralelos e frente a frente 
surge uma imagem recursiva, porque a imagem do objeto refletida num espelho passa a 
ser o objeto a ser refletido no outro espelho e, assim, sucessivamente. 
 
Veja as figuras 1(a) e 1(b), para exemplificar essa questão. 
 
 
1 Um problema é dito parcialmente solucionável ou computável se existe um algoritmo (máquina universal) que 
solucione o problema tal que pare quando a resposta é afirmativa (aceita). Entretanto, quando a resposta 
esperada for negativa, o algoritmo pode parar (rejeita) ou permanecer processando indefinidamente (loop). 
Uma função é computável se é possível construir uma Máquina de Turing (ou um formalismo equivalente) que 
compute tal função. 
 29 
Figura 1(a): Efeito droste: Fonte http://www.dignow.org/post/o-verdadeiro-efeito-
droste-1392619-13715.html. Figura 1(b): Efeito droste: http://www.flickr.com/photos/ 
johs/420412473/sizes/z/in/photostream/ 
 
Outros detalhes sobre esse efeito droste podem ser vistos nos endereços: 
• http://caraquadrada.blogspot.com/2011/02/o-verdadeiro-efeito-droste.html e em, 
• http://www.allanbrito.com/2009/07/03/tutorial-after-effects-cs4-criando-o-efeito-
droste-com-o-pixel-bender/ 
 
Uma das principais motivações para empregar um algoritmo recursivo consiste em 
diminuir sucessivamente o tamanho do problema a um de menor tamanho ou mais 
simples, até que se possa resolvê-lo de forma direta, sem recorrer a si mesmo. Quando 
isso ocorre, diz-se que o algoritmo atingiu uma condição de parada, a qual deve estar 
presente em pelo menos no algoritmo. 
 
Sem esta condição de parada o algoritmo não interrompe de chamar a si mesmo, até 
“estourar” a capacidade da pilha, o que geralmente causa o término indesejável do 
programa. Esse problema é algumas vezes designado de recursão infinita, e nesse caso 
a estrutura de dados que é utilizada para guardar as chamadas recursivas tornar-se-á 
demasiada “grande” para ser manipulada o que irá resultar num overflow. 
 
Assim, para que a condição de parada seja atingida, o algoritmo recursivo deve, a cada 
passo, diminuir a instância (ou entrada) do problema. Porém, embora algumas 
vantagens no uso de funções recursivas seja a clareza, simplicidade e objetividade do 
código gerado, algumas desvantagens inerentes dessa abordagem é que pode ser difícil 
encontrar erros de implementação e o algoritmo pode ser ineficiente do ponto de vista 
do custo (memória e desempenho) computacional. 
 
 30 
Exemplo 25: A expressão matemática para o método fatorial na forma recursiva é 
como: 
=

= 
 − >
1, se n 0
fatorial(n)
n.fatorial(n 1), se n 0
 
• E um algoritmo recursivo que implementa essa função é como: 
 
 
 
 
 
A função Fat é chamada recursivamente com argumento decrescente até chegar ao 
caso trivial (0!), cujo valor é 1. Este caso trivial é a condição de parada e encerra a 
sequência de chamadas recursivas. A sequência de chamadas é como: 
 
Como por definição iterativa, a função fatorial é especificada como n! = n. (n-1).(n-
2).…………3.2.1, com 1!=1 e 0!=1, é simples implementar um algoritmo iterativo da função 
fatorial. 
• Já um algoritmo iterativo que implementa essa função é como: 
 
 
 
 
 
 
 
função Fat(n : Natural): Natural 
início 
se n=0 então 
retorne 1 
senão 
retorne n . Fat(n-1) 
fim 
função Fat(n: Natural) : Natural 
declare 
k, x: natural 
Início 
x ← 1 
para k ← 2 até n faça 
x ← x . k 
retorne x 
fim 
 31 
Exemplo 26: A expressão matemática para o método Fibonacci na forma recursiva é 
como 
=

= =
 − + − >
0, se n 0
Fib(n) 1, se n 1
Fib(n 1) Fib(n 2), se n 1
 
 
• Um algoritmo recursivo que implementa essa função é como: 
 
 
 
 
 
 
• Já um algoritmo iterativo que implementa essa função é como: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Qual a grande diferença entre esses algoritmos? É claro que só de se olhar pode-se 
verificar que a versão recursiva é mais clara, simples e objetiva. Porém, a grande 
diferença é o custo computacional. 
Função Fib(n:natural) 
Início 
se n=0 ou n=1 então 
retorne n 
senão 
retorne Fib(n-1) + Fib(n-2) 
fim 
função Fib(n : Natural) : Natural 
declare 
k, F1, F2, F: Natural 
início 
se n=0 ou n = 1 então 
retorne n 
senão 
início 
F1 ← 0 
F2 ← 1 
para k ← 1 até n – 1 faça 
início 
F ← F1 +F2 
F1 ← F2 
F2 ← F 
fim 
retorne F 
fim 
fim 
 32 
• Na versão recursiva no caso de Fibonacci tem-se para n>1, que cada chamada causa 
2 novas chamadas de Fib, de modo que a quantidade total de chamadas cresce 
exponencialmente (prova-se através da análise do algoritmo). No diagrama de 
execução apresentado observa-se para Fib(5), são feitas 14 chamadas da função. As 
instâncias Fib(0) e Fib(2) são chamadas 3 vezes e Fib(1) é chamada 5 vezes. 
 
Diagrama de execução de Fib(5). 
Olhando e discutindo mais de perto essa questão verifica-se que para projetar um 
algoritmo eficiente, é fundamental preocupar-se com a sua complexidade 
computacional em termos de necessidades de memória e desempenho. A função Fib(n) 
que calcula o n-ésimo elemento da seqüência de Fibonacci é um exemplo notável para 
mostrar essa relevante questão da necessidade do Projeto e Análise da Complexidade 
de algoritmos. Reescrevendo o algoritmo recursivo anterior tem-se: 
 
 
 
 
 
 
 
 
 
Este algoritmo tem complexidade da O(2n). Executando-o para n = 100 e considerando-
se que cada operação requer um picosegundo (1x10-12 s) , as 2100 operações levarão 
entrada: valor de n 
saída: O n-ésimo elemento da seqüência de Fibonacci 
Função Fib(n) 
1: se n = 0 então 
2: retorne 0 
3: senão 
4: se n = 1 então 
5: retorne 1 
6: senão 
7: retorne Fib(n - 1) + Fib(n - 2) 
8: fim se 
9: fim se 
 33 
3.1013 anos = 30.000.000.000.000 anos, o que completamente inviável para qualquer 
efeito. Agora, Reescrevendo a implementação iterativa anterior tem-se: 
 
 
 
 
 
 
 
 
 
 
 
 
Já no caso da versão iterativa 
do método de Fibonacci, pode-se provar que seu custo computacional, ou seja, sua 
complexidade cresce linearmente com o tamanho do problema, isto é, pelo menos da 
O(n). 
 
 
7 – RELAÇÕES DE RECORRÊNCIA 
Pode-se perguntar quando se deve empregar expressões ou algoritmos recursivos? 
Uma resposta pode ser “para resolver problemas que”: 
1. São de natureza inerentemente recursiva. Neste caso, a solução recursiva é a mais 
natural, elegante e fácil de implementar. 
2. A solução recursiva não leva a uma excessiva repetição dos cálculos. 
3. A solução iterativa equivalente é mais complexa (um exemplo é o problema das 
Torres de Hanói). 
 
Função Fib(n) 
1: se n = 0 então 
2: retorne 03: senão 
4: se n = 1 então 
5: retorne 1 
6: senão 
7: penúltimo ← 0 
8: ultimo ← 1 
9: para i ← 2 até n faça 
10: atual ← penúltimo + ultimo 
11: penúltimo ← ultimo 
12: ultimo ← atual 
13: fim para 
14: retorne atual 
15: fim se 
16: fim se 
 34 
Definição 06: Uma função ou uma relação é dita recursivamente definida ou, ainda, ser 
uma função ou relação de recorrência se sua especificação se referir a ela própria, de 
modo a satisfazer duas condições: 
1. Devem existir certos argumentos, chamados de valores bases ou condições iniciais, 
nos quais a função não se referencie a ela mesma. 
2. Cada vez que a função se referir a si própria, o argumento da função precisa estar 
próximo a um valor base. 
Uma expressão recursiva com essas duas propriedades é dita estar bem definida. 
 
Definição 07: Uma sequência de números reais é uma função a:IN → IR definida no 
conjunto dos naturais IN = {0,1,2,3,4,...} e tomando valores no conjunto IR dos números 
reais. O valor a(n) é representado por an, para todo n ∈∈∈∈ IN, e é chamado o termo geral, 
ou n-ésimo termo da seqüência (veja a definição 04). 
 
Porém, frequentemente se, usa as notações (an) ou simplesmente an para representar a 
sequência. Usa-se ainda a notação {an} ou {a0,a1,a2,...} para indicar o conjunto de valores 
da sequência. Essa distinção deve ser feita, pois a especificação de uma sequência não 
é a mesma coisa que seu conjunto de valores. 
 
Exemplo 27: (não unicidade na representação de uma seqüência) Considere a sequência 
especificada por: 
= ∈
=  = + ∈
ℤ
ℤn
0, se n 2k k
a
1, se n 2k 1 k
 
O conjunto de valores da sequência an assim definida é {1,0,1,0,...}. Seu conjunto de valores é 
a(IN)={0,1}. Essa sequência poderia ser especificada pela expressão recursiva: 
( ) + = + − 
n 1
n
1
a 1 1
2
 
ou então por 
π = ∈ 
 
ℤ2n
n
a sen ;n
2
 
 
 35 
Exemplo 28: Considere a sequência que começa com o número 3, e cada um dos termos 
seguintes é obtido pela multiplicação por 2 do termo anterior. Isto é tem-se: {3, 6, 12, 24, 
48,…}. Essa função pode ser especificada recursivamente observando que: 
−
= =


 = ≥
0
n n 1
a 3, n 0
a 2a , n 1
 
ou, equivalentemente, 
+
= =


 = ≥
0
n 1 n
a 3, n 0
a 2a , n 0
 
Assim: 
• A expressão −=n n 1a 2a ou, equivalentemente, + =n 1 na 2a , é uma relação de recorrência ou 
função recursiva ou passo recursivo. 
• A expressão =0a 3 , que atribui um valor específico ao primeiro dos termos definidos na 
sequência de números, é dita ser a condição inicial ou o passo base. 
Note-se que a fórmula = nna 3(2 ) fornece o n-ésimo termo da sequência como função de n 
sem que seja necessário calcular qualquer termo prévio. Tal expressão é dita ser a solução 
geral da relação de recorrência. 
 
Tal termo pode ser gerado observado que do enunciado “a sequência começa com o 
número 3, e cada um dos termos seguintes é obtido pela multiplicação por 2 do termo 
anterior” tem-se: 
�
−
−
=
=
=
=
=
n n 1
n 2
0
n vezes
n
n
a 2a
2.2a
2...2 a
2 3
3.2
 
Portanto, 
• para n=0, = =00a 3(2 ) 3 , 
• para n=1, = =11a 3(2 ) 6 , 
• para n=2, = =22a 3(2 ) 12 , 
 36 
• para n=3, = =33a 3(2 ) 24 , 
etc., gerando a seqüência 
{a0, a1, a2, a3,…} = {3, 6, 12, 24,…}. 
 
Exemplo 29: Uma progressão aritmética é uma sequência da forma: 
+ + …a, a r,a 2r, 
de modo que a sequência de números inicia com o número a, designado de termo inicial ou 
primeiro termo e cada termo sucessivo é obtido a partir do termo prévio pela adição do 
número r, designado razão da diferença entre quaisquer dois termos. 
• Considere, para ilustrar, a = 3 e r = 2 então a sequência é tal que {3, 5, 7, 9, …}. Se a=1 e r=0 
então a sequência é tal que {1, 1, 1, 1,…}. 
 
Uma relação recursivamente definida ou, uma relação de recorrência para uma 
progressão aritmética pode ser obtida especificando que o primeiro termo vale a e os 
demais são obtidos pela soma dos anteriores mais a razão. Ou seja: 
+
=


 = + ≥
1
n 1 n
a a
a a r, n 1
 
E o n-ésimo termo da sequência como função de n sem que seja necessário calcular qualquer 
termo prévio. Ou seja, a solução geral da relação de recorrência da progressão aritmética 
pode ser obtida notando que: 
−
− −
− −
= +
= + + = +
=
= + −
= + −
= + −
⋮
n n 1
n 2 n 2
n (n 2)
1
a a r
(a r) r a 2r
a (n 2)r
a (n 1)r
a (n 1)r
 
Ou seja, = + −na a (n 1)r , de modo que: 
• = + − =1a a (1 1)r a , 
• = + − = +2a a (2 1)r a r , 
• = + − = +3a a (3 1)r a 2r , 
 37 
e assim sucessivamente, de modo que a seqüência { }+ + …a, a r,a 2r, pode ser escrita como: 
{ } { }+ + =… ⋯1 2 3a, a r,a 2r, a ,a ,a , 
 
Exemplo 30: Uma progressão geométrica é uma sequência da forma: 
…2a, ar,ar , 
de modo que a sequência de números inicia com o número a e cada termo sucessivo é obtido 
a partir do termo prévio pela multiplicação do número r, designado razão c0mum entre 
quaisquer dois termos. 
• Considere, para ilustrar, a = 5 e r = 2. Então a sequência é tal que {5, 10, 20, 40,…}. Se a = 1 
e r = 3 então a sequência é tal que {1, 3, 9, 27,…}. 
 
Uma relação recursivamente definida para uma progressão geométrica pode ser 
obtida especificando que o primeiro termo vale a e os demais são obtidos pelo produto 
dos anteriores pela razão. Ou seja: 
+
=


 = ≥
1
n 1 n
a a
a ra , n 1
 
E o n-ésimo termo da sequência como função de n sem que seja necessário calcular qualquer 
termo prévio. Ou seja, a solução geral da relação de recorrência da progressão aritmética pode 
ser obtida notando que: 
�
+
−
−
=
=
=
=
=
=
n 1 n
n 1
n 2
0
n vezes
n
0
n
a ra
r(ra )
rr (ra )
r...r a
a r
ar
 
Ou seja, + =
n
n 1a ar , de modo que: 
• = =01a ar a , 
• = =12a ar ar , 
• = 23a ar , 
 38 
e assim sucessivamente de modo que a seqüência …2a, ar,ar , pode ser escrita como: 
{ } { }=… ⋯2 1 2 3a, ar,ar , a ,a ,a , 
 
É possível considerar a definição 06 para expressões algébricas an cujo resultado presente 
seja função de k resultados passados. Ou seja, tem-se: 
 
Definição 08: Chama-se de recursão ou função ou relação de recorrência qualquer 
expressão algébrica an cujo resultado presente seja função f de k resultados 
precedentes e, possivelmente, de n. A expressão é especificada genericamente como: 
( )− − −= …n n 1 n 2 n ka f a ,a , ,a ,n 
 
Definição 09: Em particular uma recursão ou relação de recorrência com coeficientes 
constantes é uma relação ou função de recorrência linear da forma: 
− − −= + + + +…n 1 n 1 2 n 2 k n ka c a c a c a g(n) 
onde c1,...,ck são constantes com ck ≠≠≠≠ 0 e g(n) é uma função de n. Se g(n) = 0 a relação é 
dita ser linear e homogênea. 
 
Com esses conceitos resolvem-se certas relações recursivas de modo a obter a única 
solução para expressões do tipo an de relevante interesse teórico ou aplicado. Com 
efeito, conhecidos os valores iniciais (base) e sabendo-se ou avaliando-se valores de an-1, 
an-2,...,an-k é possível calcular an, como discutido a seguir. 
 
Definição 10: Como especificado na definição 09 uma relação de recorrência 
homogênea de segunda ordem com coeficientes constantes é escrita como: 
− −= +n n 1 n 2a ca da 
ou, equivalentemente, 
− −− − =n n 1 n 2a ca da 0 
onde c e d≠≠≠≠ 0 são constantes, n≥≥≥≥1. 
 
 39 
Observação 11: Veja que a especificação da relação de recorrência de segunda ordem 
− −= +n n 1 n 2a ca da homogênea é simplesmente um caso particular darelação de recorrência 
geral − − −= + + + +…n 1 n 1 2 n 2 k n ka c a c a c a g(n) que se reduz a − −= +n 1 n 1 2 n 2a c a c a , pois =g(n) 0 . 
Assim, tomando = =1 2c c, c d se obtém a expressão apresentada. 
 
Para resolver essas relações de recorrência homogênea de segunda ordem com 
coeficientes constantes pode-se utilizar uma metodologia consagrada na Álgebra 
Linear, que é associar um polinômio com os autovalores de uma apropriada matriz. 
Uma discussão sobre essas questões pode ser encontrada em qualquer bom livro de 
Álgebra Linear, e não será tratada nestas notas de aulas. 
 
 
Um um polinômio quadrático da forma: 
= − −2p(x) x cx d 
é designado polinômio característico, associado a uma relação de recorrência 
homogênea de segunda ordem com coeficientes constantes. As raízes de p(x) são ditas 
serem as raízes características da relação de recursividade, que são obtidas resolvendo-
se a equação característica p(x)=0. Com esses conceitos podem-se provar os seguintes 
resultados. 
 
Proposição 01: Suponha que o polinômio característico = − −2p(x) x cx d associado à 
relação de recursão − −= +n n 1 n 2a ca da ou seja, − −− − =n n 1 n 2a ca da 0 tem raízes reais e 
distintas λλλλ1 e λλλλ2. Então a solução geral da relação de recorrência é como: 
= λ + λn nn 1 1 2 2a c c
 
onde c1 e c2 são constantes arbitrárias que são unicamente determinadas pelas 
condições iniciais (ou base). 
Prova: Veja a literatura técnica indicada. 
 
Exemplo 31: Encontrar a solução geral da relação de recursão homogênea de segunda 
ordem especificada por: 
 40 
− −= +n n 1 n 2a 2a 3a 
Solução: 
1. Inicialmente determina-se o polinômio característico = − −2p(x) x cx d e suas raízes λλλλ1 
e λλλλ2. Por comparação ∼∼∼∼ com a relação de recursão − −= +n n 1 n 2a 2a 3a pode-se ver que 
c=2 e d=3, pois ( ) ( )− −− − = − − = ⇔ − = − ∧ − = −∼2 n n 1 n 2x cx d 0 a 2a 3a 0 ( c 2) ( d 3) , de modo 
que o polinômio é escrito como: 
= − −2p(x) x 2x 3 
ou, equivalentemente, como ( )( )= − +p(x) x 3 x 1 . 
 
2. As raízes de tal polinômio são obtidas quando da avaliação da equação característica, isto é, 
quando =p(x) 0 , isto é, fazendo( )( )− + =x 3 x 1 0 , obtendo as raízes λ =1 3 e λ = −2 1 . 
Como as raízes são reais e distintas, pela proposição 01 a solução geral de − −= +n n 1 n 2a 2a 3a 
é = λ + λn nn 1 1 2 2a c c . Isto é, de λ =1 3 e λ = −2 1 , como: 
( ) ( )= + −n nn 1 2a c 3 c 1 
Então para determinados valores de 1c e 2c obtém-se uma solução geral para a 
relação de recorrência − −= +n n 1 n 2a 2a 3a . Tais valores são obtidos quando da especificação 
das condições iniciais. 
 
3. Da relação − −= +n n 1 n 2a 2a 3a , é necessário especificar as condições iniciais 0a e 1a . 
Considere que =0a 1 e =1a 2 . Então, observe inicialmente que da relação de 
recorrência gera-se = + = + =2 1 0a 2a 3a 2.2 3.1 7 , = + = + =3 2 1a 2a 3a 2.7 3.2 20 , entre outros 
valores. Ou seja, se produz a sequência de números especificada por {1, 2, 7, 20,...}. 
 
4. A solução geral única é obtida com a explicitação das constantes 1c e 2c usando as 
condições iniciais como: 
• Para n=0 tem-se =0a 1 e usando expressão geral ( ) ( )= + −
n n
n 1 2a c 3 c 1 obtém-se 
( ) ( )= + −0 01 21 c 3 c 1 , ou seja, + =1 2c c 1 . 
 41 
• Para n=1 tem-se =1a 2 e pela expressão geral ( ) ( )= + −
n n
n 1 2a c 3 c 1 obtém-se 
( ) ( )= + −1 11 22 c 3 c 1 , ou seja, − =1 23c c 2 . 
Resolvendo o sistema de equações 
+ =
 − =
1 2
1 2
c c 1
3c c 2
 obtém-se =1
3c 4 e =2
1c 4 . Observe que 

+ = − = − =

3 1 3 1 9 1
1, 3 2
4 4 4 4 4 4
. Assim, a única solução da relação de recursão 
− −= +n n 1 n 2a 2a 3a com os passos bases =0a 1 e =1a 2 é dada por: 
( ) ( )
( ) ( )
( )
( )+
= + −
= + −
+ −
=
+ −
=
n n
n 1 2
n n
nn
nn 1
a c 3 c 1
3 1
3 1
4 4
3.3 1 1
4
3 1
4
 
De modo que a única solução geral do problema é como: 
( )+ + −
=
nn 1
n
3 1
a
4
 
Então, por exemplo, tem-se: 
• 
( )+ − +
= = =
01
0
3 1 3 1
a 1
4 4
. 
• 
( )+ − −
= = =
12
1
3 1 9 1
a 2
4 4
. 
• 
( )+ − +
= = =
23
2
3 1 27 1
a 7
4 4
. 
• 
( )+ − −
= = =
34
3
3 1 81 1
a 20
4 4
. 
e assim sucessivamente, fornecendo a sequência números {1, 2, 7, 20, ...} como explicitada 
anteriormente. 
 
Exemplo 32: Encontrar a solução geral da relação de recursão homogênea de segunda 
ordem especificada por (sequência de Fibonacci): 
 42 
=

=
 − + −
F(0) 0
F(1) 1
F(n 1) F(n 2), caso contrario
 
Solução: 
1. Observe inicialmente que essa expressão é escrita em notação atual como − −= +n n 1 n 2a a a 
com =0a 0 e =1a 1. Observe-se que algumas vezes a sequência de Fibonacci tem 
como passos bases =0a 1 e =1a 1 ou =0a 1 e =1a 2 , mas esses três conjuntos de 
condições iniciais produzem a mesma sequência a partir do termo 2. 
− −
=

= =
 + ≥
0
n 1
n 1 n 2
a 0
a a 1
a a , n 2
 
2. Dadas as condições iniciais =0a 0 e =1a 1 obtém-se da relação de recorrência que 
= + = + =2 1 0a a a 0 1 1 , = + = + =3 2 1a a a 1 1 2 , = + = + =4 3 2a a a 2 1 3 , etc. produzindo a 
sequência de números determinada por {0, 1, 1, 2, 3,...}. 
3. Como tal sequência é linear e homogênea de segunda ordem, ela pode ser resolvida 
com o auxílio da proposição 01. Seu polinômio característico = − −2p(x) x cx d é 
determinado explicitamente comparando com a forma geral − −= +n n 1 n 2a ca da , de 
modo que c=1 e d=1, pois ( ) ( )− −− − = − − = ⇔ − = − ∧ − = −∼2 n n 1 n 2x cx d 0 a a a 0 ( c 1) ( d 1) . 
4. Ou seja, tem-se = − −2p(x) x x 1, cujas raízes da equação característica − − =2x x 1 0 podem 
ser obtidas pela fórmula de Bhaskará: 
− ± −
λ =
2
1,2
b b 4ac
2a
 
para a equação quadrática na forma + + =2ax bx c 0 . Assim, por comparação, tem-se que 
b=-1 e c=-1, de modo que se tem: 
± − − −
λ =
± +
=
±
=
2
1,2
1 ( 1) 4.1.( 1)
2.1
1 1 4
2
1 5
2
 
 43 
5. Ou seja, tem-se 
+
λ =1
1 5
2
 e 
−
λ =2
1 5
2
, de modo que a solução geral da relação de 
recorrência é, pela proposição 01, = λ + λn nn 1 1 2 2a c c , isto é, como: 
   + −
= +   
   
n n
n 1 2
1 5 1 5
a c c
2 2
 
6. E as condições iniciais =0a 0 e =1a 1 fornecem a seguinte análise:
 
• Para n=0 tem-se =0a 0 , então usando expressão acima se obtém 
   + −
= +   
   
0 0
0 1 2
1 5 1 5
a c c
2 2
, ou seja, + =1 2c c 0 . 
• Para n=1 tem-se =1a 1 e pela expressão para na obtém-se 
   + −
= +   
   
1 1
1 1 2
1 5 1 5
a c c
2 2
, 
ou seja, 
   + −
+ =   
   
1 2
1 5 1 5
c c 1
2 2
. 
• Resolvendo o sistema de equações 
+ =

   + −
+ =   
   
1 2
1 2
c c 0
1 5 1 5
c c 1
2 2
 obtém-se =1
1
c
5
 e 
= −2
1
c
5
. Observe que a solução do sistema é obtida como: 
= −
     + − − − −
− + = +     
     
 −
= = 
 
∴ = − ∴ = − =
1 2
2 2 2
2
2 1 2
c c
1 5 1 5 1 5 1 5
c c c
2 2 2 2
2 5
c 1
2
1 1
c c c
5 5
 
• Assim a única solução da relação de recursão − −= +n n 1 n 2a a a com os passos bases =0a 0 
e =1a 1 é dada por: 
   + −
= −   
   
n n
n
1 1 5 1 1 5
a
2 25 5
 
Observe que: 
 44 
1. 
   + −
= − =   
   
0 0
0
1 1 5 1 1 5
a 0
2 25 5
. 
2. 
   + −
= − =   
   
1 1
1
1 1 5 1 1 5
a 1
2 25 5
. 
3. 
   + −
= − =   
   
2 2
2
1 1 5 1 1 5
a 12 25 5
. 
4. 
   + −
= − =   
   
3 3
3
1 1 5 1 1 5
a 2
2 25 5
. 
e assim sucessivamente, fornecendo a sequência números {0, 1, 1, 2, 3, 5, 8, 13, 21,...}. 
 
Note que o cálculo desses termos pode ser elaborado através do desenvolvimento das 
potências envolvidas. Por exemplo, no caso de 2a tem-se: 
    + −
 = −   
     
  + + − +
= −  
   
 + + − + −
=  
 
 
=  
 
=
2 2
2
1 1 5 1 5
a
2 25
1 1 2 5 5 1 2 5 5
4 45
1 1 2 5 5 1 2 5 5
45
1 4 5
45
1
 
A proposição 01 pode ser aplicada no caso de um polinômio quadrático p(x) associado com 
uma relação de recorrência homogênea de segunda ordem com coeficientes 
constantes, mas cujas raízes de p(x) são reais e distintas. Quando as raízes são reais e 
iguais tem-se o seguinte resultado. 
 
Proposição 02: Suponha que o polinômio característico = − −2p(x) x cx d associado à 
relação de recursão − −= +n n 1 n 2a ca da tem raízes reais iguais λλλλ1 = λλλλ2 = λλλλ0. Então a solução 
geral da relação de recorrência é como: 
= λ + λn nn 1 0 2 0a c c n
 
 45 
onde c1 e c2 são constantes arbitrárias que são unicamente determinadas pelas 
condições iniciais ou base. 
Prova: Veja a literatura técnica indicada. 
 
Exemplo 33: Encontrar a solução geral da relação de recursão homogênea especificada 
por: 
− −= −n n 1 n 2a 6a 9a 
Solução: 
1. Como o polinômio característico é = − +2p(x) x 6x 9 , por comparação com a equação 
recursiva, ( ) ( )− −− − = − + = ⇔ − = − ∧ − =∼2 n n 1 n 2x cx d 0 a 6a 9a 0 ( c 6) ( d 9) , e as raízes da 
equação característica − + =2x 6x 9 0 são obtidas notando que ( )− + = − =22x 6x 9 x 3 0 , 
se tem que as raízes são reais e iguais λ =0 3 . 
2. Assim, pela proposição 02 a solução geral de − −= −n n 1 n 2a 6a 9a é como: 
( ) ( )= +n nn 1 2a c 3 c n 3 
e, assim, para quaisquer valores de 1c e 2c obtém-se uma solução para a relação de 
recorrência − −= −n n 1 n 2a 6a 9a . 
3. Dadas às condições iniciais =1a 3 e =2a 27 obtém-se que = − = − =3 2 1a 6a 9a 6.27 9.3 135 , 
= − = − =3 2 1a 6a 9a 6.135 9.27 567 , etc. Ou seja, se produz a sequência de números {3, 27, 
135, 567,...}. 
4. A solução única é obtida com a explicitação das constantes 1c e 2c usando as condições 
iniciais como: 
• Para n=1 tem-se =1a 3 e então usando expressão ( ) ( )= +
n n
n 1 2a c 3 c n 3 obtém-se 
( ) ( )= +1 11 23 c 3 c 1. 3 , ou seja, + =1 23c 3c 3 . 
• Para n=2 tem-se =2a 27 e pela expressão ( ) ( )= +
n n
n 1 2a c 3 c n 3 obtém-se 
( ) ( )= +2 21 227 c 3 c 2 3 , ou seja, + =1 29c 18c 27 . 
Resolvendo o sistema de equações 
+ =
 + =
1 2
1 2
3c 3c 3
9c 18c 27
, ou seja, 
+ =
 + =
1 2
1 2
c c 1
c 2c 3
, de modo que 
se tem = −1c 1 e =2c 2 . 
 46 
5. Assim a única solução da relação de recursão − −= −n n 1 n 2a 6a 9a com os passos bases 
=1a 3 e =2a 27 é dada por: 
( ) ( )
( )( ) ( )
( ) ( )
( ) ( )
= +
= − +
= − +
= −
n n
n 1 2
n n
n n
n
a c 3 c n 3
1 3 2n 3
3 2n 3
3 2n 1
 
ou seja 
( ) ( )= −nna 3 2n 1 
De modo que, por exemplo, tem-se: 
1. ( ) ( )= − = =11a 3 2.1 1 3(1) 3 . 
2. ( ) ( )= − = =22a 3 2.2 1 9.(3) 27 . 
3. ( ) ( )= − = =33a 3 2.3 1 27.(5) 135 . 
4. ( ) ( )= − = =44a 3 2.4 1 81.7 567 . 
e assim sucessivamente, fornecendo a sequência números {3, 27, 135, 567,...}. 
 
Observe que uma solução geral é uma fórmula fechada para uma expressão definida pelo 
esquema recursivo que avalia ou calcula uma seqüência de números. 
 
Exemplo 34: Seja a expressão Sn especificada por: 
=


 = − ≥ ∈ ℕ
S(1) 2
S(2) 2S(n 1); n 2
 
Então S(1)=2 é o termo base (0 primeiro objeto) da sequência Sn. O segundo elemento 
em Sn é S(2)=2S(1)=2.2=4. O terceiro é S(3)=2S(2)=2.4=8. Fazendo essa recursividade 
sucessivamente obtém-se a sequência {2,4,8,16,...}. A solução geral ou uma fórmula 
fechada para Sn é obtida observando que: 
 47 
( )
( )
= −
= − = −
= − = −
= −
⋮
2
2 3
k
S(n) 2S(n 1)
2 2S(n 2) 2 S(n 2)
2 2S(n 3) 2 S(n 3)
2 S(n k)
 
Ou seja, após k expansões sucessivas têm-se uma expressão da forma de 
= −kS(n) 2 S(n k) . Uma expressão mais sintética para tal S(n) pode ser obtida considerando-
se que nesse caso deve-se ter que n-k=1, ou seja, k=n-1, visto que por especificação 1 é o 
primeiro elemento válido da seqüência (o primeiro argumento). Assim tem-se: 
−
−
= −
=
=
=
k
n 1
n 1
n
S(n) 2 S(n k)
2 S(1)
2 2
2
 
A expressão = nS(n) 2 é a forma fechada para a expressão recursiva apresentada. Pode-se 
provar por indução que essa expressão = nS(n) 2 , com n≥≥≥≥1 é sempre válida. Com efeito, 
considere que: 
1. Vale que = =1S(1) 2 2 , que é exatamente o valor do caso base da expressão recursiva dada, 
pois =S(1) 2 . 
2. Suponha por hipótese de indução (HI) que vele = kS(k) 2 para com n≥≥≥≥k. 
3. Então: 
+
+ =
=
=
Def
HI
k
k 1
S(k 1) 2S(k)
22
2
 
o que mostra que a expressão vale para todo para com n≥≥≥≥k+1. 
 
 
Observe-se agora que também as raízes do polinômio característico = − −2p(x) x cx d 
associado à relação de recursão − −= +n n 1 n 2a ca da podem não ter raízes reais e distintas λλλλ1 
e λλλλ2 ou não tem raízes reais iguais λλλλ1 = λλλλ2 = λλλλ0.de modo não é possível aplicar as 
proposições 01 ou 02. Como fazer? Tem-se para esses casos o seguinte resultado: 
 48 
 
Proposição 03: Suponha que o polinômio característico = − −2p(x) x cx d associado à 
relação de recursão − −= +n n 1 n 2a ca da tem raízes complexas conjugadas λλλλ1=αααα+iββββ e λλλλ2=αααα-
iββββ. Então a solução geral da relação de recorrência é como: 
= ρ θ + ρ θn nn 1 2a c cos( n) c sen( n)
 
com ρ = α +β2 2 e ( )βθ = αarctg , e onde c1 e c2 são constantes arbitrárias que são 
unicamente determinadas pelas condições iniciais (ou base). 
Prova: Veja a literatura técnica indicada. 
 
Exemplo 35: Faça os seguintes exemplos / exercícios (LIPSCHUTZ, LIPSON, 2004) 
 49 
REFERÊNCIAS PARA O TÓPICO 
ANTAR NETO, A., LAPA, N., SAMPAIO, J. L. P., CAVALLANTTE, S. L. Progressões e 
Logaritmos. Coleção Noções de Matemática. Volume 2. Editora Moderna. 1979. 257 
p. 
AZEVEDO FILHO, A. Princípios de Inferência Dedutiva e Indutiva: Noções de Lógica e 
Métodos de Prova. Editora CreateSpace Publishers. 2010. 136 p. 
CARNIELLI, W., EPSTEIN, R. L. Computabilidade, Funções Computáveis, Lógica e os 
Fundamentos da Matemática. Editora Unesp. 2005. 415 p. 
FREITAS, R. VIANA, P. Introdução aos Métodos de Prova. Notas 1, 2, 3 e 4, do Minicurso 
de Métodos de Prova. 2012. Disponível em http://www.uff.br/grupodelogica/slides/. 
GERSTING, J. Fundamentos Matemáticos para a Ciência da Computação. Rio de Janeiro. 
Editora LTC. 1995. 518 p. 
HEFEZ, A. Indução Matemática. Caderno de Iniciação Científica – OBMEP2006. 2007. 79 
p. 
HUNTER, D. J. Fundamentos da Matemática Discreta. Editora LTC. Rio de Janeiro. 2011. 
235 p. 
LIMA, E. L. O Princípio da Indução. 2005. Disponível em www.obm.org.br/export/sites/ 
default/revista_eureka/ 
LIPSCHUTZ, S., LIPSON. M. Matemática Discreta. Coleção Schaum. Editora Bookman. 
2004. 511 p. 
LOPES, L. Manual de Indução Matemática. Editora Interciência. 1999. 133 p. 
LOUREIRO, A. A. F. Métodos de Prova. Notas de Aulas (slides). 2012. Disponível em 
http://homepages.dcc.ufmg.br/~loureiro/. 
MUNIZ NETO, A. C. Tópicos de Matemática Elementar. Volume 1: Números Reais. SB<. 
Coleção do Professor de Matemática. 2012. 222 p. 
NERICI, I. G. Introdução à Lógica. São Paulo. Editora Nobel. 1985. 197 p. 
PINEDO, C. Q. Fundamentos da Matemática. GEPEM.UFT. Campus de Araguaia. 2008. 
266 p. 
POLLMAN, H. S. Equações de Recorrência. 2000. Disponível em www.obm.org.br/ 
export/sites/default/revista_eureka.