| n | an |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
A linear recurrence of order k is defined by:
a_n = c1·a_{n-1} + c2·a_{n-2} + … + ck·a_{n-k} + b
- Iteration computes terms sequentially from the seeds.
- Matrix powering uses a companion matrix to jump to a(n) in O(k3 log n).
- The characteristic polynomial (homogeneous part) is: x^k − c1·x^{k-1} − … − ck.
- Choose the order k and target index n.
- Enter coefficients c1..ck for the recurrence.
- Enter the first k starting values (seeds).
- Optional: add a constant term b and/or a modulus.
- Press Submit to see results above the form.
- Use the CSV/PDF buttons to download your table.
1) What is a linear recurrence?
It defines each term as a fixed linear combination of earlier terms, plus an optional constant. You set the order, coefficients, and initial seeds, then compute any future term.
2) What do “order k” and “seeds” mean?
Order k means each new term uses the previous k terms. Seeds are the first k starting values that anchor the sequence and make the recurrence produce a unique result.
3) When should I use matrix powering?
Use it when n is very large. It computes a(n) quickly using exponentiation by squaring, without generating every intermediate term one-by-one.
4) What does the modulus option do?
It reduces every operation modulo m, keeping numbers bounded and fast. This is common in programming contests, cryptography exercises, and large-index sequence checks.
5) Can I use negative coefficients or seeds?
Yes. Negative inputs work in both normal arithmetic and modulo arithmetic. For modulus mode, results are normalized into the range 0..m−1.
6) Why does the table sometimes show only part of the sequence?
For large n, printing every term is heavy and not very useful. The calculator summarizes early terms and the last terms, while still computing a(n) correctly.
7) What is the characteristic polynomial used for?
It describes the homogeneous recurrence structure. Its roots relate to closed-form solutions and long-run behavior, such as growth rate and oscillation patterns.
8) My integers look inaccurate for big n. Why?
Without a modulus or an exact big-integer extension, very large values can overflow native integers or lose precision as decimals. Use a modulus for huge n, or enable BCMath for exact integer runs.