# The characteristic polynomial of a recurrence relation.

If I have a linear homogeneous recurrence relation

$$y_n=c_1y_{n-1}+\ldots+c_ky_{n-k},$$

I can get its characteristic equation, which is

$$r^k=c_1r^{k-1}+\ldots+c_k.$$

In particular for $y_n=cy_{n-1},$ I get $r=c.$ While I see that this obviously gives the right solution, something seems not right. For a differential equation $y'=cy,$ I get a similar characteristic equation: $r=c$, however, as I understand it, the the analogy between differential equations and recurrence relations is given by $y'\sim y_n-y_{n-1},$ not $y'\sim y_n.$ By this logic, I think the characteristic equation for the recurrence relation $y_n=cy_{n-1}$ should be $r=c-1,$ because the recurrence relation is equivalent to $y_n-y_{n-1}=(c-1)y_{n-1}.$ Could you help me understand why the analogy breaks down here (or why it doesn't)?

• The choice of $x$ to denote the characteristic value is unfortunate in that $y'$ is conventionally used to denote the derivative with respect to $x$. – joriki May 27 '13 at 9:29
• @joriki OK, I'll change it. I usually used $t$ for the argument of $y$. – Bartek May 27 '13 at 9:32
• In physics, differentiation with respect to $t$ is conventionally denoted by a dot over the letter denoting the function; I've seen that convention used on this site as well. – joriki May 27 '13 at 9:37

The idea behind using the characteristic equation to solve the recurrence relation is to postulate exponential solutions, $y_n=r^n.$ The roots of the characteristic equation, assuming none are multiple roots, then give a set of basis functions, and the general solution is a linear combination of these basis functions, $$y_n=\alpha_1r_1^n+\alpha_2r_2^n+\ldots+\alpha_kr_k^n.$$

The idea behind using the characteristic equation to solve the differential equation is similar. We postulate an exponential solution $y=e^{rx}.$ The roots of the characteristic equation, again assuming no multiple roots, give a set of basis functions, and the general solution is a linear combination of these basis functions, $$y=\alpha_1e^{r_1x}+\alpha_2e^{r_2x}+\ldots+\alpha_ke^{r_kx}.$$

Let's see how the two methods are related in your examples, $y_n=cy_{n-1}$ and $y'=cy.$

• For the recurrence we get $r=c,$ and therefore the general solution $y_n=\alpha c^n$.
• For the differential equation we also get $r=c.$ This gives the general solution $y=\alpha e^{cx}.$

Let's now solve a discrete approximation of the differential equation using the recurrence equation method. Approximating the derivative, we have $$\frac{y(x+\Delta x)-y(x)}{\Delta x}\approx cy(x).$$ If we discretize the $x$-axis, letting $x=n\Delta x,$ we get $$\frac{y((n+1)\Delta x)-y(n\Delta x)}{\Delta x}\approx cy(n\Delta x).$$ If we write $y_n$ for $y(n\Delta x),$ we get $$y_{n+1}-y_n\approx cy_n\Delta x$$ or $$y_{n+1}\approx(1+c\Delta x)y_n.$$ The quantity in parentheses plays the role of $c$ in the recurrence relation solved above. Adapting that solution gives $r=1+c\Delta x$ and therefore $$y_n\approx\alpha(1+c\Delta x)^n.$$ Since $\Delta x=x/n,$ this is the same as $$y_n\approx\alpha(1+cx/n)^n.$$ This is consistent with the exact solution to the differential equation since, for large $n,$ $(1+cx/n)^n$ is approximately $e^{cx}.$

• What do you mean by exponential solutions, y_n=r_n and basis vectors? I believe that the only differentiation operators, e.g. $\begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix}$, have exponential solutions, $r^n$ whereas no recurrent relation has such kind of matrix. Nevertheless, you have made a comprehensive answer to a important question and it seems to shed some light on the difference between s and z, the (continuous) Laplace variable and discrete time shift operator. – Val Dec 6 '13 at 0:52
• @Val: If you take the linear homogeneous recurrence in the original question, $y_n=c_1y_{n-1}+\ldots+c_ky_{n-k},$ and postulate a solution of the form $y_n=r^n,$ for some constant $r,$ then substitution gives $r^n=c_1r^{n-1}+\ldots+c_kr^{n-k}.$ Dividing by $r^{n-k}$ yields $r^k=c_1r^{k-1}+\ldots+c_k.$ This polynomial equation has $k$ roots, $r_1,\ldots,r_k.$ If these are distinct, then we have found $k$ different solutions to the recurrence, each of the form $y_n=r_j^n.$ But the recurrence is linear, so linear combinations of solutions are also solutions. – Will Orrick Dec 6 '13 at 10:36
• @Val: The space of solutions is $k$-dimensional since the $k$ values $y_0,\ldots,y_{k-1}$ determine the entire sequence $y_j.$ Any set of $k$ linearly independent vectors $[y_0,\ldots,y_{k-1}]$ is a basis for the space of solutions. If the roots of the polynomial equation are distinct, then the vectors they give rise to form such a set. – Will Orrick Dec 6 '13 at 10:36
• Thanks, it seems that I finally got the crucial point that I missed from the GStrang's Linear Algebra. I have created another question regarding the relationship between the difference operator and recurrences. Thank you appreciating that. – Val Dec 6 '13 at 22:45