21
$\begingroup$

In my book, this succession defined by recurrence is presented:

$$U_n=3U_{n-1}-U_{n-3}$$

And it says that the characteristic equation of such is:

$$x^3=3x^2-1$$

Honestly, I don't understand how. How do I get the characteristic equation given a succession?

$\endgroup$
4
  • 1
    $\begingroup$ Put $U_n=x^n$ in your original equation. $\endgroup$ – Artem Jul 4 '12 at 20:26
  • $\begingroup$ ^ and then factor out the common powers of $x.$ $\endgroup$ – user2468 Jul 4 '12 at 20:27
  • $\begingroup$ You can take a route via generation functions - which shows why it all works. Or you can see that you have a linear equation which is defined by specifying two values, and see that the quadratic gives you two linearly independent functions, and therefore the procedure works. Generating function technology deals with exceptional cases rather better. $\endgroup$ – Mark Bennet Jul 4 '12 at 21:03
  • 2
    $\begingroup$ Possible duplicate of Characteristic equation of a recurrence relation $\endgroup$ – Xander Henderson Jul 24 '18 at 20:24
33
$\begingroup$

Here’s a rote rule for doing so. Start with the recurrence:

$$U_n=3U_{n-1}-U_{n-3}$$

Convert each subscript to an exponent:

$$U^n=3U^{n-1}-U^{n-3}$$

Change the variable to the one that you want to use in the characteristic equation:

$$x^n=3x^{n-1}-x^{n-3}$$

Divide through by the smallest exponent, in this case $n-3$:

$$x^{n-(n-3)}=3x^{(n-1)-(n-3)}-1\;,$$

which simplifies to $$x^3=3x^2-1\;.$$

With a little practice you can do the conversion in one go. For instance, the recurrence $$a_n=4a_{n-2}-6a_{n-3}+3a_{n-4}$$ has characteristic equation $$x^4=4x^2-6x+3\;,$$ as you can check by following through the steps given above.

$\endgroup$
10
  • 2
    $\begingroup$ What justifies such a conversion? That is from $U_n$ to $U^n$ (treating the terms like powers)? $\endgroup$ – Airdish Sep 11 '16 at 3:37
  • 1
    $\begingroup$ @Airdish: Converting to powers in this way, changing the variable, and dividing out the smallest power obviously produces the characteristic equation; that’s just basic algebra. Since the OP seemed to be having trouble with the actual mechanics, I gave this as a simple, mechanical procedure to do just that. $\endgroup$ – Brian M. Scott Sep 11 '16 at 17:51
  • $\begingroup$ Sorry, I think you misunderstand. I don't mean to attack your answer in any way. I have a genuine doubt about how the recurrence relations is transformed into the characteristic equation, or rather what justifies the transformation. $\endgroup$ – Airdish Sep 11 '16 at 17:55
  • $\begingroup$ @Airdish: Let me see if I understand correctly: essentially you want to know why the roots of the characteristic equation, obtained in the usual way, determine the solutions to the linear homogeneous recurrence? $\endgroup$ – Brian M. Scott Sep 11 '16 at 18:02
  • 3
    $\begingroup$ Yes, exactly. Is there a proof? $\endgroup$ – Airdish Sep 12 '16 at 12:38
22
$\begingroup$

Often one sees much handwaving here: rote rules, guesses, etc. But the conceptual background is very simple. Let $\rm\,S\,$ be the linear $\,n$-shift operator $\rm\:S\, u_n = u_{n+1}.\,$ In operator form we have

$$\begin{align} \rm 0\, &=\,\rm u_{\large n+3} - 3\, u_{\large n+2} + u_{\large n}\\[.2em] &=\,\rm S^{\large 3} u_{\large n} - 3\, S^{\large 2} u_{\large n} + u_{\large n}\\[.2em] &=\rm (\underbrace{S^{\large 3}\ \ -\ \ 3\,S^{\large 2} +\, 1}_{\rm\Large f(S)})\, u_{\large n}\\ \end{align}\quad$$

Factoring $\rm\,f(S) = (S-c_1)\,(S-c_2)\,(S-c_2)\,$ for $\rm\, c_j\in \mathbb C,\,$ reduces to solving linear recurrences $\rm\: (S-c)\,u_n = 0,\:$ i.e. $\rm\,u_{n+1} = c\,u_n,\,$ so $\rm\:u_n = u_o c^n.\,$ Because the $\rm\,c_j,\:$ are independent of $\rm\,n\,$ the operators $\rm\, S-c_j\:$ commute, so if the roots $\rm\,c_j\,$ are distinct, this yields three solutions $\rm\,c_j^n.\,$ Simple linear algebra (using the Casoratian) shows that these three solutions span the solution space.

Same for LDEs: $\rm\ D\!-\!ax\,$ kills $\,\rm e^{ax}$ so $\,\rm (D\!-\!i)(D\!+\!i) = D^2\!+\!1\,$ kills $\,\rm (e^{ix}\!+\!e^{-ix})/2=\cos(x)\,$

and $\rm\,S\!-\!x,\, S\!-\!y\,$ kill $\,\rm x^n,y^n$ so $\,\rm(S\!-\!x)(S\!-\!y) = S^2\! -\! (x\!+\!y) S\! +\! xy\,$ kills $\,\rm x^n+y^n =: f_n,\ $ i.e. $\rm \,f_{n+2}-(x\!+\!y)\,f_{n+1}+xy\, f_n = 0$.

Thus the characteristic polynomial is simply the polynomial $\rm\,f(S)\,$ or $\rm\,f(D)\,$ obtained from writing the difference / differential equation in operator form, and the form of the solutions follows immediately from factoring the characteristic polynomial. This reduces the solution of an $\rm\,n$-th order constant coefficient equation to the solution of $\rm\,n\,$ first-order constant coefficient equations.

Remark $\ $ The above depends crucially on the fact that the coefficients $\rm\,c_j\,$ are constant, i.e. independent of $\rm\,n,\,$ so they commute with $\rm\,S,\,$ i.e. $\rm\, Sc = cS\ $ (vs. $\rm\,Sc_{\large n} = c_{\large \color{#c00}{n+1}}S;\,$ $\rm Dc = c D+\color{#c00}{c'} 1)$. This property is what allows us to faithfully map the factorization of the characteristic polynomial $\rm\,f(x)\,$ into the same factorization for $\rm\,f(S),\, $ i.e. polynomial arithmetic assumes that $\,\rm x\,$ commutes with all coef's $\rm\,c_j,\,$ e.g $\rm\,x^2-c^2 = (x-c)(x+c)\iff cx = xc.\ $ The proof that the factorization of $\rm\,f(x)\,$ is true depends only on the ring axioms and the fact that $\rm\,x\,$ commutes with the coefficients, so the proof will persist in any ring where such constant commutativity persists. See this answer for further discussion from the viewpoint of the universal property of polynomial rings.

The same sort of sort of reduction works for any product of linear operators that commute.

$\endgroup$
8
  • $\begingroup$ Rote rules, while certainly not ideal, are not handwaving; this 'very simple' conceptual background will be altogether opaque to most students encountering these recurrences in a typical sophomore level discrete math course; and this, though a nice addition for those in a position to benefit from it, doesn't actually answer the question that was asked. $\endgroup$ – Brian M. Scott Aug 4 '16 at 22:23
  • 2
    $\begingroup$ @Brian I have no idea why you think that it doesn't answer the question. The mathematics is quite simple and should be accessible to anyone who has done analogous manipulation of linear differential operators in calculus, Generally I am always happy to elaborate if anyone has questions. $\endgroup$ – Bill Dubuque Aug 4 '16 at 22:47
  • $\begingroup$ You do realize, I hope, that a great many students -- quite possibly a majority -- encountering this material in a typical sophomore level discrete math class have not seen the analogous manipulation of elementary differential operators, has not taken a differential equations or linear algebra course, and may not have had more than a bare bones business calculus course. Your answer gives information from which a sufficiently sophisticated reader can deduce the answer to the question, but the way the question was asked strongly suggests that the OP is not such a reader. $\endgroup$ – Brian M. Scott Aug 4 '16 at 22:54
  • $\begingroup$ I will admit that I probably wouldn't have bothered to comment (or even have seen your answer) had I not happened to notice that some silly person had downvoted mine this afternoon and been mildly annoyed by such foolishness. $\endgroup$ – Brian M. Scott Aug 4 '16 at 23:03
  • 3
    $\begingroup$ @Brian Yes, of course I realize that it may be beyond the level of some readers. But I don't let that stop me from making remarks that might prove illuminating to others. When I was a student, analogous remarks like that - just beyond my knowledge level - often piqued my curiosity, and served to plant the seeds of ideas that later came to fruition. $\endgroup$ – Bill Dubuque Aug 4 '16 at 23:08
5
$\begingroup$

"Guess" that $U(n) = x^n$ is a solution and plug into the recurrence relation:

$$ x^n = 3x^{n-1} - x^{n-3} $$

Divide both sides by $x^{n-3}$, assuming $x \ne 0$:

$$ x^3 = 3x^2 - 1 $$

Which is the characteristic equation you have.

$\endgroup$
3
$\begingroup$

Given a recurrence, $$a_{n+j+1} = \sum_{k=0}^{j} c_k a_{n+k}$$ Take $a_n = x^n$. Then the characteristic equation is $$x^{n+j+1} = \sum_{k=0}^{j} c_k x^{n+k}$$ which gives us the characteristic equation $$x^{j+1} - \sum_{k=0}^{j} c_k x^k = 0$$ This is analogous to taking $y = e^{mx}$ when we solve linear differential equations.

$\endgroup$
0
$\begingroup$

For a difference equation one always expect a non-trivial solution of the form $U_n=x^n$. The choice of such $U_n$ is due to the facts that:

$a$. The successive differences of it are multiples of it i.e. $U_n+1=x.x^{n+1}=x.U_n$, etc., so that you can easily get a polynomial equation.

$b$. It is a non-zero discrete numeric function.

Now it all remains to plug this in your equation and you will get the required equation.

$\endgroup$

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.