Take the 2-minute tour ×

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|improve this question

1 Answer 1

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

share|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


