2
$\begingroup$

Let $(u_n)$ and $(v_n)$ be two linear recurrent sequences, satisfying the same recurrence relation. Suppose that $v_n$ is nonzero for all large enough $n$, then we can set $w_n=\frac{u_n}{v_n}$. I have two questions about $(w_n)$ :

-Is $(w_n)$ still linear recurrent (not necessarily with the same recurrence relation, but with a new relation that may be computed directly from the relation ruling $(u_n)$ and $(v_n)$, independently of the initial values) ? My guess is that the answer is no.

-Is $(w_n)$ still recurrent (i.e. satisfies a not necessarily linear recurrence formula that may be computed directly from the relation ruling $(u_n)$ and $(v_n)$, independently of the initial values) ? My guess is that the answer is yes.

  • 0
    If say start with homogeneous linear constant coefficients, not even necessarily same recurrence, then ratio satisfies linear non-constant coefficients equation.2012-03-03

2 Answers 2

3

Suppose $u$ and $v$ satisfy the $d$-step homogeneous linear constant-coefficient recurrence $x_n = \sum_{k=1}^d a_k x_{n-k}$. The case $d=1$ is easy, so I'll suppose $d\ge 2$. Then $u_n = v_n w_n = \sum_{k=1}^d a_k v_{n-k} w_{n-k}$. But also $v_n w_n = \sum_{k=1}^d a_k v_{n-k} w_n$. So $\sum_{k=1}^d a_k v_{n-k} (w_n - w_{n-k}) = 0$. That says $v$ satisfies a $d-1$-step homogeneous recurrence whose coefficients are polynomials of degree $1$ in $w$, in addition to its original $d$-step recurrence.
Now for the $2d-1$ variables $v_n, v_{n-1}, \ldots v_{n-2d+2}$ we have $2d-1$ homogeneous linear equations: $v_{n-j} - \sum_{k=1}^d a_k v_{n-j-k} = 0$ for $j = 0$ to $d-2$ and $\sum_{k=1}^d a_k (w_{n-j} - w_{n-k-j}) v_{n-k-j} = 0$ for $j = -1$ to $d-2$. But these equations do have a nonzero solution, so the determinant of the coefficient matrix must be $0$. That determinant is a polynomial of degree $d$ in $w_{n+1}$ to $w_{n-2d+2}$, which gives you your recurrence relation for $w$. It won't be linear, though: it's a homogeneous polynomial of degree $d$ in the w_j's, with degree $1$ in $w_{n+1}$, so $w_{n+1}$ is a rational function of $w_n$ to $w_{n-2d+2}$ with numerator and denominator of degrees $d$ and $d-1$ respectively.

For example, if $u_n$ and $v_n$ satisfy the Fibonacci relation $x_n = x_{n-1} + x_{n-2}$ (with $d=2$), $\eqalign{\det &\pmatrix{1 & -1 & -1\cr w_{n+1}-w_n & w_{n+1}-w_{n-1} & 0\cr 0 & w_n - w_{n-1} & w_n - w_{n-2}\cr} \cr =& w_{{n+1}}w_{{n}}-2\,w_{{n+1}}w_{{n-2}}-2\,w_{{n-1}}w_{{n}}+w_{{n-1}}w_ {{n-2}}+w_{{n+1}}w_{{n-1}}+w_{{n}}w_{{n-2}} =0\cr}$

2

If by "linear recurrence" you mean with constant coefficients, then the answer to 1) is no. The sequences satisfying such a recurrence are precisely the sequences of the form $a_n = \sum_{i=1}^k P_i(n) \lambda_i^n$

where $P_i$ are polynomials and $\lambda_i \in \mathbb{C}$. In particular, the sequence $a_n = \frac{1}{n}$

(which is a quotient of two sequences of this form) is not of this form. Indeed, it approaches $0$, so we must have $|\lambda_i| < 1$ for all $i$, but it approaches $0$ polynomially rather than exponentially.

Alternately, the sequences (eventually) satisfying a linear recurrence are precisely the sequences with rational generating function, and the sequence $a_n = \frac{1}{n}$

(which is a quotient of two sequences of this form) is not of this form. Indeed, it has generating function $\sum a_n x^n = \log \left( \frac{1}{1-x} \right).$

  • 0
    Never forget generating functions ! I don't like them, but I should.2012-03-03