(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 youmustcheck 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 = -1The 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 answeryesorNoYes it is unique.Recurrence relations with appropriate initial conditionsalwayshave 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: putnoblocks 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.Answera_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>= 3ora_1 = 1, a_2 = 1, a_3 = 2 and your recurrence relation applies to n>=4

Back to