How to define functions for a parameter-dependent recursive sequence

Question

I am trying to generate a two variable recursive sequence

For instance on Mathematica, I did

z[1] := {1, 1}
B := {{t, 1}, {-1, t}}
z[n_, t_] := B.z[n - 1, t]

When I tried to see z[2], I get a bunch of gibberish.

$n$ is the variable that is iterating, $t$ is just a parameter that I can throw in whenever I want. My goal is to generate a table of terms based on various iterations of $n$. From that, my sequence would be defined in terms of only $t$, then I would like test out various values of $t$ to generate a numerical sequence.

There are two problems I am having: how to define the functions properly, and how to implement the recursion.

I use Mathematica 8.0.4

Answer 1

I see two ways to do the kind of thing desired. You could make the parameter an argument to every function, or have the parameter be a global symbol and not an argument to any function.

Parameters as arguments

Put an argument in each function representing the parameter:

z[1, t_] := {1, 1};
B[t_] := {{t, 1}, {-1, t}};
z[n_Integer, t_] /; n > 0 := B[t].z[n - 1, t];

{z[2, t], z[2, s], z[2, 100]}
(* {{1 + t, -1 + t}, {1 + s, -1 + s}, {101, 99}} *)

Parameters as global variables

Make sure t is undefined when z and B are defined. (I clear any definitions of z and B as well.)

Clear[t];
Clear[B, z]; (* clear previous definitions *)
z[1] = {1, 1};
B = {{t, 1}, {-1, t}};
z[n_Integer] /; n > 0 := B.z[n - 1];

{z[2], z[2] /. t -> s, z[2] /. t -> 100}
(* {{1 + t, -1 + t}, {1 + s, -1 + s}, {101, 99}} *)

Memoizing

You can often improve performance of recursively defined function if you use a technique called "memoization." An good discussion can be found What does the construct f[x_] := f[x] = ... mean?, cited in a comment by @whuber. The Mathematica documentation has a good introductory tutorial, "Functions That Remember Values They Have Found", too. For example, in the example using t as a global variable, the definition of z would be

z[n_Integer] /; n > 0 := z[n] = B.z[n - 1]

See the links for further discussion.

Discussion

Each approach can do what you want, and each is probably used often. The biggest consideration is that if the parameter t is a global variable, then generally you want to avoid it being set (no t = 3 for example). It might cause unexpected behavior. Thus I have a slight preference for using the argument approach

Why _Integer.../; n > 0 instead of _?

If the definition of z begins z[n_, t_] :=..., then for an undefined symbol n, z[n, t] matches the definition and is expanded. This leads to z[n-1,t], then z[n-2,t] etc. Since z[1,t] is never reached, the recursion goes until the limit is hit. The n_Integer restricts the definition to matching only when n is an integer. The Condition /; n > 0 further restricts the definition to positive integers. This guarantees that recursive definition will be applied only to positive n.

What went wrong in the original definitions?

What is wrong with the first line has to do with how it matches the third line. The recursive definition of z has two arguments and so it will never lead to this pattern:

z[1] := {1, 1}

In the second, t is a global symbol. If it has a value, it will be substituted whenever B is evaluated, because B is defined using SetDelayed.

B := {{t, 1}, {-1, t}}

Another difficulty arises in the different way z and B are defined.

z[n_, t_] := B.z[n - 1, t]

The t in the definition of z is not a variable per se, just the name of the second argument. Technically, it is the Pattern Blank[] that matches whatever is passed as the second argument. It has nothing to do with the global t in B. For instance, z[2, s] will expand to

{{t, 1}, {-1, t}}.z[1, s]

where s would be whatever was passed to z and does not have to be the same as t. (Of course, the recursion will go on until $RecursionLimit is hit, because of the mismatch with the first definition.)

Answer 2

There are two issues here: getting the syntax of the functions correct and then doing the iteration. wHuber shows in the comments a way to correct the syntax of the functions (using pattern matching in the argument of the calling function). You can find this kind of approach applied to calculate the Fibonnaci sequence which essentially uses the SetDelayed command := to do the iteration. While this is quite slick, it is also tricky to get right and does not generalize well.

Mathematica also has several functions devoted to solving iterations. RSolve is one, LinearRecurrence is another. What I would like to do here is to show a structured way of iterating that can be generalized easily just by changing the function definitions.

Let's define two functions. b defines your time varying matrix. f defines the function you want to iterate: in this case, each iteration increases the n and calculates the matrix multiply:

b[n_] := {{n, 1}, {-1, n}};
f[{n_, z_}] := {n + 1, b[n].z};

Then the iteration can be done by NestList:

NestList[f, {1, {1, 1}}, 3]

In this case, your answer comes out looking like:

{{1, {1, 1}}, {2, {2, 0}}, {3, {4, -2}}, {4, {10, -10}}}

where each entry is {n, {z1,z2}}, that is, the iteration number followed by the state z at that time. Of course you can replace the 3 by any number to specify how many iterations to carry out and you can replace the initial state {1,1} with whatever values are convenient.

The above us purely numerical. In the final part of the question, the OP asks to keep the t variable symbolic. This can be done by changing the definition of f to

    f[{n_, z_}] := {n + 1, b[t].z};

Now, running the same NestList gives:

{{1, {1, 1}}, {2, {1 + t, -1 + t}}, 
 {3, {-1 + t + t (1 + t), -1 - t + (-1 + t) t}},
 {4, {-1 - t + (-1 + t) t + t (-1 + t + t (1 + t)), 
      1 - t - t (1 + t) + t (-1 - t + (-1 + t) t)}}}

which is of course, growing rapidly in length.