## Math 2320 Quiz 3 SOLUTIONS Whiteley


(10)  Marks

(2)  1.   Consider the recurrence relation:
a_n = a_{n-1} + 2(n+1)$for n >= 1, with the initial condition a_0= 2. Verify that a_n=(n+2)(n+1) is a solution. Substituting into recurrence relation: LHS = (n+2)(n+1) =? RHS = (n+1)(n) + 2(n+1) = (n+1)(n+2) which is, in fact equal to LHS. Also you must check the initial condition: n=0: (0+2)(0+1) = 2. = a_0 (5) Give a solution to the recurrence relation: a_n = 2a_{n-1} + 3a_{n-2} for n\geq 2 , with the initial conditions: a_0= 0, a_1= 4. Substituting a_n= r^n and simplifying - we get the characteristic equation: r^2 = 2 r + 3 or r^2 - 2r -3 = 0 Factoring (or using the quadratic equation) we have: (r-3)(r+1) = 0 or r=3 and r= -1. The general solution to the recurrence relation is: a_n = \alpha_1 (3)^n + \alpha_2 (-1)^n The initial conditions give the two linear equations: n=0 \alpha_1 + \alpha_2 = 0 I n=1 3\alpha_1 - \alpha_2 = 4 II Solving in I, we have \alpha_1 =-\alpha_2 and substituting into II: - 3\alpha_2 - \alpha_2 = 4 or \alpha_2 = -1. Returning to the first equation: \alpha_1 = 1 and \alpha_2 = -1 The solution is : a_n = (3)^n - (-1)^n (ii) Verify that your solution from part (i) works. Substituting the answer in the recurrence relation: LHS = (3)^n - (-1)^n = 9[3^(n-2)] - (-1)^(n-2) RHS = 2[(3)^(n-1) - (-1)^(n-1)] + 3[(3)^(n-2) - (-1)^(n-2)] = 6[3^(n-2)] + 2(-1)^(n-2)] + 3[(3)^(n-2)] -3(-1)^(n-2)] = 9[3^(n-2)] - 1 (-1)^(n-2)] = LHS! Also n = 0: 1 - 1 = 0 = a_0; n = 1: 3 + 1 = 4 = a_1. (iii) Is this solution unique? [Just answer yes or No Yes it is unique. Recurrence relations with appropriate initial conditions always have a unique sequence as a solution (something we proved by induction). 2. You are to construct an n\times 1 strip of blocks using two shapes: 1\times 1 and 3\times 1. (1) a) Give the number of distinct ways of constructing: a 0\times 1 strip: there is 1 way: put no blocks down and the job is finished. (The analogy is - how many ways to pay a$0  toll at a toll booth:  one way - just drive on through!)

a  1\times 1  strip:   there is  1 way -put down a 1x1 block.

a  2\times 1  strip:  there is  1 way -put down two  1x1 blocks,
side by side if your strip is horizontal,
(or on top of one another if your strip is vertical).

a   3\times 1  strip:  There are two ways:  three 1x1 blocks side by side,
one    3x1 block

(2)  b)  Give a recurrence relation for the number of ways of constructing
an  n\times 1  strip from these smaller   1\times 1  and  3\times 1  blocks.

Answer   a_n  =  a_(n-1)  +  a_(n-3):

Let  T_n be the set of all possible   nx1  strips.  Take an element for this set
Remove the last block:
if it is  1x1, then we have something of length  (n-1) from  T_(n-1).
Otherwise, the last block is  3x1, and we are left with something of
length  (n-3)  from  T_(n-3).
Counting these sets, we have the recurrence:
a_n  =  a_(n-1)  +  a_(n-3)

State the corresponding initial conditions.
a_0 = 1,   a_1 = 1, a_2 = 1  and your recurrence relation applies to  n>= 3
or
a_1 = 1,   a_2 = 1, a_3 = 2  and your recurrence relation applies to n>=4