- #1

- 1,754

- 650

This is not meant as a full introduction to recursion relations but it should suffice for just about any level of the student.

Most of us remember recursion relations from secondary school. We start with a number, say, 1. Then we add 3. That gives us 4. Now we that number and add 3 again and get 7. And so on. This process creates a series of numbers ##\{ 1, 4, 7, 10, \dots \}##. Once we get beyond that stage we start talking about how to represent these. Well, let’s call the starting number ##a_0##. Then the next number in the series would be ##a_1##, then ##a_2##, …, on to ##a_n## where n is the nth number in the series. We may now express our recursion as a rule: ##a_{n +1} = a_n + 3##, where ##a_0 = 1##.

We may go much further. We can talk about things like the Fibonacci series: ##F_{n + 2} = F_{n + 1} + F_{n}##, where ##F_1 = F_2 = 1##. This is the famous series ##\{ 1, 1, 2, 3, 5, 8, 13, \dots \}##. But what if we want a formula to find out what ##F_n## is for the nth number...

Continue reading...