Recurrence Relations

According to legend, the 19th century mathematician Gauss, when he was a
schoolboy, was asked by his teacher to add up all of the integers from 0 to
100. The idea was to keep Gauss busy for a while, but he almost immediately
gave the correct answer of 5050. Gauss had solved the problem not by doing the
obvious arithmetic, but by taking advantage of a clever insight into the
problem. This and many similar problems involving integers can be tackled by
setting up and solving recurrence relations.

In a recurrence relation, we express the solution to a problem involving a
large integer in terms of the solution to the same problem involving a smaller
integer. For example, suppose that we'd like to have a formula for the sum of
the first n integers. Gauss was using just such a formula to calculate that
the sum of the first 100 integers is 5050.

The key insight is this: the sum of the first n integers is just n plus the
sum of the first n-1 integers. In other words, if you want to know the sum
of the first 100 integers, just add up the first 99 integers and then add 100.
If S(n) stands for the sum of the first n integers, then

(1) S(n) = n + S(n-1)

These equations (1) and (2) are all that we need to figure out a formula for
calculating the sum of the first n integers. We can ask Mathematica to solve this
recurrence relation by using RSolve[ ] which comes with the
DiscreteMath Package.

Needs["DiscreteMath`RSolve`"]

Now used the on-line documentation (or the printed documentation on the Mathematica Packages) to learn about using the function RSolve []. For the case of Gauss's little problem we have:

sol=RSolve[{ s[n] == n +s[n-1] , 
s[0] == 0},s[n], n ]

What Mathematica prints out is a formula into which we can plug a value for n to
obtain the sum of the first n integers. Before we experiment with the
formula, let's simplify it. First, we extract the solution (we give the extracted part a new name since we want to use s[n] again later)

s1[n]=s[n]/. sol[[1]]

And now we ask Mathematica to simplify the solution.

Simplify[s1[n]]

Play around with the formula a bit before you continue by typing it in using
different values in place of n. You should be able to confirm Gauss' answer
to his teacher's question.

If you think about what we've just done, you'll realize that the creative part
of the problem solving process was setting up the recurrence relation. Once
we'd done that, Mathematica was able to do the rest of the work.

Try to come up with some recurrence relations of your own and get Mathematica to
solve them. Here are two examples to try out.