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