MATH 3600 - HW14

Date: ________________

A simple but very important sequence is the geometric sequence (also called a geometric progression).  The recurrence relation is simply

$a_n = \beta a_{n-1}$  with  $a_0 = \alpha$.

Note that if $\beta=1$, then the sequence is just the constant sequence.  If $\beta$ is positive and larger than 1, then the sequence grows, and if $\beta$ is positive and less than 1, then the sequence decays.  If $\beta$ is negative, then the behavior is similar except that terms alternate sign.

For the geometric sequence the closed form solution to the recurrence relation is simply

$a_n = \alpha \beta^n$

Exercise 1:  In the next block complete the definition of the recursive function that returns the $n$-th term in the geometric sequence defined by $\alpha=3$ and $\beta=2$.  Then evaluate the subsequent block.  In third block write a while loop that uses the recurrence relation to create a list of all the terms in the sequence that are less than 10,000.  Finally, in the fourth block complete the definition of the function that returns the $n$-th term in the sequence using the closed form solution of the recurrence relation, and then evaluate the subsequent block.

def f1(n): if n < 0: return None alpha = 3 beta = 2 # # # #
print f1(-1),f1(0),f1(1),f1(2),f1(3),f1(4),f1(5),f1(10),f1(25) timeit("f1(-1),f1(0),f1(1),f1(2),f1(3),f1(4),f1(5),f1(10),f1(25)")
alpha = 3 beta = 2 A = [] y = alpha while y < 10000: # # A
def f2(n): if n < 0: return None alpha = 3 beta = 2 #
print f2(-1),f2(0),f2(1),f2(2),f2(3),f2(4),f2(5),f2(10),f2(25) timeit("f2(-1),f2(0),f2(1),f2(2),f2(3),f2(4),f2(5),f2(10),f2(25)")

geometric series is a sequence of partial sums of a geometric sequence.  Given the geometric sequence [$a_0$, $a_1$, $a_2$, $a_3$, . . . , $a_n$] the corresponding geometric series is

[ $s_0 = a_0$,   $s_1 = a_0 + a_1$,   $s_2 = a_0 + a_1+a_2$,   $s_3 = \sum_{k=0}^3 a_k$,  .  .  .  ,  $s_n = \sum_{k=0}^n a_k$ ]

The linear, constant coefficient, two term recurrence relation is given by

$s_n - (1+\beta)s_{n-1} + \beta s_{n-2} = 0$   with   $s_0 = \alpha$   and   $s_1 = \alpha(1+\beta)$.

Notice that this recurrence relation (and the related difference equation) is a linear homogeneous equation.  We can take that same approach that we would use with a second order linear homogeneous differential equation, namely see what happens with $\lambda ^n$.  Substituting $\lambda ^n$ into the recurrence relation we get

$\lambda^n - (1+\beta)\lambda^{n-1} + \beta\lambda^{n-2} = 0$

For a non-zero value of $\lambda$ to satisfy this equation,  $\lambda$ must be a solution to the quadratic equation

$\lambda^2 - (1+\beta)\lambda + \beta = 0$

Since $\lambda^2 - (1+\beta)\lambda + \beta = (\lambda - 1)(\lambda - \beta)$ the general solution has to be

$s_n = A ( 1^n) + B( \beta^n)$

For $n=0$ and $n=1$ we get the two equations

$A+B=\alpha$  and  $A + B\beta = \alpha(1+\beta)$

Solving these two equations gives us $A = \alpha/(1-\beta)$ and $B = -\alpha\beta/(1-\beta)$.  Thus

$s_n = \alpha(1 - \beta^{n+1})/(1-\beta)$

A more common approach that skips over the recurrence relation is to simply consider what happens to the expression $s_n - \beta s_n = s_n(1-\beta)$ which yields a telescoping series.

Exercise 2:  In the next block complete the definition of the recursive function that returns the $n$-th term in the geometric series defined by $\alpha=3$ and $\beta=2$. Then evaluate the subsequent block. In third block write a while loop that creates a list of all the terms in the sequence that are less than 10,000.  Finally, in the fourth block complete the definition of the function that returns the $n$-th term in the sequence using the closed form solution of the recurrence relation, and then evaluate the subsequent block.

def f3(n): if n<0: return None alpha = 3 beta = 2 # # # # # # #
print f3(-1),f3(0),f3(1),f3(2),f3(3),f3(4),f3(5),f3(10),f3(25) timeit("f3(-1),f3(0),f3(1),f3(2),f3(3),f3(4),f3(5),f3(10),f3(25)")
alpha = 3 beta = 2 S = [alpha] y = alpha*(1+beta) while y < 10000: # # S
def f4(n): if n<0: return None alpha = 3 beta = 2 #
print f4(-1),f4(0),f4(1),f4(2),f4(3),f4(4),f4(5),f4(10),f4(25) timeit("f4(-1),f4(0),f4(1),f4(2),f4(3),f4(4),f4(5),f4(10),f4(25)")

Exercise 3:  The recursive function, f3, makes two recursive calls at each step.  This causes an explosion in the number of recursive copies that get created.  Run the following two blocks to get a printed confirmation of this behavior and draw the calling trees (on a separate piece of paper) for cases $n$= 2, 3, 4, and 5.  Then run the two blocks that implement the cache.

def f5(n): print n, if n<0: return None alpha = 3 beta = 2 # # # # # # #
print f5(-1);f5(0);f5(1);f5(2);f5(3);f5(4);f5(5);f5(10) # f5(25) Run this case to see what happens, but don't include the result on the worksheet you turn in.
timeit("f5(-1);f5(0);f5(1);f5(2);f5(3);f5(4);f5(5);f5(10);f5(25)")
# A cache can eliminate the redundancy from this type of recursion def f5c(n): print n, if n<0: return None # # # # # # # # # # # #
cache = {} print f5c(-1);f5c(0);f5c(1);f5c(2);f5c(3);f5c(4);f5c(5);f5c(10);f5c(25)
timeit("cache = {};f5c(-1);f5c(0);f5c(1);f5c(2);f5c(3);f5c(4);f5c(5);f5c(10);f5c(25)")

Fibonacci Reprise

A recurrence relation that we are fairly familiar with is

$f_n = f_{n-1} + f_{n-2}$   with   $f_0 = 0$  and  $f_1=1$.

This recurrence relation is also a linear homogeneous relation.  So, as in the previous case, we can ask what happens to $\lambda^n$.  We can quickly see that $\lambda^n$ is a solution to the recurrence if and only if $\lambda$ solves the quadratic equation

$\lambda^2 - \lambda - 1 = 0$

By the quadratic formula we can see that the two roots are $\lambda_1 = (1+\sqrt(5))/2$ and $\lambda_2 = (1-\sqrt(5))/2$.

The closed form solution to the two-term recurrence relation is

$f_n = A \lambda_1^n + B \lambda_2^n$.

Exercise 4:  In the next block determine the coefficients $A$ and $B$ so that

$A \lambda_1^n + B \lambda_2^n = f_n$

for $n=0$ and $n=1$.

Exercise 5:  In the next block complete the definition of the recursive function that returns the $n$-th term in the Fibonacci sequence. Then evaluate the subsequent block. In third block write a while loop that creates a list of all the terms in the sequence that are less than 10,000.  Finally, in the fourth block complete the definition of the function that returns the $n$-th term in the sequence using the closed form solution of the recurrence relation, and then evaluate the subsequent block.

def Fib1(n): if n<0: return None # # # # # # #
print Fib1(-1),Fib1(0),Fib1(1),Fib1(2),Fib1(3),Fib1(4),Fib1(5),Fib1(6),Fib1(7),Fib1(8),Fib1(9),Fib1(10),Fib1(25) timeit("Fib1(-1),Fib1(0),Fib1(1),Fib1(2),Fib1(3),Fib1(4),Fib1(5),Fib1(6),Fib1(7),Fib1(8),Fib1(9),Fib1(10),Fib1(25)")
F = [0] y = 1 while y<10000: # # F
def Fib(n): if n<0: return None # # # # return expand(y)
print Fib(-1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(5),Fib(6),Fib(7),Fib(8),Fib(9),Fib(10),Fib(25) timeit("Fib(-1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(5),Fib(6),Fib(7),Fib(8),Fib(9),Fib(10),Fib(25)")