1.5.1. Recurrences

---

 

Recurrences, although a very tedious computation method by hand, is very simple to do in Maple. The best way to learn how to do recurrences in Maple are by examples, and a perfect example for this topic is the Fibonacci sequence.

I. Explicitly Defined Sequences

---

In order for a sequence to be defined explicitly, there must be a function that allows computation. Let’s try to define a function and then find the first three terms of the sequence using that function. Therefore, try the following input:

> s:=a->3*a+5;

This is the function that we use for the sequence. Next, input the following:

> seq(s(a),a=1..3);

As you can see, the seq command provided and output of the first three terms of the sequence.

II. Recursively Defined Sequences

---

Now that we’ve seen an explicitly defined sequence, let’s take a look at a recursively defined sequence.
The format of a recursive sequence is different from the above example mainly because the commands and input is entirely different. Here, you will use for, from, to, do, and od commands, which are special commands. Why are they special? For one, they appear differently when typed in Maple. Normal commands appear red, but these commands appear in black and bold. These commands also cannot solve equations alone compared to other commands. They must be used together in order for commands to be executed. It is better to see this in an example.

> s||1:=1;
> for k from 2 to 10 do s||k:=3*s||(k-1)+2;od;

The above commands should result in the first 10 terms of this recursive sequence.

III. Using rsolve

---

The command rsolve is used to solve linear recurrence relations. According to the Maple website, the rsolve command can solve linear recurrences with constant coefficients, systems of linear recurrences with constant coefficients, divide and conquer recurrences with constant coefficients, many first order linear recurrences, and some nonlinear first order recurrences.

Try the following input:

> eqn:= y(n)=y(n-1)+y(n-2);
> initial:=y(0)=0,y(1)=1;

The rsolve command takes in the parameters of the equation in question and the initial conditions, respectively. Note that the curly braces must be part of the input in order for this to work.

> soln:=rsolve({eqn,initial},y);

IV. Resolving First Order Recurrences

---

This example outlines a different way to use the rsolve command. This combines the use of the rsolve and seq commands to find the elements of a sequence.

{f(n)=f(n-1)+9,f(0)=7};

rsolve(%,f(k)); Note the % refers to the output of the previous line.

seq(subs(k=j,%),j=0..5); Note the subs command, which basically substitutes the k variable with the j variable.

 

Newton's method

is one of the most fundamental algorithms for approximating solutions of f(x) = 0, where the approximations are generated as follows:

x(k+1) = x(k) - f(x(k))/f'(x(k)) , for k=0,1,2,... ,

where f'(x) is the derivative of the function f.

We will make a procedure that returns the right hand side of the iteration above. First of all, we must note the difference between x
and x -> x: the first x is just the name x, while x -> x is the function x.

newtonstep := proc(f::procedure)
description `returns one step with Newton's method on f`:
local ix:
ix := x -> x:                      # identity function
ix - eval(f)/D(eval(f));      # implicit return
end proc;

Note that we use the eval in the procedure to force Maple to evaluate, because for eficiency, Maple would
otherwise delay the evaluation. Let us apply this to approximate a root of cos(x) =1/sqrt(2). First we must make
a function g(x) = cos(x) - 1/sqrt(2).

g := x -> evalf(cos(x) - 1/sqrt(2)):     #define the function g(x)
gstep := newtonstep(g):                    # create a procedure
# gstep(a);                                        # symbolic execution
gstep(1.0);                                       # numerical execution
y := 0.4:                                           # starting value
Digits := 32:                                    # working precision
for i from 1 to 7 do                          # we will do 7 steps
y := gstep(y);
end do;

0.80177037790971674455488745954471
0.94941996709225066605458038769588
0.79574223132384885703507016815897
0.78545075174905338861835347773983
0.78539816478009448345397870159798
0.78539816339744831057151606463206
0.78539816339744830961566084581987
0.78539816339744830961566084581987

To check our calculations, we type

solve(cos(x) = 1/sqrt(2), x)

(1/4)*Pi

evalf(%)

0.78539816339744830961566084581988

Many functions are defined recursively. We see how Maple has a nice mechanism to avoid superiuous recursive calls. One classical example
of a recursive sequence are the Fibonacci numbers:

F(0)=1, F(1)=1, and F(n) = F(n-1) + F(n-2), for n=2,3,... .

The direct way to implement this goes as follows:

fib := proc(n::nonnegint)
description `returns the nth Fibonacci number`:
if n = 0 then
return 0:
elif n = 1 then
return 1:
else
return fib(n-2)+fib(n-1):
end if;
end proc;
Then we calculate first ten Fibonacci numbers:

for i from 1 to 10 do # first ten Fibonacci numbers
fib(i);
end do;

OUT (in blue):
proc(n::nonnegint)
description `returns the nth Fibonacci number`;
if n = 0 then return 0 elif n = 1 then return 1 else return
fib(n-2)+fib(n-1) end if
end proc

1
1
2
3
5
8
13
21
34
55

This is a very expensive way to compute the Fibonacci numbers, because of too many repetitive calls.

starttime := time():
fib(20);
elapsed := (time()-starttime)*seconds;

6765
0.019 seconds

Now we calculate Fibonacci numbers with dynamic programming approach.

newfib := proc (n::nonnegint)
option remember;
description `Fibonacci with remember table`;
if n = 0 then return 0
elif n = 1 then return 1
else return newfib(n-2)+newfib(n-1)
end if end proc;
starttime := time();
newfib(20);
elapsed := (time()-starttime)*seconds

proc(n::nonnegint)
option remember;
description `Fibonacci with remember table`;
if n = 0 then return 0 elif n = 1 then return 1 else return
newfib(n-2)+newfib(n-1) end if
end proc

6765
0.

With the option remember, Maple has built a "remember table" for the procedure. This remember table stores the results of all calls of the procedure. Here is how we can consult this table: eval(newfib); proc(n::nonnegint)
option remember;
description `Fibonacci with remember table`;
if n = 0 then return 0 elif n = 1 then return 1 else return
newfib(n-2)+newfib(n-1) end if
end proc

table([0 = 0, 1 = 1, 2 = 1, 3 = 2, 4 = 3, 5 = 5, 6 = 8, 7 = 13, 9 = 34, 8 = 21, 11 = 89, 10 = 55, 13 = 233, 12 = 144, 15 = 610, 14 = 377, 18 = 2584, 19 = 4181, 16 = 987, 17 = 1597, 20 = 6765])

<
newfib(21)

10946

eval(T)
table([0 = 0, 1 = 1, 2 = 1, 3 = 2, 4 = 3, 5 = 5, 6 = 8, 7 = 13, 9 = 34, 8 = 21, 11 = 89, 10 = 55, 13 = 233, 12 = 144, 15 = 610, 14 = 377, 18 = 2584, 19 = 4181, 16 = 987, 17 = 1597, 20 = 6765, 21 = 10946])

The command forget is used to clear the remember table of a Maple procedure. For example: forget(newfib);