5
$\begingroup$

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)?

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ – joriki May 27 '13 at 9:29
  • $\begingroup$ @joriki OK, I'll change it. I usually used $t$ for the argument of $y$. $\endgroup$ – Bartek May 27 '13 at 9:32
  • $\begingroup$ 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. $\endgroup$ – joriki May 27 '13 at 9:37
7
$\begingroup$

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}.$

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Val Dec 6 '13 at 0:52
  • $\begingroup$ @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. $\endgroup$ – Will Orrick Dec 6 '13 at 10:36
  • $\begingroup$ @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. $\endgroup$ – Will Orrick Dec 6 '13 at 10:36
  • $\begingroup$ 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. $\endgroup$ – Val Dec 6 '13 at 22:45

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.