Problem 4 (Example 10.14 of [10])Solve the recurrence system fT(n)=3T(n-1)+2S(n-1) S(n)=T(n-1)+S(n-1). Problem 5 (Optional,Bonus Question,USA TSTST 2017-6)A sequence fan}is said to be Fibonacci type if it satisfies the recurrence an =an-+an-2.Does there exist a partition P of positive integers,such that P is infinite,and that for all S E P,the elements of S can form a Fibonacci type sequence?Prove your answer. 4 The Annihilator Method Recall that an operator or functional means a high-order function that maps a function to another function.If we keep this definition in mind,we can see that a recurrence is actually a functional equation,in the sense that the unknown in a recurrence is a function.For example,the recurrence T(n)=T(n-1)+2T(n-2)-en can be understood in the following way:We take a function T(n),and apply an operator to map it to another function S(n)=T(n-1)+2T(n-2)-e";if we want the result S(n)to be equal to T(n)itself,what kind of function T(n)should we begin with? At the first look,this change of view does not seem to give us an immediate solution of the recurrence.We might even wonder what is the advantage of changing our view this way.However,if you have studied differential equations,you may remember that a similar change of view enables us to solve some differential equations.For differential equations,it is called"the annihilator method."Fortunately,the same method applies to recurrences as well. The main idea of this method is that we can always rewrite a recurrence in the form A(T(n)=0, where A is an operator.Since the operator A maps function T(n)to constant zero,it is called an annihilator of T(n).If we are lucky enough to know what operator annihilates what functions,then we can figure out function T(n)from its annihilator A. We are particularly interested in an operator L,which is the shiftting operator:For all function T(n)de- fined on natural numbers,IT(n)=T(n +1).In addition to L,we also consider another basic operator c,the multiplication-by-constant operator,which does nothing but multiplying a function by a constant c.Based on these two basic operators,we establish a family of operators using the following operations: .Addition.We can add two operators together to get another operator:for operators A1,A2,for all function T defined on natural numbers,(AI+A2)TeAT+A2T. Multiplication by constant.We can multiply an operator by a constant:for operator A,constant c,for all function T defined on natural numbers,(cA)T=(Ac)T def c(AT). 10Problem 4 (Example 10.14 of [10]) Solve the recurrence system  T(n) = 3T(n − 1) + 2S(n − 1) S(n) = T(n − 1) + S(n − 1). Problem 5 (Optional, Bonus Question, USA TSTST 2017-6) A sequence {an} is said to be Fibonacci type if it satisfies the recurrence an = an−1 + an−2. Does there exist a partition P of positive integers, such that P is infinite, and that for all S ∈ P, the elements of S can form a Fibonacci type sequence? Prove your answer. 4 The Annihilator Method Recall that an operator or functional means a high-order function that maps a function to another function. If we keep this definition in mind, we can see that a recurrence is actually a functional equation, in the sense that the unknown in a recurrence is a function. For example, the recurrence T(n) = T(n − 1) + 2T(n − 2) − e n can be understood in the following way: We take a function T(n), and apply an operator to map it to another function S(n) = T(n − 1) + 2T(n − 2) − e n ; if we want the result S(n) to be equal to T(n) itself, what kind of function T(n) should we begin with? At the first look, this change of view does not seem to give us an immediate solution of the recurrence. We might even wonder what is the advantage of changing our view this way. However, if you have studied differential equations, you may remember that a similar change of view enables us to solve some differential equations. For differential equations, it is called “the annihilator method.” Fortunately, the same method applies to recurrences as well. The main idea of this method is that we can always rewrite a recurrence in the form A(T(n)) = 0, where A is an operator. Since the operator A maps function T(n) to constant zero, it is called an annihilator of T(n). If we are lucky enough to know what operator annihilates what functions, then we can figure out function T(n) from its annihilator A. We are particularly interested in an operator L, which is the shiftting operator: For all function T(n) de- fined on natural numbers, LT(n) = T(n + 1). In addition to L, we also consider another basic operator c, the multiplication-by-constant operator, which does nothing but multiplying a function by a constant c. Based on these two basic operators, we establish a family of operators using the following operations: • Addition. We can add two operators together to get another operator: for operators A1, A2, for all function T defined on natural numbers, (A1 + A2)T def = A1T + A2T. • Multiplication by constant. We can multiply an operator by a constant: for operator A, constant c, for all function T defined on natural numbers, (cA)T = (Ac)T def = c(AT). 10