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)?
 A: 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}.$
