Recurrences and recursive counting

Count a short climb by its final move

Starting at height zero, reach height three using moves of size one or two. Record their order. The possible lists are (1,1,1), (1,2) and (2,1): three outcomes. The lists (1,2) and (2,1) visit different intermediate heights, so they are different climbs.

A climb ending with a one-step move leaves a climb to height two when that last move is removed. A climb ending with a two-step move leaves a climb to height one. The two final-move cases cannot overlap, and every climb has one of these final moves.

There are two climbs to height two, namely (1,1) and (2), and one to height one, namely (1). Thus the height-three count is 2+1 = 3. We can count a larger problem using counts of smaller versions of the same problem.

Build a short table before solving a general formula

Revisit Counting, zero and natural numbers for the difference between no outcomes and one empty outcome. The lesson Addition and subtraction helps you combine disjoint cases. Use the lesson Formulas and rearranging simple relationships to replace a variable by a stated value while retaining the formula’s structure.

The earlier sum/product counting and proof-by-induction lessons develop useful methods. Here the needed ideas are explained locally: add only disjoint exhaustive outcome classes, and verify a proposed formula at the starting index and at every forward step. You can use these two ideas before studying their general proof methods.

On a first reading, follow the stair and binary-string tables through the initial cases. Return to closed formulas after practising substitution and distribution. The published lesson Exponent laws and power functions prepares geometric powers; it does not supply the counting partition.

A rule needs an index range and starting values

A sequence is an ordered list of values labelled by indices. Here indices are nonnegative integers: a₀,a₁,a₂,… . The subscript tells you the position; it is not a multiplier. Stating a₀ rather than a₁ changes which position is the starting point.

A recurrence relates a term to earlier terms. For example, aₙ = aₙ₋₁+3 for n ≥ 1 computes each next term after one initial value a₀ has been given. The rule alone does not determine the sequence: initial values 2 and 5 give different sequences under that same rule.

The order of a recurrence is the largest backward index shift used. The rule uₙ = uₙ₋₁+uₙ₋₂ for n ≥ 2 is second order and, in this form, needs u₀ and u₁. With these seeds, each new term is uniquely computed from terms already determined. This forward argument establishes both existence and uniqueness on the stated domain.

Do not apply the rule before its range. At n = 1 the second-order expression would request u₋₁, which has not been defined. Initial values supply the small cases where the general decomposition is unavailable.

Prove the stair recurrence with two reversible cases

Let uₙ count ordered lists of 1 and 2 with total n. There is one empty list of total zero, so u₀ = 1. There is one list of total one, (1), so u₁ = 1.

For n ≥ 2, partition all lists by their last move. Removing a final 1 maps its class to all lists of total n−1; appending 1 restores the original list. Removing a final 2 similarly gives all lists of total n−2, with appending 2 as the inverse.

The last-one lists are (1,1,1,1),(1,2,1),(2,1,1), coming from (1,1,1),(1,2),(2,1). The last-two lists are (1,1,2),(2,2), coming from (1,1),(2). Thus u₄ = u₃ + u₂ = 3 + 2 = 5.

These correspondences are one-to-one, the classes are disjoint, and they cover all lists. Consequently uₙ = uₙ₋₁+uₙ₋₂ for n ≥ 2. No division or assumption that the two classes have equal size is needed.

The table begins 1,1,2,3,5,8,13 for indices 0 through 6. In particular the five lists totalling four split into three ending in 1 and two ending in 2. A finite display checks that example; the reversible-case argument proves the rule for every stated n.

The same rule can count different objects or use different indices

Tile a strip of n unit cells with tiles of lengths one and two, without gaps or overlap. Reading tile lengths from left to right gives exactly a list of 1 and 2 with total n. Placing tiles with those lengths reverses the construction. Thus these strip tilings have count uₙ too, including one tiling of a length-zero strip.

Use the Fibonacci convention F₀ = 0, F₁ = 1 and Fₙ = Fₙ₋₁+Fₙ₋₂ for n ≥ 2. It gives 0,1,1,2,3,5,8,… . Our climb counts instead begin 1,1,2,3,5,8,… . Under this convention, uₙ = Fₙ₊₁, not Fₙ.

The shift holds at n = 0 and n = 1, and both sides then obey the same recurrence. A familiar sequence name never replaces the specified seeds and starting index. Different objects may share a recurrence without being identical outcomes.

A final 1 forces an earlier 0

Let bₙ count length-n binary strings with no adjacent 1’s. A string has labelled positions containing 0 or 1. The empty string, denoted ε, is one outcome, so b₀ = 1. Both length-one strings are allowed, so b₁ = 2.

For n ≥ 2, a valid string either ends in 0 or ends in 1. In the first case, remove the final 0; every valid length-(n−1) string can be extended by 0. In the second case, the preceding digit must be 0, so remove the final 01; every valid length-(n−2) string can be extended by 01.

Ending in 0 gives 000,010,100 from 00,01,10. Ending in 01 gives 001,101 from 0,1. The two cases are disjoint and cover all five strings: b₃ = b₂ + b₁ = 3 + 2 = 5.

Both constructions have inverse removal maps, preserve the restriction at the new boundary, and define disjoint exhaustive cases. Hence bₙ = bₙ₋₁+bₙ₋₂ for n ≥ 2. The counts begin 1,2,3,5,8,13,21, so bₙ = Fₙ₊₂ under our convention.

For length three, ending in 0 gives 000,010,100; ending in 01 gives 001,101. Merely saying “append 1 to any valid shorter string” is wrong: appending 1 to a string already ending in 1 creates a forbidden 11.

An empty construction is one completed outcome

The empty climb and empty string each contribute one initial outcome because nothing remains to be chosen. Their entries number zero, but their outcome collection has one member. A required positive-length string over an empty alphabet, by contrast, has no outcome.

Our stair count is defined only for n ≥ 0. Some extended formulas define negative-size counts as zero to simplify notation, but that is an additional convention. We use two direct initial cases and apply the stair recurrence only for n ≥ 2.

A problem with different restrictions can have different small cases. If moves of size one are forbidden, a total of one is impossible. Retaining u₁ = 1 after changing that rule would count an outcome the new problem does not allow.

Unfold first-order arithmetic and geometric rules

For real constants A and d, let a₀ = A and aₙ = aₙ₋₁+d for integers n ≥ 1. Reaching index n adds d exactly n times, giving aₙ = A+nd. This arithmetic formula also allows negative or zero d.

For real constants A and q, let a₀ = A and aₙ = q aₙ₋₁ for n ≥ 1. If q ≠ 0, repeated multiplication gives aₙ = A qⁿ for n ≥ 0. Negative q can alternate signs; it does not make the sequence undefined.

The adjacent table gives all six terms and both computations. Negative terms remain below the zero line. Differences, ratios and reset behaviour follow each panel’s stated rule, not the drawing’s slope alone.

If q = 0, retain a₀ = A separately and use aₙ = 0 for n ≥ 1. No value of 0⁰ is needed. If q = 1 the sequence is constant A. Inferring q from aₙ/aₙ₋₁ is permitted only when that denominator is nonzero.

A sequence plot contains samples at integer indices. Connecting dots can help the eye, but would not define between-index terms. Our plots therefore mark only the samples, with labelled linear scales and the zero line visible when terms are negative.

A constant extra term creates a finite geometric sum

Consider a₀ = A and aₙ = q aₙ₋₁+b for n ≥ 1, with real constants A,q,b. The extra b makes this nonhomogeneous when b ≠ 0: the rule adds an amount not obtained by multiplying earlier sequence values.

Unfolding gives a₁ = qA+b, a₂ = q²A+qb+b and a₃ = q³A+q²b+qb+b. For n ≥ 1, the general form is aₙ = qⁿA+b(1+q+…+qⁿ⁻¹). Each b contribution is multiplied once for each later step.

If q ≠ 1, multiplying the finite sum S = 1+q+…+qⁿ⁻¹ by q and subtracting S gives (q−1)S = qⁿ−1. Thus aₙ = qⁿA+b(qⁿ−1)/(q−1). For q = 0 and n ≥ 1 this reduces directly to aₙ = b; keep a₀ = A separately.

If q = 1, the displayed quotient has a zero denominator and must not be used. The original rule instead adds b at every step, so aₙ = A+nb. At n = 0 every case uses the stated seed; the unfolded sum has no contributions.

Adding n differs from adding a constant

For a₀ = A and aₙ = aₙ₋₁+n for n ≥ 1, unfolding adds 1, then 2, then 3, and so on. Therefore aₙ = A+(1+2+…+n).

Let S = 1+2+…+n. Write the same sum in reverse beneath it; each of the n aligned pairs sums to n+1. Hence 2S = n(n+1), so aₙ = A+n(n+1)/2. For n = 0 the empty sum is zero and the formula gives A.

This is a simple nonhomogeneous recurrence with an index-dependent extra term. Its varying increments are not a constant arithmetic difference. Check what the recurrence actually adds before borrowing a geometric or arithmetic formula.

A guessed formula becomes a proof when it satisfies both tests

A candidate closed formula must match every required initial value and satisfy the recurrence for every index in its range. Checking five listed values is a useful error check, but it cannot establish an infinite sequence formula.

For a₀ = 2 and aₙ = 2aₙ₋₁+1, the candidate aₙ = 3·2ⁿ−1 gives 2 at n = 0. If its expression is correct at n−1, the next value is 2(3·2ⁿ⁻¹−1)+1 = 3·2ⁿ−1. Thus correctness passes to the next index.

At n = 0, 3·2⁰−1 = 2. If aₙ₋₁ = 3·2ⁿ⁻¹−1, then 2aₙ₋₁+1 = 3·2ⁿ−1. The displayed terms 2,5,11,23,47 illustrate this verified rule.

Begin at the verified seed and repeat this implication to any finite target index. This is the local induction argument: there is no first later index where the formula can fail. For a second-order rule, verify both seeds and use both preceding expressions in the forward step.

A different sequence can share any finite starting display. For example, aₙ = n and cₙ = n+n(n−1)(n−2)(n−3) agree at n = 0,1,2,3, then differ at n = 4. A guessed pattern alone does not impose the recurrence on unobserved indices.

Not every relation determines the next value

For aₙ = q aₙ₋₁+b, backward recovery aₙ₋₁ = (aₙ−b)/q requires q ≠ 0. When q = 0, every starting value produces the same next value b, so knowing a₁ = b cannot recover a₀.

A relation such as aₙ² = aₙ₋₁ need not give a unique forward value over the real numbers. Starting from a₀ = 4, the first relation permits a₁ = 2 or −2; a rule selecting a sign would be extra information.

The relation aₙ = aₙ+1 is inconsistent. The relation aₙ = aₙ imposes no restriction. These are not useful forward recursive definitions. Check that each required next value exists uniquely, and that recursive dependencies actually lead to known initial data.

Reuse a computed subproblem without merging its outcomes

A direct recursive computation of u₄ requests u₃ and u₂. Computing u₃ requests u₂ again. Both calls ask the same numerical question, so u₂ can be stored once and reused. This storage is called memoization.

The exact u₄ call tree contains nine call nodes but only five distinct indices, 0 through 4. It counts five climb outcomes. These three quantities have different meanings; for u₅ they are 15 calls, six distinct indices and eight outcomes.

To compute u₄, request u₃ and u₂; u₃ requests u₂ and u₁; each u₂ requests u₁ and u₀. There are nine call nodes but only five different indices, zero through four. Both calls for u₂ return two; the five counted step lists remain distinct outcomes.

Repeated requests for u₂ are not double-counting in the outcome proof. Its smaller lists are extended in different final cases or larger prefixes, producing different full lists. The partition defines distinct counted objects; the call tree describes how a number is computed.

A bottom-up table starts with u₀,u₁, then stores u₂,u₃,… once each. It has the same values as correct recursion because every entry applies the same rule to the same seeds. A closed formula is another way to obtain those values after its proof; faster computation cannot repair an incorrect counting model.

Worked examples

Try it yourself

1. Compare u₀ = 1,u₁ = 1 with v₀ = 0,v₁ = 1 when both obey the previous-two sum rule for n ≥ 2. What are their index-three values?

   Show the answer and reasoning

   u₃ = 3, while v₃ = 2.

   Their index-two values are 2 and 1. Adding the corresponding preceding two terms gives 3 and 2. The recurrence alone does not fix the sequence.

2. Why is b₀ = 1 for strings without adjacent 1’s, and why is the final-01 case not used as the size-one definition?

   Show the answer and reasoning

   There is one empty string. Size one has the two direct outcomes 0 and 1; a final 01 requires at least two positions.

   The restriction is satisfied by the empty string. The recurrence starts at n = 2, so it does not request b₋₁ or lose the allowed singleton string 1.

3. For a₀ = 2 and aₙ = q aₙ₋₁, list indices 0,1,2,3 when q = −1 and when q = 0.

   Show the answer and reasoning

   For q = −1: 2,−2,2,−2. For q = 0: 2,0,0,0.

   A negative multiplier alternates signs here. A zero multiplier resets every positive-index term to zero while preserving the stated initial 2; no value of 0⁰ is required.

4. For a₀ = 7 and aₙ = q aₙ₋₁−2, find a₄ when q = 1 and describe all positive-index terms when q = 0.

   Show the answer and reasoning

   If q = 1, a₄ = 7−4·2 = −1. If q = 0, aₙ = −2 for every n ≥ 1; a₀ remains 7.

   The q = 1 rule adds −2 at each step and avoids division by q−1. The q = 0 rule erases the previous term; keep the index-zero seed separate.

5. May the total-three climbs be counted by adding “ends in 1” and “contains a 1” counts? Explain with one list.

   Show the answer and reasoning

   No. These classes overlap: (1,1,1) belongs to both.

   All three total-three climbs contain 1, while two end in 1. Adding 3+2 would count overlapping outcomes twice. Ending in 1 versus ending in 2 is the valid disjoint partition.

6. Does cₙ = 2ⁿ−1 solve a₀ = 2,aₙ = 2aₙ₋₁+1 for n ≥ 1?

   Show the answer and reasoning

   No. It satisfies the recurrence but gives c₀ = 0, not the required 2.

   The correct formula is 3·2ⁿ−1. Matching the forward equation without matching the initial value solves a different sequence.

7. If aₙ = 0·aₙ₋₁+3 for n ≥ 1 and a₁ = 3, can a₀ be recovered?

   Show the answer and reasoning

   No. Every real starting value a₀ gives a₁ = 3.

   The forward rule is unique after a seed is supplied, but the zero multiplier loses information. Dividing by q = 0 is not a valid backward step.

8. A naive previous-two recursive computation for u₅ uses 15 calls and six distinct indices. How many climb outcomes does it count, and what changes if each subproblem is stored once?

   Show the answer and reasoning

   It counts 8 climbs. Storing values avoids repeated computation; it does not reduce the 8 outcomes.

   The count is u₅ = u₄+u₃ = 5+3. Calls are computational requests, while outcomes are ordered move lists. Reusing a number preserves the counting partition.

What to carry forward

• Specify index domain, recurrence range and required seeds; a list of samples does not supply a general rule.
• Justify recursive counts with disjoint exhaustive cases and inverse smaller-outcome constructions.
• One empty outcome and zero outcomes differ; Fibonacci index shifts depend on the stated seeds.
• Unfolding derives simple formulas, with separate q = 0 and q = 1 cases where needed.
• Verify every initial value and the forward rule to prove a proposed sequence formula.
• Repeated calls, distinct stored subproblems and counted outcomes are different quantities.