**1. Recursively defined sequences.**

A sequence is recursively defined if it the value of a term in the sequence is determined by a rule which determines the value of a term in terms of the values of earlier terms, with some of the first few terms of the sequence possibly being given in advance. For example, if
, and
defines the sequence whose value at any positive integer n is simply
**. **
To define this sequence recursively in Maple, we use a procedure with a remember option. The remember option makes the procedure run more efficiently. You might want to look up remember in the help to understand what is going on.

`> `
**a:=proc(n)**

`> `
**option remember;**

`> `
**a(n-1)+1;**

`> `
**end;**

However, this recursion will not work unless we also tell Maple the initial value of the sequence.

`> `
**a(1):=1;**

Let us verify that Maple will compute the correct value for .

`> `
**a(10);**

A very famous recursively defined sequence is the
**Fibonacci**
sequence, which is determined by
, with initial values
,
. Note that to define the sequenc in Maple, you want to convert the definition to the form
. Then all we do is enter

`> `
**a:=proc(n)**

`> `
**option remember;**

`> `
**a(n-2)+a(n-1);**

`> `
**end;**

`> `
**a(1):=1;a(2):=1;**

Let us calculate .

`> `
**a(5);**

How about graphing the Fibonacci sequence.

`> `
**plot([seq([n,a(n)],n=1..100)],style=point);**

It looks like the Fibonacci sequence is increasing and diverges. However, because this sequence is defined recursively, Maple is unable to compute the limit.

`> `
**limit(a(n),n=infinity);**

Error, (in limit) invalid limiting point

**Submission:**

For the sequences below, do the following.

a) Define a procedure which gives the sequence.

b) Plot the first 100 terms in the sequence.

c) Decide whether the sequence appears to converge, and if so, estimate the value to which it converges.

1) , .

2) .

**Submission worksheet:**

`> `

In a problem analysis it is often convenient to express a value at one point in time in terms of values at earlier times - this is called recursion. The following program generates a sequence, {
} where
which gives the size of a population at generation
*n*
which is of interest to an ecologist,
is the fraction of the maximum size of the population, so it is always between 0 and 1.

`> `
**p := proc(k,p0,n)**

`> `
**a := [p0]:**

`> `
**for i from 2 to n do**

`> `
**a:= [op(a),k*a[i-1]*(1-a[i-1])]:**

`> `
**od;**

`> `
**RETURN(a);**

`> `
**end:**

Warning, `a` is implicitly declared local to procedure `p`

Warning, `i` is implicitly declared local to procedure `p`

`> `
**popmodel := p(1.1,0.5,30);**

If we want to look at a graph of this we would just type

`> `
**plot([seq([n,popmodel[n]],n=1..30)],style=point);**

**Submission:**

(a) Calculate 30 terms of the sequence {
} for
and for for two values of
*k*
such that 1<
*k*
< 3 . Graph the sequences. Do they appear to converge? Repeat for a different value of
between 0 and 1. Does the limit depend on the choice of
? Does it depend on the choece of
*k*
?

(b) Calculate terms of the sequence for a value of
*k*
between 3 and 3.4 and plot them. What do you notice about the behavior of the terms?

(c) Experimaent with values of
*k*
between 3.4 and 3.5. what happens to the terms?

(d) For values of
*k*
between 3.6 and 4, compute and plot at least 100 terms and comment on the behavior of the sequence. What hapens if you change
by 0.001? this type of behavior is called
*chaotic*
and is exhibited by insect populations under certain conditions. Say some words about why you think this behavior is called
*chaotic*
.

**Submission worksheet:**

`> `

**3. Picard's method for finding roots.**
** **

Picard's method of finding roots of the equation
is to consider the equation function
, and solve the equation
instead. The solutions to both equations are the same. At first, this seems to be no benefit, but Picard came up with an ingenious method for finding the roots of the second equation by means of a recursively defined sequence. Let
be any number in the domain of the function, and define the sequence
** **
by
. In many cases, this sequence will converge to some number
*x,*
and it can be shown that when it does converge to a number
*x*
, then it happens that
, so that
.

Let us consider a simple example. Suppose that
**. **
Then
. It is easy to determine that
precisely when
. In fact, we can solve the equation very easily, because it is linear. Let us construct the Picard sequence for this function, starting with
.

`> `
**g:=x->x/4+3;**

`> `
**x:=proc(n)**

`> `
**option remember;**

`> `
**g(x(n-1));**

`> `
**end;**

`> `
**x(1):=5;**

Let us plot the first 100 terms of this sequence to see what it seems to converge to.

`> `
**plot([seq([n,x(n)],n=1..100)],style=point);**

It does appear that the sequence is converging to , as we would hope.

Let us solve the equation . In this case, we have , or .

`> `
**g:=cos;**

`> `
**x:=proc(n)**

`> `
**option remember;**

`> `
**g(x(n-1));**

`> `
**end;**

Let us use .

`> `
**x(1):=0;**

`> `
**plot([seq([n,x(n)],n=1..100)],style=point);**

This time the sequence jumps around a bit before approaching a value which we can estimate by clicking on the graph. is an approximate solution. We could get a better approximation by evaluating the value of .

`> `
**evalf(x(100));**

It is interesting to note that Maple cannot solve this problem exactly.

`> `
**x:='x';**

`> `
**solve(cos(x)=x);**

Nevertheless, Maple can find an estimate of the solution.

`> `
**fsolve(cos(x)=x);**

The answer concurs with our estimate from the Picard sequence. I wonder what method Maple might have used to come up with this estimate?

**Submission:**

Use Picard's method to solve the following equations. First define the Picard sequence for the problem, then graph it, and use the graph to estimate the solution. Then determine the solution with Maple.

1) .

2)

**Submission worksheet:**

`> `

`> `

`> `