Resolução de relações de recorrência

Uma relação de recorrência é uma equação em que cada termo de uma sequência é definido em função dos elementos anteriores.

Resolver uma relação de recorrência é encontrar uma fórmula explícita que dá o termo geral da sequência, de preferência usando funções elementares ou outras relações de recorrência mais simples.

Exemplo

Seja a sequência $S(n)$, definida por:

• Condição Básica: $S(1)=2$;
• Relação de Recorrência: $S(n)=$$2\cdot S$$(n$–$1)$, para $n\geq 2$.

Através desta sequência observamos que:

• $S(1)=2=2^{1}$
• $S(2)=2\cdot S(1)=2\cdot 2^{1}=2^{2}$
• $S(3)=2\cdot S(2)=2\cdot 2^{2}=2^{3}$

Por meio dos resultados podemos conjecturar que $S(n)=2^{n}$, o que nos dá uma equação para o cálculo direto de $S(n)$ sem utilizarmos recorrência. Esta equação é denominada de solução em forma fechada para a relação de recorrência, sujeita à condição básica $S(1)$.

Métodos

Vamos falar agora de técnicas para se resolver Relações de Recorrência.

Relações de recorrência lineares com coeficientes constantes

Ver artigo principal: Relações de recorrência lineares com coeficientes constantes

Um caso particular de solução simples é uma relação de recorrência do tipo:

$S(n)=c_{1}S(n-1)+c_{2}S(n-2)+\ldots +c_{d}S(n-d)+c(n)\,$

Esta relação é de grau $d$. Quando $c(n)=0$, a relação é homogênea.

Analogamente ao caso de equações diferenciais, a solução será uma soma em que alguns termos são da forma $Cn^{x}y^{n}\,$ (em que $y$ é uma raiz do polinômio característico e $x$ um número menor que sua multiplicidade) e uma solução da equação não-homogênea.

Método expandir, conjecturar e verificar

Uma técnica para resolver relações de recorrência é uma abordagem do tipo expandir, conjecturar e verificar, que usa repetidamente a relação de recorrência para expandir a expressão para o n-ésimo termo até poder ter uma "ideia" da forma geral. Essa técnica também conhecida como método da substituição iterativo. Logo após, esta conjectura é verificada por indução matemática.

Exemplo

Utilizando a relação de recorrência $S(n)$, definida anteriormente, primeiro devemos expandir $S(n)$, utilizando a relação recorrente, até conseguirmos identificar a forma geral. Portanto, temos:

${\begin{aligned}S(n)&=2\times S(n-1)\\&=2\times (2\times S(n-2))\\&=2^{2}\times S(n-2)\\&=2^{2}\times (2\times S(n-3))\\&=2^{3}\times S(n-3)\end{aligned}}$

Observando o padrão formado, podemos conjecturar que, após $k$ expansões, a equação terá a forma:

$S(n)=2^{k}\times S(n-k)$

Novamente, observando a expansão de $S$ em função dos elementos anteriores, podemos conjecturar que tal expansão irá parar quando $n-k=1$, ou seja, quando $k=n-1$, pois $S(n-k)=S(n-(n-1))=S(1)$, o que corresponde à condição básica da definição. Desta forma, substituindo na equação temos:

${\begin{aligned}S(n)&=2^{(n-1)}\times S(n-(n-1))\\&=2^{(n-1)}\times S(1)\\&=2^{(n-1)}\times 2\\&=2^{(n-1)+1}\\&=2^{n}\end{aligned}}$

o que corresponde à solução em forma fechada de $S(n)$.

Precisamos agora verificar a conjectura $S(n)=2^{n}$, por indução matemática. Prova-se pelo valor de $n$.

Passo básico:

$S(1)=2^{1}=2$, o que é verdade pela condição básica;

Hipótese de indução:

Suponha que $S(k)=2^{k}$seja verdade;

Passo indutivo:

Prova-se a seguir que: $S(k+1)=2^{(k+1)}$. Pela definição de $S(n)$ temos:

${\begin{aligned}S(k+1)&=2\times S((k+1)-1)\\&=2\times S(k)\\&=2\times 2^{k}\\&=2^{(k+1)}\end{aligned}}$

Portanto, provamos nossa conjectura.

Método da Fórmula de Solução Geral

Métodos para resolver relações de recorrência são semelhantes aos utilizados para resolver equações diferenciais. Tanto as relações de recorrência como as equações diferenciais são classificadas em tipos, muitos dos quais têm fórmulas conhecidas para suas soluções. Uma relação de recorrência para uma sequência $S(n)$ é dita linear se os valores anteriores de $S$ que aparecem na definição aparecem apenas na primeira potência. A relação de recorrência linear mais geral tem a forma:

$S(n)=f_{1}(n)\times S(n-1)+f_{2}(n)\times S(n-2)+\ldots +f_{k}(n)\times S(n-k)+g(n)$

Onde os coeficientes $f_{i}$ e $g$ podem ser expressões envolvendo $n$. A relação de recorrência tem coeficientes constantes se todos os $f_{i}$ forem constantes. Ela é de primeira ordem se o n-ésimo termo depende apenas do termo $n-1$. Relações de recorrência lineares de primeira ordem com coeficientes constantes têm, portanto, a forma:

$S(n)=c\times S(n-1)+g(n)$

Uma relação de recorrência é homogênea se $g(n)=0$, para todo $n$.

Para encontrar a solução em forma fechada para a equação anterior, isto é, para a relação de recorrência lineares de primeira ordem genérica com coeficientes constantes, $S(n)$, sujeita à condição básica, podemos utilizar a abordagem de expandir, conjecturar e verificar. Pela equação anterior temos:

${\begin{aligned}S(n)&=cS(n-1)+g(n)\\&=c(c\times S(n-2)+g(n-1))+g(n)\\&=c^{2}\times S(n-2)+c\times g(n-1)+g(n)\\&=c^{2}(c\times S(n-3)+g(n-2))+c\times g(n-1)+g(n)\\&=c^{3}\times S(n-3)+c^{2}\times g(n-2)+c\times g(n-1)+g(n)\\&=\ldots \end{aligned}}$

Após $k$ expansões, temos:

$S(n)=c^{k}\times S(n-k)+c^{(k-1)}\times g(n-(k-1))+\ldots +c\times g(n-1)+g(n)$

Se o primeiro termo da seqüência é conhecido, então a expansão termina quando $n-k=1$, ou ainda, $k=n-1$, ou seja,

$S(n)=c^{(n-1)}\times S(1)+c^{(n-2)}\times g(2)+\ldots +c\times g(n-1)+g(n)=c^{(n-1)}\times S(1)+c^{(n-2)}\times g(2)+\ldots +c^{1}\times g(n-1)+c^{0}\times g(n)$

Utilizando a notação de somatório temos, então:

$S(n)=c^{(n-1)}\times S(1)+\sum _{i=2}^{n}c^{(n-i)}g(i)$

Apesar desta ser uma fórmula para a solução para a equação de $S(n)$, denominada de fórmula de solução geral, ela não é uma solução fechada, pois é necessário encontrar uma expressão para o somatório.

Por exemplo, seja a definição recorrente de $S(n)$, indicada a seguir:

• Condição básica: $S(1)=2$;
• Relação de recorrência: $S(n)=2\times S(n-1)$, para $n=2$ ou $n>2$.

De acordo com a definição de $S(n)$, $c=2$ e $g(n)=0.$ Portanto, substituindo temos:

$S(n)=2^{(n-1)}\times 2+\sum _{i=2}^{n}2^{(n-i)}\times 0=2^{n}$

o que nos dá como solução a fórmula $S(n)=2^{n}$, a qual foi encontrada anteriormente pelo método de expandir, conjecturar e verificar.

Ver também

• Método de Akra–Bazzi
• Teorema mestre (análise de algoritmos)
• Relação de recorrência