This post is the second in a series. The first is here. The plan for this post is to introduce just enough notation to define some functions in the Mathematica language, and then use Mathematica to solve a not-entirely-trivial problem.

The central idiom in functional programming is applying a function **f** to an argument **x**. Mma offers several notations for doing so. I’ll illustrate the two I use most. 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 used to control operator precedence, nothing else. The most common notational 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] ] ].** The whitespace is optional; I could have written **h@g@f@x**. The square bracket notation is more convenient with functions of several arguments.

The next bit of notation illustrates how to define functions. I’ll define a couple of example functions, double and recip. Their meaning should be clear.

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

Notice the underscore following the parameter. It needs to be there. I’ll say more about that shortly. For now just go with it.

Most functional languages put a lot of stock in working with lists. Mma is no different; lists abound. Mma lists are delimited by curly braces, and have comma separated values. Here is a list of integers: {2, 3, 7, 13}. The handy built-in function **Range** generates lists of integers. For instance, **Range[1, 3]** returns { 1, 2, 3 }.

One last bit of notation and we are ready to go. Here are two equivalent ways to map the function **recip** over the elements of a list.

recip /@ Range[1, 3] Map[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 }**.

As an aside, notice that Mma returned exact rational numbers rather than approximate floating point values.

The problem I have chosen as my example is the exercise 8 in Concrete Mathematics, by Graham, Knuth, and Patashnik. Great book, by the way.

The problem is to solve a recurrence. That means that we are given a recursive definition of how to compute the terms of a sequence, and need to figure out an explicit formula for the nth term. You have probably already seen recurrences, even if they weren’t called recurrences. Here’s an easy one, as a warm up.

T_{0} = 1

T_{n} = 2 T_{n-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

T_{n} = 2 ^{n}

Knuth et alia propose a somewhat harder recurrence. Here it is.

T_{0} = a

T_{1} = b

T_{n} = (1+T_{n-1})/T_{n-2}

How does one start to solve a recurrence? One very natural thing to do is to generate the first few terms of the sequence and look for 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]

The code neatly mirrors the mathematics. Notice that the definition of the function **t** occurs in three parts, rather than as a single expression containing conditional logic. This style of definition is used in other languages, Erlang for instance, and is a joy to use. I really miss it when it is not available.

I promised to say something about the notation of an underscore following a parameter, as after the **n** in the third clause of the definition of **t**. Roughly, the underscore indicates that we are using **n** as a parameter. Without the underscore, we would be defining the action of **t** on the symbol **n**. In the first two lines we define **t** on 0 and 1.

What’s that you say? I did not assign values to **a** and **b**? Hold that thought.

Let’s generate a few terms of the sequence. Evaluating **t /@ Range[0,4]** gives the following:

Yow, continued fractions. Maybe we can simplify those numerators. There’s a handy built-in called **Simplify** for simplifying algebraic expressions. Let use it. We’ll map **Simplify** 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

The recurrence turns out to be cyclic. There are only five distinct terms which repeat periodically. So the solution is that **T _{n} = T_{n mod 5}**

with **T _{0} = a**,

**T**, etc, as above.

_{1}= bWhat is **x + x** ? Algebra says it’s **2x**, no matter what the value of **x**. 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?

In Mathematica, a symbol can be assigned a value, or it can just be a symbol. I did not have to give either **a** or **b** values to be able to work with algebraic expressions involving **a** and **b**. That is a very powerful feature. It makes it possible for Mathematica to perform symbolic mathematics such as calculus. Or simple algebra. For instance, we could expand (a + b +c)^3 as follows:

`Expand[(a + b + c)^3]`

```
```

` The result is a^3 + 3 a^2 b + 3 a b^2 + b^3 + 3 a^2 c + 6 a b c + 3 b^2 c + 3 a c^2 + 3 b c^2 + c^3.`

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