Relação de recorrência

Relação de recorrência (ou passo recorrente) é uma técnica matemática que permite definir sequências, conjuntos, operações ou até mesmo algoritmos partindo de problemas particulares para problemas genéricos. Ou seja, por intermédio de uma regra pode-se calcular qualquer termo em função do(s) antecessor(es) imediato(s).

As relações de recorrência são compostas por duas partes importantes: a(s) condição(ões) inicial(is) — que deve(m) ser conhecida(s) —, e a “equação de recorrência” — que é a regra que permitirá calcular os próximos termos em função dos antecessores.

A equação de recorrência não pode definir sequências sem as condições iniciais, isto é, não é uma relação de recorrência.^[1]

• Quanto ao modelo de equação:
• Equação de Recorrência Linear: Se, e somente se, a equação de recorrência for do mesmo modelo que as funções do primeiro grau.

Exemplos:

${\displaystyle x_{n}=nx_{n-1}-3n^{2}}$

Ou

${\displaystyle x_{n}=5x_{n-2}+x_{n-3}}$

• Equação de Recorrência Não Linear: Se a equação de recorrência não for do mesmo modelo que as funções do primeiro grau.

Exemplos:

${\displaystyle x_{n}=x_{n-3}^{2}}$

Ou

${\displaystyle x_{n}=x_{n-1}!}$

• Quanto à quantidade de termos envolvidos:

• Equação de Recorrência de Primeira Ordem: Quando aparece na equação de recorrência um termo em função de seu antecessor imediato.

Exemplos:

${\displaystyle x_{n}=nx_{n-1}}$

Ou

${\displaystyle x_{n}=x_{n-1}-3n^{2}}$

• Relação de Recorrência de Segunda Ordem: Quando aparece na equação de recorrência um termo em função de seus dois antecessores imediatos.

Exemplos:

${\displaystyle x_{n}=9x_{n-2}}$

Ou

${\displaystyle x_{n}=x_{n-1}+3x_{n-2}-4}$

• Relação de Recorrência de Ordem k: Quando aparece na equação de recorrência um termo em função de seus k antecessores imediatos.

Exemplos:

${\displaystyle x_{n}=x_{n-1}+3x_{n-2}-4x_{n-k}+\cos n}$

Ou

${\displaystyle x_{n}=x_{n-k}^{k}+x_{n-k+1}^{k-1}+x_{n-k+2}^{k-2}+...+x_{n-3}^{3}+x_{n-2}^{2}+x_{n-1}}$(Esse exemplo é não linear).

• Quanto à equação:

• Relação de Recorrência Homogênea: Quando, em um dos lados da igualdade estarão todos os termos da sequência presentes e no outro lado restará o ${\displaystyle 0.}$

Exemplos:

${\displaystyle x_{n}=2x_{n-1}+x_{n-3}^{2}\Rightarrow x_{n}-2x_{n-1}-x_{n-3}^{2}=0}$

• Relação de Recorrência Não – Homogênea: Quando, em um dos lados da igualdade estarão todos os termos da sequência presentes e no outro lado restará uma ${\displaystyle g(n)\neq 0.}$

Exemplos:

${\displaystyle x_{n}=2x_{n-1}+x_{n-3}^{2}+g(n)\Rightarrow x_{n}-2x_{n-1}-x_{n-3}^{2}=g(n)}$

Ou

${\displaystyle x_{n}=2x_{n-1}+x_{n-3}^{2}+6\Rightarrow x_{n}-2x_{n-1}-x_{n-3}^{2}=6}$

Em diversos modelos matemáticos de fenômenos físicos, o tempo, que costuma ser a variável independente, varia continuamente. Assim, a variação é uma grandeza infinitesimal e as mudanças na variável dependente podem ser descritas por derivadas. Nesses casos, usamos as equações diferenciais para construir modelos matemáticos que descrevam melhor, em termos numéricos, um determinado fenômeno.

Mas há modelos onde o tempo varia discretamente, isto é, assume apenas valores inteiros. Deste modo, já não se justifica utilizar as equações diferenciais para modelar esses fenômenos, pois o conceito de derivada perde sua aplicabilidade. Nessas situações, usamos as equações de diferenças para a construção do modelo matemático.^[2]

Matematicamente,

• Equações diferenciais (envolvem derivadas, pois a distância entre os pontos está ficando cada vez menor, até ser nula. A variação é continua).

${\displaystyle {\frac {df}{dt}}=\lim _{t\rightarrow t_{0}}{\frac {f(t)-f(t_{0})}{t-t_{0}}}}$

• Equação de diferenças (a variação é discreta).

${\displaystyle {\frac {\Delta f(t)}{\Delta t}}={\frac {f(t)-f(t_{0})}{t-t_{0}}}.}$ Com ${\displaystyle (t-t_{0})\in \left\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 5,...,\pm n,...\right\}\subseteq \mathbb {Z} ^{*}}$

Logo, uma equação de diferenças é qualquer problema onde deve-se determinar uma função (desconhecida) a partir de uma relação de recorrência envolvendo o operador diferença. O termo “equação de diferenças” refere-se a um tipo específico de relação de recorrência, embora, frequentemente, seja usado como sinônimo das equações de recorrência.

Resolver uma relação de recorrência significa procurar uma forma de calcular qualquer termo dessa relação dependendo apenas do valor do ${\displaystyle n}$ e não precisando calcular todos os antecessores até o valor que se deseja descobrir.

Essa função dependendo de ${\displaystyle n}$ é chamada de forma fechada da equação de recorrência.

• Equação de Recorrência de segunda ordem homogênea

Acompanhe a demonstração de resolução da equação de recorrência de segunda ordem homogênea abaixo:

${\displaystyle {\color {MidnightBlue}a\,x_{n}=-b\,x_{n-1}-c\,x_{n-2}\Rightarrow }a\,x_{n}+b\,x_{n-1}+c\,x_{n-2}=0}$   ♠

Nesta equação, a soma de um termo com seu antecessor imediato e seu segundo antecessor imediato deve resultar em 0 (equação de recorrência de segunda ordem homogênea).

• Se ${\displaystyle b=0,}$  o termo será igual a seu segundo antecessor imediato vezes uma constante.

• Se ${\displaystyle a=0,}$  o primeiro antecessor será igual ao segundo antecessor vezes uma constante.

• Se ${\displaystyle c=0,}$  o termo será igual a seu antecessor vezes uma constante.

As funções lineares (e seus múltiplos), verificam qualquer uma dessas 3 condições. Assim, uma solução possível para esta equação de recorrência de segunda ordem homogênea seria 

${\displaystyle {y_{\left\{n\right\}}}_{1}=r\,{y_{\left\{n-1\right\}}}\,_{1},}$

${\displaystyle {y_{\left\{0\right\}}}\,_{1}=1,}$

${\displaystyle {y_{\left\{n\right\}}}_{1}\neq 0,\forall n\in \mathbb {N} .}$

Disso,

${\displaystyle {y_{\left\{1\right\}}}_{1}=r\,{y_{\left\{0\right\}}}_{1}=r\cdot 1\Rightarrow {y_{\left\{1\right\}}}_{1}=r}$

${\displaystyle {y_{\left\{2\right\}}}_{1}=r\,{y_{\left\{1\right\}}}_{1}=r\cdot (r\,{y_{\left\{0\right\}}}_{1})=r^{2}{y_{\left\{0\right\}}}_{1}=r^{2}\cdot 1\Rightarrow {y_{\left\{2\right\}}}_{1}=r^{2}}$

${\displaystyle {y_{\left\{3\right\}}}_{1}=r\,{y_{\left\{2\right\}}}_{1}=r\cdot (r^{2}{y_{\left\{0\right\}}}_{1})=r^{3}{y_{\left\{0\right\}}}_{1}=r^{3}\cdot 1\,\Rightarrow {y_{\left\{3\right\}}}_{1}=r^{3}}$

${\displaystyle ...}$

${\displaystyle {y_{\left\{n\right\}}}_{1}=r^{n}}$ Substituindo

${\displaystyle x_{n}}$${\displaystyle {y_{\left\{n\right\}}}_{1}}$

na equação♠:

${\displaystyle a{y_{\left\{n\right\}}}_{1}+b{y_{\left\{n-1\right\}}}_{1}+c{y_{\left\{n-2\right\}}}_{1}=0{\color {Violet}=}}$

${\displaystyle ar^{n}+br^{n-1}+cr^{n-2}=0}$

${\displaystyle {\frac {ar^{n}+br^{n-1}+cr^{n-2}}{r^{n-2}}}=0{\color {Violet}=}}$

${\displaystyle ar^{n-(n-2)}+br^{(n-1)-(n-2)}+cr^{(n-2)-(n-2)}=0{\color {Violet}=}}$

${\displaystyle ar^{2}+br^{1}+cr^{0}=0{\color {Violet}=}}$

${\displaystyle ar^{2}+br+c=0}$♣

Logo, calculando as raízes da equação quadrática♣

${\displaystyle \left(r'\right.}$e&${\displaystyle \left.r'\right)}$, também conhecida por equação característica da relação de recorrência, se encontrará uma solução da equação de recorrência.^[3]

• Equações de recorrência de primeira ordem homogênea

${\displaystyle {\color {MidnightBlue}a\,x_{n}=-b\,x_{n-1}\Rightarrow }a\,x_{n}+b\,x_{n-1}=0}$

A equação característica será  ${\displaystyle ar+b=0}$

• Equações de recorrência de ordem ${\displaystyle k}$ homogênea

${\displaystyle {\color {MidnightBlue}a_{0}\,x_{n}=-a_{1}\,x_{n-1}-a_{2}\,x_{n-2}-...-a_{k-1}\,x_{n-k+1}-a_{k}\,x_{n-k}\Rightarrow }a_{0}\,x_{n}+a_{1}\,x_{n-1}+a_{2}\,x_{n-2}+...+a_{k-1}\,x_{n-k+1}+a_{k}\,x_{n-k}=0}$

A equação característica será

${\displaystyle a_{0}\,r^{k}+a_{1}\,r^{k-1}+a_{2}\,r^{k-2}+...+a_{k-1}r+\,a_{k}=0}$

Como a equação característica da equação de recorrência de segunda ordem pode ter duas raízes distintas, as soluções da equação de recorrência serão  ${\displaystyle {y_{\left\{n\right\}}}_{1}={\left(r'\,\right)}^{n}}$   e   ${\displaystyle {y_{\left\{n\right\}}}_{1}={\left(r''\,\right)}^{n}.}$

Assim, ${\displaystyle y_{n}\,=\,C_{1}\,{\left(r'\,\right)}^{n}+C_{2}\,{\left(r''\,\right)}^{n}}$também é solução da equação de recorrência ♠

• Demonstração:

Como ${\displaystyle y_{n}}$ é solução de ♠ então as contantes ${\displaystyle C_{1}}$ e ${\displaystyle C_{2}}$ serão solução do sistema

${\displaystyle {\begin{cases}\ C_{1}\,{r'}+C_{2}\,{r''}=y_{2}\\C_{1}\,{\left(r'\,\right)}^{2}+C_{2}\,{\left(r'\,\right)}^{2}=y_{3}\end{cases}}}$

Ou seja, ${\displaystyle C_{1}={\frac {y_{3}-y_{2}\,{r''}}{{r'}({r'}-{r''})}}}$

${\displaystyle C_{2}={\frac {y_{2}\,{r'}-y_{3}}{{r''}({r'}-{r''})}},}$

${\displaystyle {r'}\neq {r''},}$

${\displaystyle {r'}\neq 0}$&

${\displaystyle {r''}\neq 0.}$

Logo,

${\displaystyle y_{n}=C_{1}\,{\left(r'\,\right)}^{n}+C_{2}\,{\left(r''\,\right)}^{n},\,\forall n\in \mathbb {N} .}$

Com efeito, seja  ${\displaystyle z_{n}=y_{n}-C_{1}\,{\left(r'\,\right)}^{n}-C_{2}\,{\left(r''\,\right)}^{n},\,\,\,z_{n}=0,\,\forall n\in \mathbb {N} .}$

Assim,

${\displaystyle a\,z_{n}+b\,z_{n-1}+c\,z_{n-2}=a\,\left(\,y_{n}-C_{1}\,{\left(r'\,\right)}^{n}-C_{2}\,{\left(r''\,\right)}^{n}\,\right)+b\,\left(\,y_{n-1}-C_{1}\,{\left(r'\,\right)}^{n-1}-C_{2}\,{\left(r''\,\right)}^{n-1}\,\right)+c\,\left(\,y_{n-2}-C_{1}\,{\left(r'\,\right)}^{n-2}-C_{2}\,{\left(r''\,\right)}^{n-2}\,\right)}$

${\displaystyle 0=\left(\,a\,y_{n}+b\,y_{n-1}+c\,y_{n-2}\right)-\left(a\,C_{1}\,{\left(r'\,\right)}^{n}+b\,C_{1}\,{\left(r'\,\right)}^{n-1}+c\,C_{1}\,{\left(r'\,\right)}^{n-2}\right)-\left(a\,C_{2}\,{\left(r''\,\right)}^{n}+b\,C_{2}\,{\left(r''\,\right)}^{n-1}+c\,C_{2}\,{\left(r''\,\right)}^{n-2}\right)}$

${\displaystyle 0=\left(\,a\,y_{n}+b\,y_{n-1}+c\,y_{n-2}\right)-C_{1}\,\left(a\,{\left(r'\,\right)}^{n}+b\,{\left(r'\,\right)}^{n-1}+c\,{\left(r'\,\right)}^{n-2}\right)-C_{2}\,\left(a\,{\left(r''\,\right)}^{n}+b\,{\left(r''\,\right)}^{n-1}+c\,{\left(r''\,\right)}^{n-2}\right)}$<

O primeiro parênteses é igual a zero porque supomos que ${\displaystyle y_{n}}$ é solução de& ♠; os dois últimos parênteses são iguais a zero porque ${\displaystyle {r'}}$ e ;${\displaystyle {r''}}$ ;são raízes de ♣.

Então ${\displaystyle a\,z_{n}+b\,z_{n-1}+c\,z_{n-2}=0.}$

Além disso, como ${\displaystyle C_{1}\,{r'}+C_{2}\,{r''}=y_{2}}$ e ${\displaystyle C_{1}\,{\left(r'\,\right)}^{2}+C_{2}\,{\left(r'\,\right)}^{2}=y_{3},}$ ${\displaystyle z_{1}=z_{2}=0.}$

Mas, se ${\displaystyle a\,z_{n}+b\,z_{n-1}+c\,z_{n-2}=0}$;e${\displaystyle z_{1}=z_{2}=0}$ ${\displaystyle z_{n}=0,\,\forall n\in \mathbb {N} ,}$ CQD.

Portanto a forma fechada para a equação de recorrência ${\displaystyle a\,x_{n}+b\,x_{n-1}+c\,x_{n-2}=0,}$ onde a equação característica tem raízes distintas, é:

${\displaystyle y_{n}\,=\,C_{1}\,{\left(r'\,\right)}^{n}+C_{2}\,{\left(r''\,\right)}^{n}}$

Para o caso das raízes serem iguais podemos nos basear na resolução das equações diferenciais. Observe que as equações de diferença também geram equações de recorrência.^{[carece de fontes?]}

${\displaystyle a\,\Delta ^{2}\,(x_{n})+b\,\Delta (x_{n})+c\,x_{n}=a\,p_{n}+b\,p_{n-1}+c\,p_{n-2}=0}$

Assim, considerando que a variação de  ${\displaystyle n}$  seja contínua, o método para resolver equações diferenciais de segunda ordem homogênea pode ser aplicado.

${\displaystyle ay^{''}+by^{'}+cy=0}$ ♦ ${\displaystyle y=f(t)}$ e ${\displaystyle n=t,}$ tem como equação característica:

${\displaystyle az^{2}+bz+c=0}$

Sendo  ${\displaystyle z_{1}=z_{2}}$  raízes da equação característica, uma das soluções da equação diferencial  ♦  será  ${\displaystyle y_{1}=e^{\frac {-bt}{2a}}.}$

Qualquer múltiplo dessa solução será solução da equação diferencial ♦. Então, vamos supor que ${\displaystyle y_{1}=v(t)\,e^{\frac {-bt}{2a}}}$  também seja solução.

Assim,

${\displaystyle y^{'}=v^{'}(t)\,e^{\frac {-bt}{2a}}-{\frac {b}{2a}}\,v(t)\,e^{\frac {-bt}{2a}}}$

${\displaystyle y^{''}=v^{''}(t)\,e^{\frac {-bt}{2a}}-{\frac {b}{2a}}\,v^{'}(t)\,e^{\frac {-bt}{2a}}-{\frac {b}{2a}}\,v^{'}(t)\,e^{\frac {-bt}{2a}}+{\frac {b^{2}}{4a^{2}}}\,v(t)\,e^{\frac {-bt}{2a}}=v^{''}(t)\,e^{\frac {-bt}{2a}}-{\frac {b}{a}}\,v^{'}(t)\,e^{\frac {-bt}{2a}}+{\frac {b^{2}}{4a^{2}}}\,v(t)\,e^{\frac {-bt}{2a}}}$

Substituindo na equação ♦

${\displaystyle a\left(v^{''}(t)\,e^{\frac {-bt}{2a}}-{\frac {b}{a}}\,v^{'}(t)\,e^{\frac {-bt}{2a}}+{\frac {b^{2}}{4a^{2}}}\,v(t)\,e^{\frac {-bt}{2a}}\right)+b\left(v^{'}(t)\,e^{\frac {-bt}{2a}}-{\frac {b}{2a}}\,v(t)\,e^{\frac {-bt}{2a}}\right)+c\left(v(t)\,e^{\frac {-bt}{2a}}\right)=0}$

${\displaystyle av^{''}(t)\,e^{\frac {-bt}{2a}}-b\,v^{'}(t)\,e^{\frac {-bt}{2a}}+{\frac {b^{2}}{4a}}\,v(t)\,e^{\frac {-bt}{2a}}+b\,v^{'}(t)\,e^{\frac {-bt}{2a}}-{\frac {b^{2}}{2a}}v(t)\,e^{\frac {-bt}{2a}}+cv(t)\,e^{\frac {-bt}{2a}}=0}$

${\displaystyle av^{''}(t)\,e^{\frac {-bt}{2a}}+\left(-b+b\right)v^{'}(t)\,e^{\frac {-bt}{2a}}+\left({\frac {b^{2}}{4a}}-{\frac {b^{2}}{2a}}+c\right)v(t)\,e^{\frac {-bt}{2a}}=0}$ ♥

A parcela envolvendo ${\displaystyle v^{'}(t)}$ é nula. O coeficiente de ${\displaystyle v(t)}$ ${\displaystyle \left({\frac {-b^{2}}{4a}}\right)+c}$ que também é nulo pois as raízes são iguais.

Logo, a equação ♥ será ${\displaystyle av^{''}(t)=0}$  com  ${\displaystyle a\neq 0.}$

Portanto

${\displaystyle v^{''}(t)=0}$;

${\displaystyle v^{'}(t)=C_{1}}$;

${\displaystyle v(t)=C_{1}\,t+\,C_{2}}$

Então, a solução de ♦, será:

${\displaystyle y=v(t)\,e^{\frac {-bt}{2a}}=(C_{1}\,t+\,C_{2})\,e^{\frac {-bt}{2a}}}$

${\displaystyle y=C_{1}\,t\,e^{\frac {-bt}{2a}}+\,C_{2}\,e^{\frac {-bt}{2a}}}$^[4]

Traduzindo esse resultado para as relações de recorrência de segunda ordem homogêneas com raízes iguais, a forma fechada da solução será:

${\displaystyle y_{n}=C_{1}\,n\,(r)^{n}+C_{2}\,(r)^{n}}$

• Para as equações de recorrência de ordem k podemos ter uma raiz de multiplicidade até k. Assim, a forma fechada da equação de recorrência será:

${\displaystyle y_{n}=C_{1}\,n^{k}\,(r)^{n}+C_{2}\,n^{k-1}\,(r)^{n}+...+C_{k-2}\,n^{2}\,(r)^{n}+C_{k-1}\,n\,(r)^{n}+C_{k}\,(r)^{n}}$

Quando as raízes da equação característica são da forma ${\displaystyle q\pm mi}$, pode-se trocar o modo de representação do número complexo para a forma polar e evitar cálculos com complexos. Portanto, se a solução da equação de recorrência fosse

${\displaystyle y_{n}=c_{1}(q+mi)^{n}+c_{2}(q-mi)^{n}}$ poderia ser trocada por

${\displaystyle y_{n}=c_{1}\left[\rho (cos\,{\theta }+i\,sen\,{\theta })^{n}\right]+c_{2}\left[\rho (cos{\theta }-isen{\theta })^{n}\right]}$

${\displaystyle y_{n}=c_{1}\rho ^{n}\left[cos\,{n\theta }+i\,sen\,{n\theta }\right]+c_{2}\rho ^{n}\left[cos\,{n\theta }-i\,sen\,{n\theta }\right]}$

${\displaystyle y_{n}=\rho ^{n}\left[c_{3}\cdot cos\,{(n\theta )}+c_{4}\cdot sen\,{(n\theta )}\right]}$; onde ${\displaystyle c_{3}=c_{1}+c_{2}}$ e ${\displaystyle c_{4}=i(c_{1}-c_{2})}$ são novas constantes arbitrárias.

Seja  ${\displaystyle ax_{n}+bx_{n-1}+cx_{n-2}=g(n)}$  uma equação de recorrência de segunda ordem não-homogênea, sua solução é do tipo  ${\displaystyle y_{n}=h_{n}+p_{n},}$  onde  ${\displaystyle h_{n}}$  é a forma fechada da equação homogênea relacionada e  ${\displaystyle p_{n}}$  é uma solução particular da equação não homogênea.

• Demonstração:

Substituindo ${\displaystyle x_{n}}$ por ${\displaystyle y_{n}=h_{n}+p_{n}}$:

${\displaystyle ax_{n}+bx_{n-1}+cx_{n-2}=g(n)}$

${\displaystyle a(h_{n}+p_{n})+b(h_{n-1}+p_{n-1})+c(h_{n-2}+p_{n-2})=g(n)}$

${\displaystyle ah_{n}+ap_{n}+bh_{n-1}+bp_{n-1}+ch_{n-2}+cp_{n-2}=g(n)}$

${\displaystyle ap_{n}+bp_{n-1}+cp_{n-2}+ah_{n}+bh_{n-1}+ch_{n-2}=g(n)}$

${\displaystyle ap_{n}+bp_{n-1}+cp_{n-2}=g(n)}$  que é válida pois ${\displaystyle p_{n}}$ é solução da equação não-homogênea e ${\displaystyle ah_{n}+bh_{n-1}+ch_{n-2}=0}$ é válida pois ${\displaystyle h_{n}}$ é solução da equação homogênea associada.

Se ${\displaystyle g(n)=d\cdot q^{n}:}$ ${\displaystyle p_{n}}$, será da forma ${\displaystyle A\cdot q^{n}}$ e ${\displaystyle A}$ poderá ser determinado usando as condições iniciais da relação de recorrência. Se ${\displaystyle q}$ for raiz de multiplicidade ${\displaystyle m}$ da equação característica da equação homogênea associada, ${\displaystyle p_{n}}$ será da forma ${\displaystyle A\,n^{m}\cdot q^{n}.}$

Se ${\displaystyle g(n)=d_{l}\,n^{l}+d_{l-1}\,n^{l-1}+d_{l-2}\,n^{l-2}+...+d_{2}\,n^{2}+d_{1}\,n+d_{0}:}$  ${\displaystyle p_{n}}$;será da forma

${\displaystyle A_{l}\,n^{l}+A_{l-1}\,n^{l-1}+A_{l-2}\,n^{l-2}+...+A_{2}\,n^{2}+A_{1}\,n+A_{0}}$ e cada ${\displaystyle A_{j}\,\,(com\,j\in \left\{1,2,3,...,l\right\})}$ pode ser determinado usando as condições iniciais da relação de recorrência.

Se 1 for raiz de multiplicidade  ${\displaystyle m}$ da equação característica da equação homogênea associada,${\displaystyle p_{n}}$ será da forma ${\displaystyle A_{l}\,n^{m+l}+A_{l-1}\,n^{m+l-1}+A_{l-2}\,n^{m+l-2}+...+A_{2}\,n^{m+2}+A_{1}\,n^{m+1}+A_{0}\,n^{m},}$  pois quando 1 é raiz de multiplicidade; ${\displaystyle m}$ da equação característica ele gera um polinômio do tipo ${\displaystyle h_{n}=(1)^{n}(C_{1}+C_{2}n+C_{3}n^{2}+...+C_{m+1}n^{m}).}$

Se ${\displaystyle g(n)}$ for uma soma dos dois últimos casos:${\displaystyle p_{n}}$ será, também, uma soma das formas dos dois casos acima e a resolução procederá como explicado em cada item.

As sequências definidas recursivamente satisfazem uma determinada relação de recorrência e tem seu(s) primeiro(s) termo(s) dado(s).

Exemplos:

• A seqüência ${\displaystyle S}$ abaixo:

${\displaystyle S_{1}=2;}$

${\displaystyle S_{n}=2\times S_{n-1},}$  para  ${\displaystyle n=2}$  ou  ${\displaystyle n>2}$

De acordo com a definição da seqüência  ${\displaystyle S,}$  temos os seguintes termos:

${\displaystyle S_{1}=2;}$

${\displaystyle S_{2}=2\cdot S_{2-1}=2\cdot S_{1}=2\times 2=4;}$

${\displaystyle S_{3}=2\cdot S_{3-1}=2\cdot S_{2}=2\times 4=8;}$

${\displaystyle S_{4}=2\cdot S_{4-1}=2\cdot S_{3}=2\times 8=16;}$

e assim por diante.

• A sequência ${\displaystyle (a_{n})}$ dos números naturais ( ${\displaystyle \mathbb {N} }$ ) ímpares  ${\displaystyle 1,3,5,7,...}$ pode ser definida por ${\displaystyle a_{n}=a_{n-1}+2\,\,(n\geq 1),}$  com  ${\displaystyle a_{1}=1.}$

Observe que essa sequência só esta definida como “a sequência dos números naturais ímpares” por causa da condição inicial  ${\displaystyle a_{1}=1.}$  Se esta condição não tivesse sido estabelecida, a relação de recorrência ${\displaystyle a_{n}=a_{n-1}+2\,\,(n\geq 1)}$ seria satisfeita por todas as progressões aritméticas de razão 2.

• Todas as progressões aritméticas de razão ${\displaystyle r}$ podem ser definidas por ${\displaystyle a_{n}=a_{n-1}+r\,\,(n\geq 1),}$ com ${\displaystyle a_{1}=b.}$

• Todas as progressões geométricas de razão ${\displaystyle q}$ podem ser definidas por ${\displaystyle a_{n}=q\cdot a_{n-1}\,\,(n\geq 1),}$ com ${\displaystyle a_{1}=c.}$

• A sequência dos números de Lucas:

${\displaystyle L_{n}=L_{n-1}+L_{n-2}\,\,(n\geq 2),}$ com ${\displaystyle L_{0}=2}$ e ${\displaystyle L_{1}=1.}$

• A sequência de Fibonacci ${\displaystyle (F_{n})}$

${\displaystyle F_{n}=F_{n-1}+F_{n-2}\,\,(n\geq 2),}$ com ${\displaystyle F_{0}=0}$ e ${\displaystyle F_{1}=1.}$

Os números de Fibonacci são definidos usando-se a relação de recorrência linear ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$, para ${\displaystyle n>1}$, com os seguintes valores iniciais: ${\displaystyle F_{0}=0}$ e ${\displaystyle F_{1}=1}$

Explicitamente, a recorrência produz as equações:

${\displaystyle F_{2}=F_{1}+F_{0}}$

${\displaystyle F_{3}=F_{2}+F_{1}}$

${\displaystyle F_{4}=F_{3}+F_{2}}$

etc.

Obtém-se a partir daí a sequência de número de Fibonnacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Conjuntos são coleções de objetos onde não existe uma ordem imposta. Porém, ainda assim é possível definir alguns conjuntos por recorrência.

• Exemplo:

• Na definição das regras sintáticas para as fórmulas bem formadas (FBFs) da lógica proposicional, utiliza-se a seguinte recorrência:

1. Condição básica: Toda proposição A é uma FBF, denominada de Fórmula Atômica;
2. Relação de recorrência: Se P e Q são FBFs, então ¬P (negação), P Λ Q (conjunção), P V Q (disjunção), P→Q (implicação ou condicional) e P↔Q (bicondicional) também são FBFs.

De acordo com esta definição:

• As proposições A, B e C são fórmulas, pela Condição Básica;
• Como A, B e C são fórmulas, então ¬A e (B Λ C) também são fórmulas, pela relação de recorrência;

Portanto, visto que ¬A e (B Λ C) são fórmulas, então (¬A →(B Λ C)) também é uma fórmula, pela relação de recorrência.

• Conjunto de A* (elementos concatenados de um alfabeto A, formando cadeias de comprimento finito). A definição recorrente de A* é:

1. Condição básica: ¢ Є A* — a cadeia vazia (de comprimento zero, representada por ¢) pertence a A*;
2. Relação de recorrência:

a) Se a Є A, então a Є A* — todos os elementos de A pertencem a A*;

b) Se a, b Є A*, então ab Є A* — a concatenação "a" com "b" pertence a A*.

De acordo com a definição, para A = {a, b}: A* = {¢, a, b, aa, ab, bb, aaa, ...}.

Algumas operações em objetos podem ser definidas de forma recorrente.

Exemplo:

• A operação de exponenciação  ${\displaystyle a^{n}}$  de um número real  ${\displaystyle a}$,  onde  ${\displaystyle n}$  é um número natural, é definida por:

1. Condição básica:  ${\displaystyle a^{0}=1;}$
2. Relação de recorrência:  ${\displaystyle a^{n}=a\cdot a^{(n-1)},}$ para  ${\displaystyle n>1}$  ou  ${\displaystyle n=1.}$

• A operação de multiplicação de dois números naturais,  ${\displaystyle x}$  e  ${\displaystyle y}$,   é definida por:

1. Condição básica:  ${\displaystyle x\cdot 1=x;}$
2. Relação de recorrência:  ${\displaystyle x\cdot (y)=x\cdot (y-1)+x,}$  para  ${\displaystyle y>1.}$

Na construção de um algoritmo recursivo é necessário estabelecer uma condição de parada, ou seja, uma condição na qual o algoritmo deve ser capaz resolver o problema de forma trivial. Veja alguns exemplos:

• Exemplo: O algoritmo para o cálculo do fatorial de modo recorrente.

função ${\displaystyle {\it {Fat}}(n)}$

se ${\displaystyle n<2}$ então

retorne ${\displaystyle 1}$

caso contrário

retorne ${\displaystyle n\times {\it {Fat}}(n-1)}$

Matematicamente, escrevemos:

${\displaystyle Fat_{n}=n*Fat_{n-1}}$

• Exemplo: O algoritmo para o cálculo do n-ésimo termo da Sequência de Fibonacci.

função ${\displaystyle {\it {Fib}}(n)}$

se ${\displaystyle n<2}$ então

retorne ${\displaystyle 1}$

caso contrário

retorne ${\displaystyle {\it {Fib}}(n-1)+{\it {Fib}}(n-2)}$

Matematicamente, definimos de forma recursiva F_n como sendo:

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

• Relação matemática
• Lógica
• Números naturais
• Conjuntos
• Seqüência matemática
• Algoritmo
• Recursão transfinita - extensão da relação de recorrência para números transfinitos

Referências

• Portal da matemática