Recursive Formula Calculator
Generate sequence terms from any recursive definition. Pick a preset like Fibonacci or factorial, or define your own first or second order recurrence. Shows up to 100 terms with partial sums and ratios.
F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
Closed form: F(n) = (phi^n - psi^n) / sqrt(5)
Sequence Terms (20)
| n | a(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
| 11 | 89 |
| 12 | 144 |
| 13 | 233 |
| 14 | 377 |
| 15 | 610 |
| 16 | 987 |
| 17 | 1,597 |
| 18 | 2,584 |
| 19 | 4,181 |
Sequence Summary
Terms Generated
20
First terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Common Patterns
Arithmetic:
a(n) = a(n-1) + d
Geometric:
a(n) = r * a(n-1)
Fibonacci-type:
a(n) = a(n-1) + a(n-2)
Linear recurrence:
a(n) = c1*a(n-1) + c2*a(n-2)
10 Preset Sequences
Fibonacci, Lucas, factorial, powers of 2, arithmetic, geometric, triangular, Catalan, Pell and Collatz ready to explore.
Custom Recurrences
Define first-order a(n) = c*a(n-1) + d + e*n or second-order a(n) = c1*a(n-1) + c2*a(n-2) + d with any coefficients.
Sums and Ratios
Toggle partial sums to see cumulative totals. Toggle ratios to watch convergence patterns like the golden ratio in Fibonacci.
Common Recursive Sequences
| Sequence | Recursive Formula | First Terms | Closed Form |
|---|---|---|---|
| Fibonacci | F(n) = F(n-1) + F(n-2) | 0, 1, 1, 2, 3, 5, 8, 13 | (phi^n - psi^n)/sqrt(5) |
| Factorial | n! = n * (n-1)! | 1, 1, 2, 6, 24, 120, 720 | n! |
| Powers of 2 | a(n) = 2*a(n-1) | 1, 2, 4, 8, 16, 32, 64 | 2^n |
| Triangular | T(n) = T(n-1) + n | 0, 1, 3, 6, 10, 15, 21 | n(n+1)/2 |
| Catalan | C(n) = (2(2n-1)/(n+1))*C(n-1) | 1, 1, 2, 5, 14, 42, 132 | (2n)!/((n+1)!n!) |
| Pell | P(n) = 2P(n-1) + P(n-2) | 0, 1, 2, 5, 12, 29, 70 | Involves 1+sqrt(2) |
How to Use the Recursive Formula Calculator
Recursive Formulas and Sequences: A Complete Guide
What Is a Recursive Formula?
A recursive formula (or recurrence relation) defines a sequence by expressing each term as a function of previous terms. Unlike an explicit formula that computes a(n) directly from n, a recursive formula builds the sequence step by step. You start with one or more initial values (base cases) and then apply the rule repeatedly to generate as many terms as you need.
The simplest example is an arithmetic sequence: a(n) = a(n-1) + d, where d is the common difference. Starting with a(0) = 2 and d = 3 gives the sequence 2, 5, 8, 11, 14, 17, and so on. Each term is 3 more than the previous one.
Recursive vs Explicit Formulas
Both representations define the same sequence, but they serve different purposes. A recursive formula is often easier to discover from a pattern. If you notice each term is double the previous one, you immediately write a(n) = 2*a(n-1). An explicit formula is better for computing a specific term directly. To find the 100th Fibonacci number with the recursive formula, you would need to compute all 99 terms before it. With the closed form (Binet's formula), you plug in n = 100 and get the answer in one step.
For linear recurrences with constant coefficients, there is a systematic method to find the closed form: solve the characteristic equation. For a(n) = c1*a(n-1) + c2*a(n-2), the characteristic equation is x^2 - c1*x - c2 = 0. The roots of this equation determine the closed form.
The Fibonacci Sequence
The Fibonacci sequence is the most famous recursive sequence. Defined by F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1, it produces 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on. The ratio of consecutive terms converges to the golden ratio phi = (1 + sqrt(5))/2, approximately 1.618034.
Fibonacci numbers appear throughout nature (sunflower spirals, pinecone scales, branching patterns), computer science (data structures, algorithms, complexity analysis), finance (technical analysis) and mathematics (number theory, combinatorics). The closed form is Binet's formula: F(n) = (phi^n - psi^n) / sqrt(5) where psi = (1 - sqrt(5))/2.
Applications of Recurrence Relations
- Algorithm analysis: The time complexity of recursive algorithms is often expressed as a recurrence. Merge sort satisfies T(n) = 2T(n/2) + n, which solves to T(n) = O(n log n).
- Dynamic programming: DP solutions are built on recurrence relations. The number of ways to climb n stairs taking 1 or 2 steps at a time follows the Fibonacci recurrence.
- Population modeling: The logistic map x(n+1) = r*x(n)*(1-x(n)) models population growth and is one of the simplest systems that exhibits chaos.
- Financial math: Compound interest follows a(n) = (1+r)*a(n-1), a geometric recurrence. Mortgage amortization and annuity calculations use similar recurrences.
- Combinatorics: Counting problems often lead to recurrences. The number of ways to tile a 2-by-n rectangle with dominoes satisfies the Fibonacci recurrence.
Solving Recurrences
For a second-order linear recurrence a(n) = c1*a(n-1) + c2*a(n-2), write the characteristic equation x^2 = c1*x + c2, or equivalently x^2 - c1*x - c2 = 0. If this has two distinct roots r1 and r2, the general solution is a(n) = A*r1^n + B*r2^n, where A and B are determined by the initial conditions. If there is a repeated root r, the solution is a(n) = (A + B*n)*r^n. This method always works for linear recurrences with constant coefficients.
Tips for Students
- Always clearly state the base cases. The recurrence alone does not define a unique sequence.
- Generate several terms by hand before writing the formula. Seeing the pattern makes the rule obvious.
- Check your formula by verifying it produces the known terms. Off-by-one errors are common.
- For homework, show the first 5 to 10 terms computed step by step to demonstrate you understand the process.