1What is the order of the recurrence relation with ?
A.$1$
B.
C.
D.
Correct Answer:
Explanation:The order of a recurrence relation is the difference between the largest and smallest subscripts of the terms in the relation. Here, .
Incorrect! Try again.
2Which of the following is a linear homogeneous recurrence relation with constant coefficients?
A.
B.
C.
D.
Correct Answer:
Explanation:Option A is non-linear (). Option B has a non-constant coefficient (). Option D is non-homogeneous (due to the ). Option C satisfies all criteria.
Incorrect! Try again.
3For the Fibonacci sequence defined by with and , what is the value of ?
A.3
B.5
C.8
D.13
Correct Answer: 5
Explanation:.
Incorrect! Try again.
4The recurrence relation for the Tower of Hanoi problem, where is the number of moves to move disks, is:
A.
B.
C.
D.
Correct Answer:
Explanation:To move disks, you move disks to the auxiliary peg (), move the largest disk to the target (1 move), and move the disks to the target (). Total: .
Incorrect! Try again.
5What is the degree of the recurrence relation ?
A.1
B.2
C.3
D.
Correct Answer: 3
Explanation:The degree of a recurrence relation is the highest power of the unknown sequence terms appearing in the relation. Here, is raised to the power of 3.
Incorrect! Try again.
6If a bank account pays 5% interest compounded annually, and represents the amount after years, the recurrence relation is:
A.
B.
C.
D.
Correct Answer:
Explanation:The new amount is the previous amount plus 5% of the previous amount: .
Incorrect! Try again.
7To solve a recurrence relation of order , how many initial conditions are generally required to find a unique solution?
A.$1$
B.
C.
D.
Correct Answer:
Explanation:Generally, a recurrence relation of order requires initial values (e.g., ) to determine the specific constants in the general solution.
Incorrect! Try again.
8Which sequence satisfies the recurrence relation with ?
A.
B.
C.
D.
Correct Answer:
Explanation:This is a geometric progression with ratio 2 starting at 3. .
Incorrect! Try again.
9Identify the Characteristic Equation of the recurrence relation .
A.
B.
C.
D.
Correct Answer:
Explanation:Substitute . Dividing by gives the characteristic equation .
Incorrect! Try again.
10What are the roots of the characteristic equation for ?
A.
B.
C.$2, 2$
D.$3, 4$
Correct Answer:
Explanation:Rewrite as . Characteristic eq: . Factors: . Roots are $4$ and .
Incorrect! Try again.
11If the roots of the characteristic equation are distinct real numbers and , the general solution is:
A.
B.
C.
D.
Correct Answer:
Explanation:For linear homogeneous recurrence relations with constant coefficients and distinct real roots, the solution is a linear combination of the roots raised to the power .
Incorrect! Try again.
12If the characteristic equation has a repeated root of multiplicity 2, the general solution is:
A.
B.
C.
D.
Correct Answer:
Explanation:When a root repeats, we multiply the second term by to ensure linear independence.
Incorrect! Try again.
13Solve the recurrence relation with .
A.
B.
C.
D.
Correct Answer:
Explanation:Char eq: . Root (repeated). Form: . Using . Using . Thus .
15A recurrence relation is called non-homogeneous if:
A.
B. and depends only on previous terms
C.The relation includes a term not involving (a function of only) which is non-zero
D.The coefficients are not constants
Correct Answer: The relation includes a term not involving (a function of only) which is non-zero
Explanation:A linear recurrence is non-homogeneous if there is an 'external' forcing function of (denoted often as or RHS) that is not part of the sequence terms.
Incorrect! Try again.
16The total solution of a non-homogeneous recurrence relation is given by:
A.
B.
C.
D.
Correct Answer:
Explanation:The complete solution is the sum of the general solution to the associated homogeneous relation and a particular solution to the non-homogeneous relation.
Incorrect! Try again.
17In the Method of Inverse Operator, the shift operator is defined such that ?
A.
B.
C.
D.
Correct Answer:
Explanation: is the forward shift operator. Applying it once moves the index from to .
Incorrect! Try again.
18Using the inverse operator method, if the recurrence is (where is a constant), the particular solution is:
A. provided
B.
C.
D.
Correct Answer: provided
Explanation:We replace the operator with the constant base , provided the denominator does not become zero.
Incorrect! Try again.
19Find the particular solution for using the inverse operator method.
A.
B.
C.
D.
Correct Answer:
Explanation:Particular solution . Substitute . .
Incorrect! Try again.
20Find the particular solution for (Note: ).
A.
B.$5$
C.$2.5$
D.
Correct Answer:
Explanation:. Substitute . .
Incorrect! Try again.
21Using the inverse operator method, if and , this is known as:
A.The homogeneous case
B.The case of failure
C.The linearity property
D.The generating function case
Correct Answer: The case of failure
Explanation:When substituting the base into the polynomial results in division by zero, it is the case of failure, requiring differentiation of or multiplying by .
Incorrect! Try again.
22Which of the following represents the recurrence in terms of the operator ?
A.
B.
C.
D.
Correct Answer:
Explanation: and . Substituting gives .
Incorrect! Try again.
23What is the particular solution of ?
A.
B.$3$
C.
D.
Correct Answer:
Explanation:Equation in : . Or convert to indices: . .
Incorrect! Try again.
24For the recurrence , the particular solution involves multiplying by:
A.
B.
C.
D.
Correct Answer:
Explanation:This is a case of second-order failure. Generally, . For , it is .
Incorrect! Try again.
25A generating function for a sequence is defined as:
A.
B.
C.
D.
Correct Answer:
Explanation:This is the definition of the Ordinary Generating Function (OGF).
Incorrect! Try again.
26What is the generating function for the sequence ?
A.
B.
C.
D.
Correct Answer:
Explanation:The sum is , which is the geometric series summing to for .
Incorrect! Try again.
27The generating function for the sequence is:
A.
B.
C.
D.
Correct Answer:
Explanation:Differentiating gives , which corresponds to sequence .
Incorrect! Try again.
28If is the generating function for , then is the generating function for:
A.
B. (shifted to the right)
C.
D.
Correct Answer: (shifted to the right)
Explanation:Multiplying by shifts the coefficients. . The sequence becomes .
Incorrect! Try again.
29The coefficient of in the expansion of is:
A.
B.
C.
D.
Correct Answer:
Explanation:By the Binomial Theorem, .
Incorrect! Try again.
30To solve using generating functions, let . Multiplying the relation by and summing from yields:
A.
B.
C.
D.
Correct Answer:
Explanation:. The first term is . The second term is .
Incorrect! Try again.
31If , find the closed form for .
A.
B.
C.
D.
Correct Answer:
Explanation:. Multiplying by 2 gives .
Incorrect! Try again.
32What is the generating function for the finite sequence $1, 4, 6, 4, 1$?
A.
B.
C.
D.
Correct Answer:
Explanation:These are the binomial coefficients . The polynomial is .
Incorrect! Try again.
33In the method of generating functions, Partial Fraction Decomposition is often used to:
A.Multiply two generating functions
B.Break a complex rational function into simpler terms to extract coefficients
C.Differentiate the function
D.Shift the indices
Correct Answer: Break a complex rational function into simpler terms to extract coefficients
Explanation:If , we split it into to easily find the coefficient of (which is ).
Incorrect! Try again.
34Solve using generating functions. The denominator of the resulting will be:
A.
B.
C.
D.
Correct Answer:
Explanation:From the relation , the G.F. manipulation leads to . Thus the denominator is .
Incorrect! Try again.
35The coefficient of in is:
A.
B.$1$
C.
D.
Correct Answer:
Explanation:.
Incorrect! Try again.
36If is the generating function for , what sequence does represent?
A.
B.
C.
D.
Correct Answer:
Explanation:. . The coefficient of is .
Incorrect! Try again.
37What is the generating function for the sequence ()?
A.
B.
C.
D.
Correct Answer:
Explanation:We know . Multiplying by shifts this to .
Incorrect! Try again.
38Which method is best suited for solving recurrence relations with non-constant coefficients or those involving complex boundary conditions?
A.Characteristic Root Method
B.Generating Functions
C.Substitution Method
D.Inverse Operator Method
Correct Answer: Generating Functions
Explanation:Generating functions transform the recurrence into a differential equation or algebraic equation which is often more powerful for non-constant coefficients or combinatorial identities.
Incorrect! Try again.
39The particular solution of is:
A.
B.
C.
D.
Correct Answer:
Explanation:We can treat as . The inverse operator for on binomial coefficients shifts the index. Specifically, . Here . So .
Incorrect! Try again.
40In the recurrence , if , what is ?
A.10
B.20
C.40
D.80
Correct Answer: 40
Explanation:.
Incorrect! Try again.
41What is the homogeneous part of the solution for ?
A.
B.
C.
D.
Correct Answer:
Explanation:Char eq: . Roots are .
Incorrect! Try again.
42Calculate the roots of .
A.3 (multiplicity 2)
B.-3 (multiplicity 2)
C.3, -3
D.9, 1
Correct Answer: 3 (multiplicity 2)
Explanation:, so is a repeated root.
Incorrect! Try again.
43If satisfies , then is an alternating sequence.
A.True
B.False
C.Depends on
D.Only if
Correct Answer: True
Explanation:. The sign flips every term (unless , which is trivially alternating $0,0...$).
Incorrect! Try again.
44Which generating function operation corresponds to the convolution of two sequences and ?
A.
B.
C.
D.
Correct Answer:
Explanation:The product of two generating functions corresponds to the Cauchy product (convolution) of their sequences: .
Incorrect! Try again.
45Solve the characteristic equation for real roots.
A.2
B.-2
C.2, -2
D.
Correct Answer: 2
Explanation:The only real number cubed to give 8 is 2.
Incorrect! Try again.
46If and RHS is , finding particular solution involves calculating . What is ?
A.1
B.5
C.
D.-1
Correct Answer: 5
Explanation:.
Incorrect! Try again.
47The generating function for is:
A.
B.
C.
D.
Correct Answer:
Explanation:Geometric series with ratio : .
Incorrect! Try again.
48When solving via generating functions, we get . The coefficient of is found by expanding:
A.
B.
C.
D.
Correct Answer:
Explanation:. Expand as geometric series .
Incorrect! Try again.
49For a non-homogeneous relation , the particular solution will be of the form:
A.
B.
C.
D.
Correct Answer:
Explanation:Since the RHS is a polynomial of degree 1 (), and 1 is not a root of the homogeneous characteristic eq (), the particular solution is a generic polynomial of degree 1: .
Incorrect! Try again.
50What is the value of ?
A.
B.$1$
C.Undefined
D.
Correct Answer:
Explanation:This is a case of failure as for . .
Incorrect! Try again.
Give Feedback
Help us improve by sharing your thoughts or reporting issues.