This post is the second in a series. The first is here. Recap: I promised a tour of some interesting features of the Mathematica programming language (which I’ll call mma). The first post was by way of introduction. The plan for this post is to introduce just enough notation to define some functions in mma, and then we’ll solve a real problem. One with a remarkable solution. I encourage the reader to explore this problem using his or her favorite programming language.

A central task in functional programming to apply a function f to an argument x. Mma offers several notations for doing so. I’ll illustrate the two I commonly use. By far the most common way to write f applied to x is

f[x]

Notice the use of square brackets, not parentheses. In mma, parentheses are only used to control operator precedence. The most common alternative to f[x] is

f @ x

This form is nice when chaining a series of functional applications. It is easier to write h @ g @ f @ x than h[g[f[x]]]. Note that the spaces are optional; I could have written h@g@f@x.

Before we start to apply functions, chances are we’ll want to define some. I’ll define a couple of example functions, double and recip. Their meaning should be plain enough.

double[x_] := 2 * x
recip[x_] := 1/x

Note the underscore following the parameter. It needs to be there. I’m not going to explain why yet; I’d rather get to something else first. For now just go with it.

Functional languages generally put a lot of stock in working with lists. Mma is no different; lists abound. In mma lists are delimited by curly braces, and have comma separated values. Here is a list of integers {2, 3, 7, 13}. The handy builtin function Range generates lists of integers. For instance, Range[1, 3] returns the list { 1, 2, 3 }. One more bit of notation and we are ready to go. Here is one way to map the function f over the elements of a list.

recip /@ Range[1, 3]

The value of the expression above is {recip[1], recip[2], recip[3]} which is to say { 1, 1/2, 1/3 }.

For the problem I have chosen the very first homework exercise in Concrete Mathematics, by Graham, Knuth, and Patashnik. Great book, btw. The problem is to solve a recurrence. What that means is that you are given a recursive definition of how to compute the terms of a sequence. The problem is to figure out an explicit formula for the nth term. Don’t be put off by the math. You have probably already seen recurrences, even if they weren’t called recurrences. Here’s an easy one, as a warm up.

T0 = 1
Tn = 2 Tn-1

Notice the form of the problem. The first equation is a boundary value which acts as a stopping condition on the recursion described by the second equation. So what does it mean to solve the recurrence? We have to provide an explicit formula for the nth term. A bit of thought will convince you that the solution is

Tn = 2 n

Knuth et alia proposed a slightly harder recurrence. Here it is.

T0 = a
T1 = b
Tn = (1+Tn-1)/Tn-2

So how do you even start to solve such a thing? The natural thing to do is to generate the first few terms of the sequence, to see whether we can spot a pattern. We’ll let mma do the heavy lifting. Here’s the code.

t[0] := a
t[1] := b
t[n_] := (1 - t[n - 1])/t[n - 2]

Well that looks familiar. What’s that you say? What are the values of a and b? Hold that thought. Lets run the code to figure out the first five terms of the sequence. Evaluating t /@ Range[0,4] gives the following:

Yow. Maybe we can simplify those numerators. There’s a handy builtin for simplifying algebraic expressions. Let use it. We’ll map it over the previous result by evaluating Simplify /@ t /@ Range[0, 4]. Here’s the result.

That looks better, let’s get a few more terms. Evaluating Simplify /@ t /@ Range[0, 9] we get

It turns out the recurrence was cyclic, with only five distinct outcomes which repeat periodically. It turns out that Tn = Tn mod 5

Quick, what is x + x ? Algebra says it’s 2x. Most programming languages treat x not as a symbol, but as an identifier for some region of memory, and demand that the memory be initialized. In that world x + x is undefined unless x is given a value. It doesn’t have to be that way. You learned how to work with symbols in grade school. Shouldn’t your computer language be able to do the same?

The next installment in this series will look at the structure of mma expressions. Lisp, anyone?