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


Back to 2320 Home Page