Recurrence relation
A recurrence relation is a relation between an entry in a sequence of numbers or other mathematical objects and preceding entries in the sequence.
For example, assume that you put 100 dollars on a bank account and that the bank pays you 6% interest every year. After one year, you will have the original 100 dollars plus 6 dollars interest, which makes 106 dollars. After two years, you have $ 112.06 (the 106 dollars you have after one year, plus 6% of $ 106 interest). The amount you have in your account grows according to the sequence 100, 106, 112.06, 118.18, …. This sequence is defined by the rule that every year you have the same amount as the previous year plus 6% of what you had the previous year. This is a recurrence relation in words. However, recurrence relations are usually formulated as a mathematical formula. As a first step, we can rewrite the rule as: in year n + 1, you have the same amount as in year n plus 6% of what you had in year n. Now, introduce the symbol an to stand for the amount in the account in year n. Then, the recurrence relation becomes an+1 = an + 0.06an.