Como Resolver Relações de Recorrência

Baixe em PDF

Baixe em PDF

Neste Artigo:

Aritmético

Geométrico

Polinomial

Linear

Gerando funções

Mostrar mais 2...

Mostrar menos...

Artigos Relacionados

Referências

Ao tentar encontrar a fórmula para uma sequência matemática, um dos passos comuns de se tomar é encontrar o enésimo termo, e não em função de $n$ mas dos termos já previamente declarados. Em um exemplo, apesar de ser bom ter uma função fechada para o enésimo termo da sequência de Fibonacci, às vezes tudo o que basta fazer é a relação de recorrência, ou afirmam que cada termo se refere à soma dos dois termos anteriores. O presente artigo demonstra diversos métodos para deduzir uma fórmula fechada a partir da recorrência.

Passos

Método 1

Método 1 de 5:

Aritmético

Baixe em PDF

1. 
   1
   Tome como exemplo uma sequência aritmética como $$ 5 , 8 , 11 , 14 , 17 , 20 , … {\displaystyle 5,8,11,14,17,20,\ldots }
2. 
   2
   Uma vez que cada termo é três unidades maior que o anterior, ela pode ser tratada como uma recorrência, conforme demonstrado.
3. 
   3
   Reconheça que qualquer recorrência no formato $$ a n = a n − 1 + d {\displaystyle a_{n}=a_{n-1}+d} é uma sequência aritmética.
4. 
   4
   Escreva a fórmula de uma sequência aritmética em seu formato fechado, incluindo as incógnitas quando necessário.
5. 
   5
   Resolva a equação com base nas incógnitas presentes, dependendo do formato da sequência. Nesse caso, uma vez que $5$ era o $0^{o}$ termo, a fórmula será $a_{n}=5+3n$. Se quiser, em vez disso, que ele seja o primeiro termo, você obterá $a_{n}=2+3n$.
   Publicidade

Método 2

Método 2 de 5:

Geométrico

Baixe em PDF

1. 
   1
   Tome por exemplo uma sequência geométrica como $$ 3 , 6 , 12 , 24 , 48 , … {\displaystyle 3,6,12,24,48,\ldots }
2. 
   2
   Uma vez que cada termo é o dobro do anterior, ela pode ser tratada como uma recorrência, conforme demonstrado.
3. 
   3
   Reconheça que qualquer recorrência no formato $$ a n = r × a n − 1 {\displaystyle a_{n}=r\times a_{n-1}} é uma sequência geométrica.
4. 
   4
   Escreva a fórmula de uma sequência geométrica em seu formato fechado, incluindo as incógnitas quando necessário.
5. 
   5
   Resolva a equação com base nas incógnitas presentes, dependendo do formato da sequência. Nesse caso, uma vez que $3$ era o $0^{o}$ termo, a fórmula será $a_{n}=3\times 2^{n}$. Se quiser, em vez disso, que ele seja o primeiro termo, você obterá $a_{n}{=3\times 2^{(n-1)}}$.
   Publicidade

Método 3

Método 3 de 5:

Polinomial

Baixe em PDF

1. 
   1
   Tome como exemplo a sequência $$ 5 , , − 8 , − 17 , − 25 , − 30 , … {\displaystyle 5,0,-8,-17,-25,-30,\ldots } apresentada pela recorrência $a_{n}=a_{n-1}+n^{2}-6n$.
2. 
   2
   Qualquer recorrência no formato demonstrado, onde $$ p ( n ) {\displaystyle p(n)} representa qualquer polinômio em $$ n {\displaystyle n} , terá um formato polinomial fechado de grau uma vez superior àquele presente em $$ p {\displaystyle p} .
3. 
   3
   Escreva o formato geral de um polinômio no grau desejado. No exemplo, $p$ é quadrático, sendo necessário um valor cúbico para representar a sequência $a_{n}$.
4. 
   4
   Uma vez que o valor cúbico geral tem quatro coeficientes incógnitos, é necessário usar quatro termos da sequência para resolver o sistema resultante. Qualquer escolha será válida, então aqui serão usados $0$, $1$, $2$ e $3$. Executar a recorrência em sentido contrário para calcular o $-1^{o}$ termo pode facilitar alguns cálculos, mas não se trata de um passo necessário.
5. 
   5
   Solucione o sistema resultante de equações $$ deg ⁡ ( p ) + 2 {\displaystyle \deg(p)+2} em incógnitas $$ deg ⁡ ( p ) = 2 {\displaystyle \deg(p)=2} ou calcule um polinômio de Lagrange aos pontos $$ deg ⁡ ( p ) + 2 {\displaystyle \deg(p)+2} conhecidos.

   • Se o $0^{o}$ termo foi um dos usados no cálculo dos coeficientes, você conseguirá a constante do polinômio de forma livre e pode imediatamente reduzir o sistema a equações $\deg(p)+1$ em incógnitas $\deg(p)+1$, conforme demonstrado.
6. 
   6
   Represente a fórmula fechada de $$ n {\displaystyle n} em forma de um polinômio com coeficientes conhecidos.
   Publicidade

Método 4

Método 4 de 5:

Linear

Baixe em PDF

1. 
   1
   Esse é o primeiro método capaz de resolver a sequência Fibonacci apresentada na introdução do artigo, mas é possível solucionar qualquer outra em que o enésimo termo consiste na combinação linear dos termos $$ k {\displaystyle k} anteriores. Tome agora um exemplo diferente cujos termos iniciais são $1,4,13,46,157,\ldots$
2. 
   2
   Escreva o polinômio característico da recorrência. Ele pode ser encontrado substituindo-se cada $a_{n}$ nela presente por $x^{n}$ e dividindo-o por $x^{(n-k)}$, restando apenas um polinômio mônico de grau $k$ e uma constante diferente de zero.
3. 
   3
   Solucione o polinômio característico. Nesse caso, a característica possui grau $2$, tornando possível usar a fórmula quadrática para determinar suas raízes.
4. 
   4
   Qualquer expressão no formato exibido satisfaz a recorrência. O $c_{i}$ representa todas as constantes, e a base dos expoentes representa as raízes para a característica encontrada acima. Isso pode ser verificado por indução.

   • Se a característica tem uma raiz múltipla, a etapa deve ser ligeiramente alterada. Se $r$ é uma raiz de multiplicidade $m$, use $(c_{1}r^{n}+c_{2}nr^{n}+c_{3}n^{2}r^{n}+\ldots +c_{m}n^{(m-1)}r^{n})$ em vez de apenas $(c_{1}r^{n})$. Em um exemplo, a sequência $5,0,-4,16,144,640,2.240,\ldots$ satisfaz a relação de recorrência $a_{n}=6a_{n-1}-12a_{n-2}+8a_{n-3}$. O polinômio característico possui uma raiz tripla igual a $2$ e sua fórmula fechada será $a_{n}=(5\times 2^{n})-(7\times n\times 2^{n})+(2\times n^{2}\times 2^{n})$.
5. 
   5
   Determine o $$ c i {\displaystyle c_{i}} que satisfaz as condições inicialmente especificadas. Assim como no exemplo polinomial, para isso é preciso criar um sistema linear de equações a partir dos termos iniciais. Uma vez que o exemplo possui duas incógnitas, dois termos serão necessários — qualquer escolha será valida, então tome como exemplo o $0^{o}$ e o $1^{o}$ para não precisar elevar um número irracional a uma potência.
6. 
   6
   Solucione o sistema resultante de equações.
7. 
   7
   Insira as constantes resultantes na fórmula geral como solução.
   Publicidade

Método 5

Método 5 de 5:

Gerando funções

Baixe em PDF

1. 
   1
   Tome como exemplo a sequência $$ 2 , 5 , 14 , 41 , 122 , … {\displaystyle 2,5,14,41,122,\ldots } dada pela recorrência demonstrada. Ela não pode ser resolvida com os métodos acima, mas é possível determinar uma fórmula com base nas funções geradoras.
2. 
   2
   Escreva a função geradora da sequência. Ela é simplesmente uma série de potência formal na qual o coeficiente de $x^{n}$ é o enésimo termo da sequência.
3. 
   3
   Manipule a função geradora como demonstrado. O objetivo desse passo é encontrar uma equação que ensine a calcular o valor da função geradora $A(x)$. Em primeiro lugar, extraia o termo inicial e aplique a relação de recorrência nos termos remanescentes. A seguir, divida a soma e extraia os termos constantes. Para isso, use a definição de $A(x)$ e a fórmula para a soma de uma série geométrica.
4. 
   4
   Determine a função geradora $$ A ( x ) {\displaystyle A(x)} .
5. 
   5
   Determine o coeficiente do $$ x n {\displaystyle x^{n}} presente em $$ A ( x ) {\displaystyle A(x)} . Os métodos para isso variam de acordo com o formato de $A(x)$, mas o das frações parciais combinado com o conhecimento da função geradora relativo a uma sequência geométrica também servirão, como demonstrado.
6. 
   6
   Escreva a fórmula de $$ a n {\displaystyle a_{n}} identificando o coeficiente de $$ x n {\displaystyle x^{n}} em $$ A ( x ) {\displaystyle A(x)} .
   Publicidade

Dicas

• A indução também é uma técnica bastante popular. Costuma ser fácil provar desse modo que uma fórmula dada satisfaz a uma recorrência dada, mas o problema é que será preciso adivinhá-la com antecedência.
• Alguns desses métodos requerem uma grande potência computacional e apresentam muitas oportunidades de erro. É sempre bom conferir a fórmula e analisar os termos conhecidos.
• "Na matemática, os números de Fibonacci são aqueles presentes na seguinte sequência: $1,1,2,3,5,8,13,21,34,55,89,144,\ldots$"
  • A espiral de Fibonacci: uma aproximação da espiral de ouro criada pelo desenho de arcos conectando cantos opostos dos quadrados presentes no mosaico de Fibonacci — nesse caso são usados quadrados de tamanhos $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$ e $34$.
  • Por definição, os primeiros dois números na sequência de Fibonacci são $1$ e $1$ ou $0$ e $1$, dependendo do ponto inicial escolhido, e cada número subsequente consiste na soma dos dois anteriores.
  • Em termos matemáticos, a sequência $F_{n}$ contendo os números de Fibonacci é definida pela relação de recorrência
    $F_{n}=F_{n-1}+F_{n-2}$
    Os seguintes valores individuais são os seguintes:
    ${\begin{aligned}F_{1}&=1\\F_{2}&=1\\\end{aligned}}$$\ \ \$ou$\ \ \$${\begin{aligned}F_{0}&=0\\F_{1}&=1\end{aligned}}$
• À medida em que $n$ aumenta, o limite da proporção ${\frac {F_{n}}{F_{n-1}}}$ é conhecido como Proporção Áurea, Proporção de Ouro ou pela letra grega $\phi$ (fi), de modo que essa mudança fica caracterizada como ${\frac {F_{n-1}}{F_{n}}}$.

Publicidade