jornadas elisa de jesus

U NIVERSIDADE F EDERAL DE M INAS G ERAIS
D E PA RTA M E N TO D E M AT E M ÁT I C A

Relações de Recorrência por Eliane Alves de Jesus
Elisa Fonseca Sena e Silva

Orientador: Bernardo Nunes Borges de Lima

Belo Horizonte-MG
2006

E LIANE A LVES DE J ESUS

1

E LISA F ONSECA S ENA E S ILVA

2

Relações de Recorrência
Monogra a apresentada ao Instituto Nacional de
Matemática Pura e Aplicada, IMPA, como proposta de apresentação

de

trabalho

nas

Jornadas

de

Iniciação Cientí ca. Estudo feito sob orientação de
Bernardo Nunes Borges de Lima.

Belo Horizonte-MG
2006
1

Bolsista do PET - PROGRAD (Pró-Reitoria de Graduação da UFMG)

2

Bolsista do CNPq - Brasil

Resumo

É importante saber como lidar com relações de recorrência, uma vez que são muito comuns não só na Matemática como também em Computação, na construção de algoritmos. No entanto, dada uma relação recorrente se quisermos saber seu n-ésimo termo, teremos que calcular os n − 1 anteriores, o que não é interessante na prática. A procura de uma forma fechada para a solução de tais relações é o tema desta monogra a.
Relações de recorrência estão intimamente relacionadas com somas; e algoritmos recursivos podem ser melhorados através da introdução de pisos e tetos, logo tais assuntos também serão abordados, bem como a descoberta de formas fechadas em representação binária. Dentre os problemas estudados estão
Torre de Hanói e o Problema de Josefus.

Introdução

Uma equação tem caráter recursivo quando é de nida em termos dela própria, ou seja, quando encontrar a solução de um determinado valor de n signi ca ter que calcular as soluções de todos os valores anteriores a esse n.
É importante saber como lidar com essas relações de recorrência, já que são muito comuns.

Na Matemática, por exemplo, podemos encontrar a idéia de

recursividade em algo simples como o cálculo fatorial

0!

=

1;

n!

=

n.(n − 1)!, n

> 0.

ou em assuntos mais so sticados, como a construção dos números naturais a partir dos axiomas de