segunda-feira, 1 de outubro de 2012

076-Sequências Recorrentes de Ordem k

 

O triângulo de Pascal tem grande importância em certas classes de sequências recorrentes.

Observação: todas as fórmulas deste blog são vizualizadas corretamente no Mozilla Firefox.

Definição

Conforme Edgard de Alencar Filho, no seu livro Funções Aritméticas / Números Notáveis, uma sequência de números reais [;a_1;], [;a_2;],...,[;a_n;],... chama-se sequência recorrente de ordem [;k\geq1;], se e somente se, existem [;k;] números reais [;c_1;],[;c_2;],...,[;c_k\neq 0;] tais que, para todo inteiro [;n>k;], temos a igualdade

[;a_n=c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k};]

ou seja, o termo genérico [;a_n;] é uma combinação linear dos [;k;] termos anteriores [;a_{n-1};], [;a_{n-2};],...,[;a_{n-k};], sendo que os [;k;] primeiros termos são previamente definidos, de forma que possamos calcular [;a_n;] para [;n>k;].


Exemplos

[;1);] Uma progressão geométrica ordinária é uma sequência recorrente de ordem [;k=1;] porque

[;a_n=a_1q^{n-1}=q.a_1q^{n-2} \Rightarrow;]

[;a_n=qa_{n-1};] ,

 com [;c_1=q \neq 0;] 

[;2);] Dados [;a_1=1;] e [;a_2=1;], temos a sequência recorrente de ordem [;k=2;] conhecida como sequência de Fibonacci

[;a_n=a_{n-1}+a_{n-2};]

com [;c_1=1;] e [;c_2=1;] 

[;F(1,1,2,3,5,8,13,21,...);] 

Mas, se em [;a_n=a_{n-1}+a_{n-2};], tivermos [;a_1=1;] e [;a_2=3;] se forma agora uma outra sequência de ordem [;k=2;] chamada de sequência de Lucas [;L(1,3,4,7,11,18,29,47,...);].

[;3);] Uma progressão aritmética ordinária, com [;r \neq 0;], é uma sequência recorrente de ordem [;k=2;] porque

[;a_n=a_{n-1}+r;]   

  [;a_{n-1}=a_{n-2}+r;] 

 e tirando a diferença membro a membro, obtemos

[;a_n-a_{n-1}=a_{n-1}-a_{n-2} \Rightarrow;] 

[;a_n=2a_{n-1}-a_{n-2};] 

com [;c_1=2;] e [;c_2=-1;]

[;4);] A sequência dos quadrados perfeitos [;(1,4,9,...,n^2,...);] é uma sequência recorrente de ordem [;k=3;], tendo em vista que

[;3a_{n-1}=3(n-1)^2=3n^2-6n+3;]

[;3a_{n-2}=3(n-2)^2=3n^2-12n+12;] 

e fazendo a diferença por membro, chegamos a

[;3a_{n-1}-3a_{n-2}=6n-9=n^2-(n-3)^2=a_n-a_{n-3} \Rightarrow;]

[;a_n=3a_{n-1}-3_{n-2}+a_{n-3};] 

com [;c_1=3;],[;c_2=-3;] e [;c_3=1;] 


TEOREMA

Toda sequência cujo termo geral é um  polinômio [;a_n=P(n);] de grau [;g\geq1;] é uma sequência recorrente de ordem [;k=g+1;] .

Demonstração

Vamos aproveitar um resultado anterior. Conforme vimos no post 074 (link), a derivada natural ou discreta de [;i;]-ésima ordem de [;P(n);] é

[;P_i(n)={ i \choose 0}P(n+i)-{ i \choose 1}P(n+i-1) +{ i \choose 2}P(n+i-2)-...(-1)^i{ i \choose i}P(n);]

Mas, da mesma forma que a derivada infinitesimal, a derivada de ordem [;g+1;] de um polinômio de grau [;g;] é [;P_{g+1}(n)=0;]. Logo,

[;P_{g+1}(n)={ g+1 \choose 0}P(n+g+1)-{g+1 \choose 1}P(n+g) +{ g+1 \choose 2}P(n+g-1)-...;]

[;...+(-1)^{g+1}{ g+1 \choose g+1}P(n)=0;] 

Agora, fazendo [;n+g+1=m;] , temos

[;{ g+1 \choose 0}P(m)-{g+1 \choose 1}P(m-1) +{ g+1 \choose 2}P(m-2)-...+(-1)^{g+1}{ g+1 \choose g+1}P[m-(g+1)]=0;] 

De forma que

[;P(m)={g+1 \choose 1}P(m-1) - { g+1 \choose 2}P(m-2)+...+(-1)^{g}{ g+1 \choose g+1}P[m-(g+1)];] 

e como temos [;g+1;] valores anteriores no segundo membro, segue que um polinômio de grau [;g;] é uma sequência recorrente de ordem [;k=g+1;]


Referência bibliográfica: Funções Aritméticas / Números Notáveis de Edgard de Alencar Filho, Editora Nobel, [;1988;].

Gostará de ler também:

074-Fórmula Recursiva para Polinômio

Imagem:http://redematematica.wordpress.com/2009/11/18/tarefas-7%C2%BA-ano-%E2%80%98sequencias-e-regularidades%E2%80%99-20092010-npmat/

Nenhum comentário:

Postar um comentário