I have a recursion $au_{n+1} + bu_n + cu_{n-1} = d_n$ where $u_n$ denotes an unknown sequence ranging from $n=1$ to $n=N-1$ and $u_0 = 0 = u_N$ and $d_n$ is a known sequence.

Let $\sum_{j=1}^{N-1}d_jx^j = D(x)$

and $\sum_{j=0}^{N}u_jx^j = U(x)$

next, we multiply the recurrence by $x^n$ and sum over all values for which the recurrence is true, i.e. $n=1$ to $n = N-1$. Then we end up getting the equation

$(c+bx+ax^2)U(x) = x(D(x) + au_1 + cu_{N-1}x^N)$

where coefficients $a,b,c$, function $D(x)$ are known and $U(x)$ needs to be found. We can solve for $u_1$ and $u_1$ and $u_{N-1}$ by plugging in the roots of the quadratic on the RHS and using the factor theorem. Where I'm stuck is solving for it when the roots, (say $r_1,r_0$) satisfy $r_1^N=r_0^N$ which is when it is a perfect square or the difference of two squares (depending on whether $N$ is odd or even). I know that $U(x)$ has the factor $x$ and that it might be possible to solve it by factoring say $(2ax+b)$ from the brackets on the RHS once and then plugging in the same root again. But is it sensible to do this? I can't seem to get a nice, closed form solution.

Oh by the way, this is an 'exercise left for the reader' i've been stuck on for days now


You have:

$$ U(x) = \frac{x(D(x) + a u_1 + c u_{N - 1} x^N)}{c + b x + a x^2} $$

Here $D(x)$ is a polynomial. You can write $U(x)$ as partial fractions with (possibly complex) linear denominators, each such term corresponds to a geometric series on $x$, giving you your coefficicients $u_n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.