Recursive rules

A recursive rule says how to get each term from the earlier ones, plus where to start. For 1, 4, 7, 10, 13, …: t₁ = 1 and tₙ = tₙ₋₁ + 3 for n ≥ 2. (tₙ₋₁ just means 'the term before'.)

Explicit or recursive?

• explicit: jump straight to any term from its position;
• recursive: walk step by step from the start. You must know the earlier terms to use it.

Example 3. u₁ = 1, uₙ = 2uₙ₋₁ + 3 gives 1, 5, 13, 29, 61, 125, 253, …. It jumps from 125 to 253, so 133 is not a term.

Example 4. s₁ = 3, sₙ = sₙ₋₁ × (sₙ₋₁ – 1) gives 3, 6, 30, 870: it grows very fast.

A rule can use two earlier terms. The Virahānka–Fibonacci sequence: V₁ = 1, V₂ = 2, Vₙ = Vₙ₋₁ + Vₙ₋₂: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …. Each term is the sum of the two before.

Virahānka wrote it down in the 7th century CE while studying the rhythms of Prakrit poetry. Gopāla (c. 1135) and Hemachandra (c. 1150) studied it too, before Fibonacci (c. 1200).