Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Put $U_n=x^n$ in your original equation. –  Artem Jul 4 '12 at 20:26
    
^ and then factor out the common powers of $x.$ –  user2468 Jul 4 '12 at 20:27
    
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. –  Mark Bennet Jul 4 '12 at 21:03

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer

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

$$\rm 0 = U_{n+3} - 3\, U_{n+2} + U_n = S^3 U_n - 3\, S^2 U_n + U_n = (S^3 - 3\,S^2 + 1)\, U_n = f(S)\, U_n$$

Factoring $\rm\,f(S) = (S-c_1)\,(S-c_2)\,(S-c_2),\,$ for $\rm\, c_i\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_i,\:$ are independent of $\rm\,n\,$ the operators $\rm\, S-c_i\:$ commute, so if the roots $\rm\,c_i\,$ are distinct, this yields three solutions $\rm\,c_i^n.\,$ Simple linear algebra (using the Casoratian) shows that these three solutions span the solution space.

Thus the characteristic polynomial is simply the polynomial $\rm\,f(S)\,$ obtained from writing the recurrence in operator form, and the form of the solutions follows immediately from factoring the characteristic polynomial, which reduces the solution of an $\rm\,n$-th order constant coefficient recurrence to the solution of $\rm\,n\,$ first-order constant coefficient recurrences.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.