Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there some standard way to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?

For example, I might want to approximate

$$ a_{n+k}=a_{n+k-1}+a_{n+k-2}+...+a_n $$

with a geometric series

$$ b_{n+1}=qb_n $$

using some standard method.

I'd like to estimate the series when the root of the characteristic equation is difficult to find or doesn't have an analytic solution.

share|cite|improve this question

In your example, take $q$ to be the number $q\gt1$ satisfying $q^k=q^{k-1}+q^{k-2}+\cdots+1$.

share|cite|improve this answer
I was just using that as an example, in some cases it might be possible to find what $q$ really is. – Tianyang Li Sep 20 '12 at 6:14
You can always find out, in any particular example, what $q$ is. It's the modulus of the largest (in modulus) zero of the characteristic polynomial of the recurrence. Things work out nicest when there is a unique zero of greatest modulus, but even when there's a tie the general result still holds. – Gerry Myerson Sep 20 '12 at 6:58

Your Answer


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.