Recurrence: How to Describe Tomorrow Using Today

There are two ways to describe a sequence of numbers. You can give the direct formula for the term you want, or you can give a starting point and a rule that builds each new term from the ones before it. That second way, the rule that reaches backward, is recurrence, and it is one of the most quietly powerful ideas in all of math. The present branches into the next step, and the next, and the next, until a whole sequence unfolds from almost nothing.

What a recurrence actually is

A sequence is defined by recurrence when each term depends on one or more earlier terms. Instead of a closed formula, you are handed the seeds and the growing rule. The classic tiny example is a sequence where every term is the previous one plus three:

From those two lines the whole sequence pours out. Two, then five, then eight, then eleven, forever. You never needed a formula for the hundredth term to start walking toward it, you only needed where to begin and how to step. That is the entire mindset shift: describe the change, not the destination.

The number of earlier terms a rule reaches back to is called the order of the recurrence. If a term depends only on the one right before it, the recurrence is first order. If it depends on the two before it, like Fibonacci, it is second order. Three before it, third order, and so on. Order is just how far back you have to look to take one step forward, and it tells you how many seeds you need to plant before the rule can grow anything.

I like to picture it as the image at the top of this post. The present sits on the left, and from it a fan of possible next steps branches outward. A recurrence is the rule that decides which branch you take, over and over, so that a single starting state grows into an entire future. Change the seeds or change the rule, and a completely different sequence blossoms from the same machinery.

The reason this shows up everywhere is that the real world rarely hands you a closed formula. It hands you a state and a rule for change. Money in an account depends on last month plus interest. A population depends on last year plus births. Your position in a game depends on the previous frame plus velocity. All of these are recurrences wearing everyday clothes, which is why learning to think in steps pays off far outside a math test.

The two friendly patterns

Most recurrences you meet in school, and a surprising number in life, collapse into one of two familiar shapes once you look closely. The first is the arithmetic progression, where you add the same amount every step:

That constant $r$ is called the common difference, and because you add it once per step, after $n-1$ steps from the start you can jump straight to any term:

That is the magic moment in a lot of recurrence problems, when the step-by-step rule suddenly folds into a direct formula. Now you do not have to walk a hundred steps to reach the hundredth term, you can teleport there. Recognizing that a messy recurrence is secretly an arithmetic progression is often the whole solution.

The second pattern is the geometric progression, where instead of adding you multiply by the same factor each step:

That factor $q$ is the common ratio, and this is the shape of anything that grows or shrinks by a percentage: compound interest, a rumor spreading, a radioactive sample fading, a savings account doubling. Addition gives you steady, straight-line growth. Multiplication gives you the explosive curve that surprises everyone who expected a straight line. Half of financial intuition is just knowing the difference between these two.

So a good first move with any unfamiliar recurrence is to compute a few terms and ask a simple question: is the difference between consecutive terms constant, or is the ratio constant? If the difference holds steady you have an arithmetic progression, if the ratio holds steady you have a geometric one, and in either case a clean formula is waiting. Testing the first handful of values is not cheating, it is how you spot the pattern hiding in the rule.

Deriving the general formula, one subtraction at a time

Rules are nice, but the real prize is turning a step-by-step recurrence into a direct formula you can evaluate anywhere. Let me actually derive one, slowly, on a concrete arithmetic progression so you can see the machinery. Take the sequence

and let us find four different formulas for its terms, each one built by writing relations and then subtracting, dividing or factoring. Every route lands on the same sequence, which is exactly the point.

Route one: telescoping the seeds. Write the single step for every index and stack the equations on top of each other:

Now add all $n-1$ of them at once. On the left, every interior term cancels with its neighbor, $-a_2$ kills $+a_2$ and so on, which is why this is called telescoping. What survives is only the outermost pair:

For our numbers that is $a_n = 3 + 4(n-1) = 4n - 1$, and a quick check gives $a_5 = 19$, exactly right. That is the general formula, deduced rather than memorized.

Route two: from any two terms, by dividing. The same telescoping between two arbitrary indices $k$ and $n$ gives $a_n = a_k + (n-k)\,r$. If you happen to know two terms and want the step, just divide it out:

So any two terms, anywhere in the sequence, pin down the whole thing. Give me $a_4 = 15$ and $a_9$ and I can recover $r$ by a single division, then jump to any term I like.

Route three: guess the shape, solve the coefficients. Because an arithmetic progression grows linearly, assume the closed form is a straight line, $a_n = A\,n + B$, and pin the unknowns from the first two terms:

Subtract the top equation from the bottom one and the $B$ vanishes, factoring the system down to a single unknown: $A = a_2 - a_1 = r$. Back-substitute into the first line for the other: $B = a_1 - A = 2a_1 - a_2$. So the coefficients are expressed entirely from the terms you were given:

Plugging in $a_1 = 3$ and $a_2 = 7$ gives $A = 4$ and $B = -1$, so $a_n = 4n - 1$ once more. This is the trick of naming what you want, writing what you know, and subtracting to isolate it, and it works far beyond straight lines.

Route four: from the last terms, no first term needed. Sometimes you do not know where the sequence started, only its recent values. Since consecutive differences are all equal, two neighboring steps must match:

Move everything to one side and factor, and you get a rule that walks forward using only the last two terms:

Each term is twice the previous minus the one before it, which is just the statement that the second difference is zero. Give me the last three terms $11, 15, ?$ and I get $a_n = 2(15) - 11 = 19$ without ever touching $a_1$.

There is a graceful cousin of that last one worth keeping. Writing $a_{k-1} = a_k - r$ and $a_{k+1} = a_k + r$ and adding them makes the $r$ cancel, leaving the cleanest fingerprint of an arithmetic progression:

Every term is the exact average of its two neighbors. Four formulas, plus this bonus, all describing the same humble sequence. Whether you start from the seeds, from any two terms, from a guessed shape, or from the tail end, the same handful of moves, subtract, divide, factor, keeps handing you back the general term. That is what deriving a formula really is: not conjuring it, but cornering it until it has nowhere left to hide.

Fibonacci and the trick of subtracting relations

Not every recurrence is that tame, and the most famous stubborn one is Fibonacci, where each term is the sum of the two before it:

Compute a few and the sequence introduces itself: one, one, two, three, five, eight, thirteen, twenty-one. It is second order, so it needs two seeds, and it refuses to be a plain arithmetic or geometric progression, because it is a blend of both ideas at once. This is where school teaches a genuinely useful technique.

The trick is to write the recurrence for two neighboring indices and subtract one from the other. Often the awkward terms cancel and a simpler relationship falls out. It does not turn Fibonacci into a one-line difference, but it reshapes the dependency and reveals structure you could not see before. Subtracting successive relations is one of those moves that feels like a magic trick the first time a stubborn problem gives way to it.

For the curious, Fibonacci does have a closed formula, Binet's formula, and it is startling because it is built entirely from irrational numbers yet always lands on a whole number:

That $\varphi$ is the golden ratio, the same proportion people chase in art and architecture, and here it is falling out of a rule about adding rabbits. I find that connection quietly beautiful: a plain counting rule, followed far enough, secretly contains one of the most admired numbers in history. In practice, though, most problems are solved with the recurrence and its transformations, not this formula, because the step-by-step view is easier to reason about and to code.

From formula to fast code

Here is where the mathematician and the programmer have to shake hands, because the most natural way to write Fibonacci in code is also a trap. Translating the recurrence directly gives you a function that calls itself twice:

long long fib_slow(int n) {
    if (n <= 2) return 1;
    return fib_slow(n - 1) + fib_slow(n - 2);
}

It is elegant, it reads exactly like the math, and it is disastrously slow. To find one term it recomputes the same smaller terms over and over, branching into a huge tree of repeated work. Ask it for the fiftieth Fibonacci number and it makes billions of calls, most of them redundant. The rule was fine, the way we walked it was the problem.

The fix is to stop reaching backward and start moving forward, carrying only the two most recent terms and stepping ahead one at a time:

long long fib_fast(int n) {
    long long a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

Same sequence, same math, but now it takes a single clean pass and remembers nothing it does not need. This is the same lesson from every corner of computing: recursion often mirrors the math most faithfully, while a loop that carries just enough state does the same job far faster. Knowing when to trade the pretty version for the practical one is a real skill.

There is even a neat classic exercise buried here, which the recurrence itself invites: printing a sequence from its last term back to its first without storing the whole thing in an array. It sounds fiddly, but a recurrence gives you exactly the relationship between neighbors you need to walk backward on the fly. It is a small puzzle that teaches a big habit, using the structure of the rule to avoid wasting memory.

Conclusion

Recurrence is the humble art of describing tomorrow using today. Give a sequence its starting seeds and a rule for change, and it grows itself, one branch at a time, from the present into a whole future. Most of the tame ones turn out to be arithmetic or geometric progressions in disguise, foldable into clean formulas the moment you recognize the pattern.

The deeper reward is the way of thinking. When you learn to describe change instead of chasing final answers, sequences, growth, interest and even a little golden ratio all start to look like the same friendly idea. And when you carry that thinking into code, you learn to respect the difference between a rule that is correct and a walk through it that is wise. Describe the step well, choose how you take it carefully, and the whole future unfolds on its own.