polynomial solution of $a_n + ca_{n-1} + a_{n-2} = 0$

Question

Let $c$ be a constant, and consider the following recurrence relation: $a_n + ca_{n-1} + a_{n-2} = 0$. I am asked to find the value of $c$ where the recurrence has a non constant polynomial solution.

I declared $f(x) = \sum_{n=0}^\infty a_n \cdot x^n$, multiplied the recurrence by $x^n$ and took the sum from $n=2$, and got that

$$\sum_{n=2}^\infty a_n \cdot x^n = -c \cdot \sum_{n=2}^\infty a_{n-1} \cdot x^n - \sum_{n=2}^\infty a_{n-2}x^n$$

$$\sum_{n=2}^\infty a_n \cdot x^n = -cx \cdot \sum_{n=2}^\infty a_{n-1} \cdot x^{n-1} - x^2 \cdot \sum_{n=2}^\infty a_{n-2}x^{n-2}$$

$$ f(x) - a_0 - a_1 x = -cx(f(x)-a_0) - x^2f(x)$$

$$ (1+cx+x^2)f(x) = a_0 cx + a_1 x + a_0 $$

$$f(x) = \frac {a_0 cx + a_1 x + a_0}{x^2 +cx + 1} $$

and here i cant see any restriction on $c$. Any $c$ looks fine to me, and no specific $c$ would make problems. Would love to get some help moving forward, or corrections if my way of solving this question is wrong. Thank you!

Answer 1

Hypothesis: $a_n=\sum_{i=0}^M b_i n^i$, $b_M \ne 0$.

It's simpler to write the recurrence as $a_{n+1} + ca_{n} + a_{n-1} = 0$ which leads to $\sum_{i=0}^M b_i (n+1)^i + c\sum_{i=0}^M b_i n^i + \sum_{i=0}^M b_i (n-1)^i=0$

$\sum_{i=0}^M b_i ((n+1)^i + (n-1)^i + c n^i) = 0$

The left side is an $M$'th degree polynomial. We want $b_i$ and $c$ such that it is zero for all $n$. Just focusing on the $n^M$ term of this expression:

$b_M (2n^M + c n^M) = 0$ which means $c = -2$.

At this point, $c=-2$ is shown to be a necessary condition. For this specific problem, it is easiest to come up with a working solution -- like $a_n=n$ -- to show that it is sufficient.

Answer 2

Polynomial sequences ${\mathbf a} := (a_n)$ of degree $< k$ are characterized by the property that $(\Delta^k {\bf a})$ is the zero sequence, where $\Delta$ is the finite difference operator, $(\Delta{\textbf a})_n = a_{n + 1} - a_n$. So, if ${\mathbf a}$ is a polynomial sequence of degree $< 2$ for some $c$, we have

$$0 = (\Delta^2 {\bf a})_n = (\Delta {\bf a})_{n+1} - (\Delta {\bf a})_n = (a_{n + 2} - a_{n + 1}) - (a_{n + 1} - a_n) = a_{n + 2} - 2 a_{n + 1} + a_n $$ But by hypothesis $a_{n + 2} = -c a_{n + 1} - a_n$, so the condition is $$0 = (-c a_{n + 1} - a_n) - 2 a_{n + 1} + a_n = (2 + c) a_{n + 1} .$$ So, either $a_n = 0$ for all $n$ (which is a constant sequence), or $c = -2$. Substituting $c = -2$ gives the recurrence $$a_n - 2 a_{n - 1} + a_{n - 2} = 0,$$ and it's routine to verify that any polynomial of degree $1$ satisfies the recurrence.

---

Alternatively, the general solution to a constant-coefficient linear recurrence $$a_n + b_{k - 1} a_{n - 1} + \cdots + b_0 a_{n - k} = 0$$ is a linear combination of terms of the form $n^l r^n$, where $r$ is a root of the characteristic polynomial of the recurrence, $p(x) := x^k + b_{k - 1} x^{k - 1} + \cdots + b_0$ and $l$ is a nonnegative integer less than the multiplicity of $r$. In particular, these terms are only polynomial for $r = 0, 1$, and for our recurrence $b_0 \neq 0$, so $r = 1$. To have a nonconstant polynomial solution, we must have a term with $r = 1$ and $l > 0$, which gives a general condition to have a nonconstant polynomial solution:

A constant-coefficient linear recurrence has a nonconstant polynomial solution if and only if 1 is a multiple root of the characteristic polynomial of the recurrence.

In our case, we must have $$x^2 + 2 c x + 1 = (x - 1)^2,$$ and expanding and comparing like coefficients gives $c = -2$.