18
$\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?

  • 1
    Put $U_n=x^n$ in your original equation.2012-07-04
  • 0
    ^ and then factor out the common powers of $x.$2012-07-04
  • 0
    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.2012-07-04
  • 2
    Possible duplicate of [Characteristic equation of a recurrence relation](https://math.stackexchange.com/questions/91379/characteristic-equation-of-a-recurrence-relation)2018-07-24

5 Answers 5

28

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.

  • 1
    What justifies such a conversion? That is from $U_n$ to $U^n$ (treating the terms like powers)?2016-09-11
  • 0
    @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.2016-09-11
  • 0
    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.2016-09-11
  • 0
    @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?2016-09-11
  • 3
    Yes, exactly. Is there a proof?2016-09-12
  • 0
    @Airdish: It’s not hard to show **that** it works: one shows by induction that the closed form obtained from the roots satisfies the recurrence. To show that every solution is of that form one uses the fact that the set of sequences is a vector space, and the set of solutions to the homogeneous recurrence is a subspace whose dimension is the order of the recurrence (since that’s the number of values that need to be specified to determine the specific sequence). The set of general solutions from the roots is a subspace of the right dimension, so it must be the right subspace. The induction ...2016-09-12
  • 0
    ... proof, at least for second-order recurrences, can be found in most of the sophomore level discrete math texts from which I’ve taught; the linear algebra part cannot, but it’s easy once one knows some linear algebra. Seeing **why** it works, or where the idea came from, is harder. It falls out quite naturally from manipulation of generating functions to get closed forms. At perhaps an even more abstract level it falls out naturally from the approach taken in Bill Dubuque’s answer below.2016-09-12
  • 0
    Ah, I guess the proof is beyond me at this point. I hope I can learn it later on though. Thank you.2016-09-12
  • 0
    @Airdish: You’re welcome.2016-09-12
18

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.

  • 0
    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.2016-08-04
  • 1
    @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.2016-08-04
  • 0
    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.2016-08-04
  • 0
    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.2016-08-04
  • 3
    @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.2016-08-04
  • 0
    What is the connection between this method and the characteristic polynomials for differential equations? I'm guessing instead of the shift operator we have the differential operator $L$, but what does "factoring" $L$ give you in that case?2017-03-19
  • 0
    And is there also a connection between solving recurrence relations using this characteristic polynomial method and using generating functions?2017-03-19
  • 0
    @1110101001 Yes, the analogous operator-theoretic approach also works in th differential case.2017-03-19
4

"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.

3

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.

0

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.