Simplifying a Recurrence Relation

97 Views Asked by At

$(n_i) $ is a sequence of integers satisfying $n_{i+1}=a_{i+1}n_i+n_{i-2}$. Consider a subsequence $(n_{i_j}).$

Can $n_{j_{i+1}}$ be written in terms of $n_{j_i}$? An attempt is to use the recurrence relation and write $$n_{j_{i+1}}=a_{j_{i+1}}n_{j_{i+1}-1}+n_{j_{i+1}-2}=a_{j_{i+1}}(a_{j_{i+1}-1}n_{j_{i+1}-2}+n_{j_{i+1}-3})+n_{j_{i+1}-2} $$ and so on, but I'm not sure how to obtain a closed formula containing $n_{j_i}$

Another idea is to write $n_i=q^i$. Then $$q=\frac{a_{j_{i+1}}+\sqrt{a_{j_{i+1}}^2+4}}{2}, $$ but there's no $n_{j_i}.$

1

There are 1 best solutions below

0
On BEST ANSWER

Here is an example to show what is not possible.

Set $\forall n: a_n=0 $, then you have $n_i=n_{i-3}$, but $n_i$ need bear no relation at all to $n_{i-2}$, and in fact you end up with three independent constant sequences interleaved with each other. You can pick a subsequence which picks out the values in any order (e.g. based on the $n^{th}$ digit of $\pi$).

With a little jiggling, you will see that the $a_i$ can be chosen to give a range of behaviours - so unless you have some control over the $a_i$ there seems to be no general way to begin to answer the question.