5
$\begingroup$

Yesterday there was a question here based on solving a recurrence relation and then when I tried to google for methods of solving recurrence relations, I found this, which gave different ways of solving simple recurrence relations.

My question is how do you justify writing the recurrence relation in its characteristic equation form and then solving for its roots to get the required answer.

For example, Fibonacci relation has a characteristic equation $s^2-s-1=0$.

How can we write it as that polynomial?

Improve this question
$\endgroup$
2
  • $\begingroup$ You'll want to see this... $\endgroup$ – J. M. isn't a mathematician Dec 14 '11 at 9:20
  • $\begingroup$ You can also look at this from the linear algebra viewpoint, since there is an equivalence between linear difference equations and the repeated multiplication of a Frobenius companion matrix with a vector. The characteristic polynomial of your matrix is the characteristic polynomial of your difference equation. $\endgroup$ – J. M. isn't a mathematician Dec 14 '11 at 9:24
6
$\begingroup$

The characteristic equation is the one that a number $\lambda$ should satisfy in order for the geometric series $(\lambda^n)_{n\in\mathbf N}$ to be a solution of the recurrence relation. Another interpretation is that if you interpret the indeterminate $s$ as a left-shift of the sequence (dropping the initial term and renumbering the renaming terms one index lower), then the characteristic equation gives the lowest degree monic polynomial that when applied to this shift operation kills all sequences satisfying the recurrence. In the case of Fibonacci recurrence, applying $s^2-s-1$ to a sequence $A=(a_i)_{i\in\mathbf N}$ gives the sequence $(a_{i+2}-a_{i+1}-a_i)_{i\in\mathbf N}$, which is by definition identically zero if (and only if) $A$ satisfies the recurrence.

A different but related polynomial that is of interest is obtained by reversing the order of the monomials (giving a polynomial starting with constant term $1$), so for Fibonacci it would be $1-X-X^2$. This polynomial $P$ has the property that the formal power series $F=\sum_{i\in\mathbf N}a_iX^i$ associated to a sequence satisfying the recurrence, when multiplied by $P$ gives a polynomial $R$ (with $\deg R<\deg P$), in other words all terms from the index $\deg P$ on are killed. This is basically the same observation as for the shift operation, but the polynomial $R$ permits describing the power series of the sequence, including its initial values, formally as $F=\frac RP$. For the Fibonacci sequence one finds $R=X$ so its formal power series is $F=\frac X{1-X-X^2}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ As far as I can understand, denominator P describes the system self-evolution while the nominator R has something to do with initial values (or other constraints also?). Can you confirm that and give keywords so that I could educate myself? I think that P is called a reciprocal of the characterisitic poly. $\endgroup$ – Val Jul 31 '13 at 13:55
  • $\begingroup$ @Val: As described in the second paragraph above, the polynomial $P$ corresponds to a linear recurrence that is satisfied (from some point onward) by the series$~F$. Given a sequence that ultimately satisfies some linear recurrence, this recurrence is not unique (you can multiply $P$ by any polynomial to get another recurrence) but taking $P$ of minimal degree and with constant coefficient $1$, it does become unique. The corresponding numerator $R$ is then simply the product $R=PF$, and as such it is indeed determined by an initial set of terms of (the sequence encoded by)$~F$. $\endgroup$ – Marc van Leeuwen Aug 1 '13 at 7:01
3
$\begingroup$

We aren't writing the Fibonacci relation as $s^2-s-1=0$, we are noting a relation between that equation and the Fibonacci relation. We are noting that if $r$ is a solution of the characteristic equation, then $r^n$ is a solution of the recurrence relation.

Improve this answer
$\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.