Generating Recursive Formulas from Non-Recursive Formulas

Introduction

Consider a sequence of numbers with a distinct pattern, such as

1, 4, 7, 10, 13, 16, 19, …

For this thought exercise, the sequence needs to be chosen with some purpose, rather than at complete random. When this is achieved, the sequence can be described by two types of formulas. For this specific example, those formulas take the following two forms:

S_n = 3n + 1

AND

S_n = S_{n-1} + 3 (with S_1 = 1)

Both formulas above help to describe the sequence we started with, but there is one significant difference between them. The first formula contains S_n but not S_{n-1}. What’s the significance of that? Well, to use the second formula, you need to know the value of the previous term in the sequence, which is what S_{n-1} represents. This may seem like a huge disadvantage, because the first formula requires no information about prior terms in the sequence. The second formula it comes with one perk to help compensate for its shortcomings though: it gives us intuition for how the terms of the sequence grow (or shrink) over time. For instance, the “+3” in the second formula indicates that each term is three more than the previous. It also says that the size of this change is the same; at every step, it is “+3”.

In general, formulas that look like the first one are called non-recursive formulas, and those that look like the second one…