# MATH 3600 HW16

## MATH 3600 - HW16

### March 7, 2014

Exercise 1:  A simple but unusual seqence. Create a list, F, of the function values, $f(N)$ for $N$ in [0,..,10].  Then calculate the lists of first, second, third, and fourth differences.  Call these list D1, D2, D3, and D4.

def f(N): y = 0 for m in [1,..N]: for n in [1,..,m]: y += n return y
F = print 'F: ',F D1 = print 'D1: ',D1 D2 = print 'D2: ',D2 D3= print 'D3: ',D3 D4 = print 'D4: ',D4

Exercise 2:  If all the differences are calculated correctly, then D4 will be a list of zeros. This implies that the sequence is generated by a cubic polynomial.  Using the first 4 terms in the sequence, determine the coefficients of the cubic polynomial

$p_3 (n) = a n^3 + b n^2 + c n + d$

Then define the function p3(n).

def p3(n): y = return y

Exercise 3:  Create two lists F and P. The list, F, contains the function values of $f(N)$ for $N$ in [0,..,20]. The list, P, contains the function values of $p_3(N)$ for $N$ in [0,..,20]. In the subsequent block enter the OEIS number and name for this sequence.

F = print 'F:',F P = print 'P:',P
# OEIS ID and Name #

Consider the sequence generated by the linear, constant coefficient, homogeneous two-term recurrence

$g_n = 4 g_{n-1} - 3 g_{n-2}$

with the initial conditions

$g(0) = 0$,  and  $g(1) = 1$.

Exercise 4:  Create a list, G1, of the function values, $g(N)$ for $N$ in [0,..,15].

G1 = [0,1] # # # print G1

Since this is a very special type of recurrence, we might ask if there is a number, $\lambda$, such that setting $g_n = \lambda ^n$ satisfies the recurrence.  Then we would have the following relationship.

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

There are two nonzero numbers which will satisfy this relationship, namely the roots of the quadratic equation

$\lambda^2 -4 \lambda +3 = 0$.

Exercise 5:  Find the two roots of this quadratic equation.  Call them r1 and r2. Whether you determine r1 and r2 by hand or by using Sage, show your process in the block below.  Then create two lists R1 and R2, where the lists contain the values of r1^n and r2^n respectively, for $n$ in [0,..,15].

# # # # r1 = r2 = print 'r1:',r1,'\t','r2:',r2
R1 = [r1^n for n in [0,..,15]] print 'R1:',R1 R2 = [r2^n for n in [0,..,15]] print 'R2:',R2

Exercise 6:  Find the coefficients A and B such that

A*R1 + B*R2 = G1

A*R1 + B*R2 = G1

Whether you find these coefficients by hand or by using Sage, show your work in the block below. Then create a list, G2, where the list contains the values of A*R1[n]+B*R2[n]  for $n$ in [0,..,15].

# # # # A = B =
G2 = print G2

Exercise 7:  Using the roots r1 and r2 and the coefficients A and B, found in the previous two exercises, define the function, g3(n), that is the closed form solution to the recurrence relation defined in Exercise 4. Then create a list, G3, of the function values, $g3(n)$ for $n$ in [0,..,15]. Finally, print G1, G2, and G3.

def g3(n): y = return y
G3 = print 'G1:',G1 print 'G2:',G2 print 'G3:',G3