Recorrência linear de primeira ordem
Tivemos muita neve nesta temporada. Na primavera, essa neve derrete e temos muita água. Digamos que a quantidade de água hoje seja u n galões.
Além disso, digamos que u n dependa de u n -1 . O n – 1 significa em um momento anterior, como no dia anterior. Por exemplo, u n = 2 u n -1 significa que a quantidade de água hoje é o dobro da quantidade de ontem. Isso pode ou não ser realista. Mas se fosse, e se a quantidade de água no início fosse 1 galão, poderíamos escrever o seguinte:
 |
Esta é uma relação de recorrência . Prevemos ou estimamos o valor presente de algo com base no valor anterior. Para que isso funcione, precisamos do valor no início. O valor inicial é o valor u o .
Vamos continuar com essa ideia de recorrência. Neste exemplo, para o dia 2, podemos escrever
 |
Da mesma forma, para o dia 3, temos
 |
Estamos obtendo uma sequência de números: 1, 2, 4, 8, … mas antes de ficarmos completamente inundados, vamos definir algumas terminologias.
Em geral, se u n = a u n – 1 + c , chamamos isso de relação de recorrência de primeira ordem . Por primeira ordem, queremos dizer que estamos olhando para trás apenas uma unidade no tempo até u n -1 . Nesta lição, os coeficientes a e c são constantes. Existem também relações de recorrência de ordem superior.
Por exemplo, esta seria uma relação de recorrência de segunda ordem, uma vez que está olhando para trás no tempo mais de uma unidade:
 |
Significando que o valor no tempo n é igual a a vezes o valor no tempo n – 1 mais b vezes o valor no tempo n – 2.
Nesta lição, vamos nos concentrar nas relações recursivas lineares de primeira ordem . Linear aqui significa que u n -1 não será elevado a nenhuma potência superior a 1. Mas, também existem relações de recorrência não lineares. Exemplos de relações de recorrência não lineares são u n = a ( u n – 1 ) 2 e u n = cos ( u n – 1 ).
Algumas aplicações de relações de recorrência podem incluir o seguinte:
- Estudo Populacional
- Análise de Algoritmo
- Processamento de sinal digital
- Finanças
Alguns exemplos de finanças
Exemplo 1
Uma conta bancária com juros é aberta e a cada ano depositamos $ 1000. Os juros anuais são de 1%. Como escreveríamos isso como uma recorrência linear de primeira ordem?
No início, abrimos a conta depositando $ 1000. Assim, u o = 1000.
Para n = 1, temos u 1 = u o + 0,01 ( u o ) + 1000. Ou seja, o novo saldo é a soma do valor que tínhamos no ano passado com os juros ganhos de 1% mais o novo depósito de 1000.
Podemos escrever isso como u 1 = (1 + 0,01) u o + 1000.
Portanto, temos esta relação de recorrência linear de primeira ordem:
 |
Após 5 anos, quanto dinheiro foi ganho em juros?
Ano 1: u 1 = 1,01 u o + 1000 = 1,01 (1000) + 1000 = 2010
Ano 2: u 2 = 1,01 u 1 + 1000 = 1,01 (2010) + 1000 = 3030,01
Ano 3: u 3 = 1,01 u 2 + 1000 = 1,01 (3030,10) + 1000 = 4060,40
Ano 4: u 4 = 1,01 u 3 + 1000 = 1,01 (4060,40) + 1000 = 5101,01
Ano 5: u 5 = 1,01 u 4 + 1000 = 1,01 (5101,01) + 1000 = 6152,02
Portanto, após 5 anos e depositando $ 6.000, ganhamos $ 152,02 em juros.
Exemplo 2
E se pegarmos emprestado $ 15.000 do banco? O banco cobra-nos 10% ao ano e reembolsamos o empréstimo a $ 800 por mês. Esta também é uma relação de recorrência linear de primeira ordem.
O saldo do empréstimo no início é u o = 15000.
Escrevemos a taxa de juros mensal como 0,10 / 12, uma vez que há 12 meses em um ano. Assim, a relação de recorrência é
 |
Calculando 1 + 0,10 / 12 obtemos 1,00833… Para tornar os cálculos mais fáceis, vamos arredondar para 1,008. Vamos calcular o que devemos ao banco durante os primeiros 12 meses.
Mês 1: u 1 = 1,008 (15000) – 800 = 14320
Mês 2: u 2 = 1,008 (14320) – 800 = 13634,56
Mês 3: u 3 = 1,008 (13634,56) – 800 = 12943,64
Mês 4: u 4 = 1,008 (12943,64) – 800 = 12247,19
Mês 5: u 5 = 1,008 (12247,19) – 800 = 11545,17
Mês 6: u 6 = 1,008 (11545,17) – 800 = 10837,53
Mês 7: u 7 = 1,008 (10837,53) – 800 = 10124,23
Mês 8: u 8 = 1,008 (10124,23) – 800 = 9405,22
Mês 9: u 9 = 1,008 (9405,22) – 800 = 8680,46
Mês 10: u 10 = 1,008 (8680,46) – 800 = 7949,90
Mês 11: u 11 = 1,008 (7949,90) – 800 = 7213,50
Mês 12: u 12 = 1,008 (7213,50) – 800 = 6471,21
Continuando esses cálculos, descobrimos que o saldo do empréstimo caiu para $ 315,06 no mês 20. Portanto, o empréstimo é pago em menos de dois anos.
Resumo da lição
Quando uma variável em um determinado momento depende de seu valor em momentos anteriores, temos uma relação de recorrência . Uma recorrência de primeira ordem ocorre em apenas uma unidade de tempo. Uma recorrência linear de primeira ordem tem a forma u n = a u n – 1 + c . As aplicações das relações de recorrência incluem estudos populacionais, análise de algoritmos, processamento digital de sinais e finanças.