0
$\begingroup$

There are many questions about $k$-order recurrence relations and answers on how to solve them at the forum. But is there a thing as a "complete" or "full" recurrence relation (I don't know their name)? I mean a recurrence relation where the $n$-th term depends on all that came before, like $$ y_{n+1} = a_n y_n + \cdots + a_0y_0. $$ How could such recurrence be solved?

$\endgroup$

1 Answer 1

0
$\begingroup$

Assuming $(a_n)_{n \ge 0}$ is a given sequence, and assuming it is the same sequence at each step: $y_{n+1}=a_n y_n+(a_{n-1}y_{n-1}+ \cdots + a_0y_0)=a_ny_n + y_n = (a_n+1)y_n\,$. Then, by telescoping, $y_n = y_0 \cdot \prod_{k=0}^{n-1} (a_k+1)\,$.

$\endgroup$
3
  • $\begingroup$ Nice. But what if it is not the same sequecence at every iteration? Maybe making the notation better: $\endgroup$
    – user308522
    Commented Apr 8, 2017 at 21:33
  • $\begingroup$ Nice. But what if it is not the same sequence at every iteration? Maybe making the notation clearer: $y_{n+1}=a_{n,n+1}y_n+a_{n-1,n+1}y_{n-1}+⋯+a_{0,n+1}y_0$. $\endgroup$
    – user308522
    Commented Apr 8, 2017 at 21:39
  • $\begingroup$ @user308522 You'll have to decide on what the question is which you mean to ask. In the most general form, a "complete" recurrence relation would be something like $y_{n+1}=f_n(y_n,y_{n-1},\cdots,y_0)$ but it's doubtful you'll find many useful properties without some additional assumptions on $f_n$. $\endgroup$
    – dxiv
    Commented Apr 8, 2017 at 21:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .