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_{n1}$ 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.





A 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_{n1} + \beta s_{n2} = 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^{n1} + \beta\lambda^{n2} = 0$
For a nonzero 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.





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.






A recurrence relation that we are fairly familiar with is
$f_n = f_{n1} + f_{n2}$ 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 twoterm 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.





