Explanation:The order of a recurrence relation is the difference between the greatest and smallest subscripts of the terms in the relation. Here, .
Incorrect! Try again.
2Which of the following is a linear recurrence relation?
A.
B.
C.
D.
Correct Answer:
Explanation:A relation is linear if the terms appear only to the first power and are not multiplied together. Options A, B, and D involve squares, products, or transcendental functions of .
Incorrect! Try again.
3Is the recurrence relation homogeneous?
A.Yes
B.No
C.Depends on n
D.Cannot be determined
Correct Answer: No
Explanation:It is non-homogeneous because of the term on the right-hand side, which is a function of not involving .
Incorrect! Try again.
4What is the degree of the recurrence relation ?
A.1
B.2
C.3
D.0
Correct Answer: 3
Explanation:The degree is the highest power to which the unknown sequence terms are raised. Here is raised to the power of 3.
Incorrect! Try again.
5The recurrence relation for the Fibonacci sequence is:
A.
B.
C.
D.
Correct Answer:
Explanation:The standard definition of the Fibonacci sequence is that each term is the sum of the two preceding terms.
Incorrect! Try again.
6In the Tower of Hanoi problem with disks, let be the number of moves. The recurrence relation is:
A.
B.
C.
D.
Correct Answer:
Explanation:To move disks, you move disks to the auxiliary peg (), move the largest disk to the destination ($1$), then move the disks to the destination (). Total: .
Incorrect! Try again.
7A bank pays 5% interest compounded annually. If is the amount after years, the recurrence relation is:
A.
B.
C.
D.
Correct Answer:
Explanation:.
Incorrect! Try again.
8The characteristic equation of the recurrence relation is:
A.
B.
C.
D.
Correct Answer:
Explanation:Substitute . Dividing by , we get .
Incorrect! Try again.
9If 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.
10Find the roots of the characteristic equation for .
A.3, 4
B.4, -1
C.2, 2
D.-1, -4
Correct Answer: 4, -1
Explanation:Equation: . Factoring: . Roots are 4 and -1.
Incorrect! Try again.
11If the characteristic equation has a repeated root of multiplicity 2, the homogeneous solution is of the form:
A.
B.
C.
D.
Correct Answer:
Explanation:When roots are repeated, we multiply the second term by to ensure linear independence.
Incorrect! Try again.
12Solve the recurrence with .
A.
B.
C.
D.
Correct Answer:
Explanation:This is a geometric progression. . General solution . Using , .
14If the roots of the characteristic equation are complex conjugates , the solution involves:
A. terms
B.Logarithmic functions
C.Trigonometric functions (sine/cosine) inside the solution structure
D.Only real exponentials
Correct Answer: Trigonometric functions (sine/cosine) inside the solution structure
Explanation:Complex roots lead to solutions of the form .
Incorrect! Try again.
15The total solution of a non-homogeneous recurrence relation consists of:
A.Only the homogeneous solution
B.Only the particular solution
C.The product of homogeneous and particular solutions
D.The sum of homogeneous and particular solutions
Correct Answer: The sum of homogeneous and particular solutions
Explanation:Similar to differential equations, .
Incorrect! Try again.
16In the method of inverse operators, the shift operator is defined as:
A.
B.
C.
D.
Correct Answer:
Explanation: is the forward shift operator.
Incorrect! Try again.
17Using the inverse operator method, the particular solution for (where ) is:
A.
B.
C.
D.$0$
Correct Answer:
Explanation:If and is not a root of the characteristic equation, replace with .
Incorrect! Try again.
18Find the particular solution of using inverse operators.
A.
B.
C.
D.
Correct Answer:
Explanation:Using standard undetermined coefficients or inverse operators: Try . Substitute: . Divide by . Solution .
Incorrect! Try again.
19When solving , what is the form of the particular solution?
A.
B.
C.
D.
Correct Answer:
Explanation:Since 3 is a root of multiplicity 2 in the characteristic equation (homogeneous part), the particular solution must be multiplied by .
Incorrect! Try again.
20For the recurrence , the particular solution is 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 characteristic equation (), the particular solution is a polynomial of degree 1.
Incorrect! Try again.
21Which of the following defines the Ordinary Generating Function (OGF) for a sequence ?
A.
B.
C.
D.
Correct Answer:
Explanation:This is the standard definition of an Ordinary Generating Function.
Incorrect! Try again.
22The generating function for the sequence is:
A.
B.
C.
D.
Correct Answer:
Explanation:Using the geometric series sum formula: .
Incorrect! Try again.
23The generating function for the finite sequence is:
A.
B.
C.
D.
Correct Answer:
Explanation:.
Incorrect! Try again.
24What is the sequence generated by ?
A.
B.
C.
D.
Correct Answer:
Explanation:Expansion of geometric series with gives .
Incorrect! Try again.
25Which recurrence relation models the number of binary strings of length containing no consecutive zeros?
A.
B.
C.
D.
Correct Answer:
Explanation:If the string ends in 1, there are ways. If it ends in 0, the previous bit must be 1, so there are ways.
Incorrect! Try again.
26To solve using generating functions, if , the equation transforms to:
A.
B.
C.
D.
Correct Answer:
Explanation:Summing from : .
.
Incorrect! Try again.
27The coefficient of in the expansion of is:
A.
B.
C.
D.
Correct Answer:
Explanation:This is the formula for combinations with repetition, derived from the generalized binomial theorem.
Incorrect! Try again.
28For the recurrence relation , if we use generating functions, the denominator of will be:
A.
B.
C.
D.
Correct Answer:
Explanation:The characteristic polynomial appears in the denominator. Here .
Incorrect! Try again.
29The generating function for the sequence is:
A.
B.
C.
D.
Correct Answer:
Explanation:Start with . Differentiate: . Multiply by : .
Incorrect! Try again.
30What is the generating function for the sequence (fixed )?
A.
B.
C.
D.
Correct Answer:
Explanation:This is a standard identity. .
Incorrect! Try again.
31The convolution of two sequences and is defined as :
A.
B.
C.
D.
Correct Answer:
Explanation:This corresponds to the multiplication of their generating functions .
Incorrect! Try again.
32If is the generating function for , then generates the sequence of:
A.Differences:
B.Sums:
C.Products:
D.Shifts:
Correct Answer: Differences:
Explanation:Multiplying by corresponds to . The coefficient of becomes .
Incorrect! Try again.
33To decompose into partial fractions, we write:
A.
B.
C.
D.
Correct Answer:
Explanation:Standard partial fraction decomposition form for distinct linear factors.
Incorrect! Try again.
34Which method is best suited for solving non-homogeneous recurrence relations where the RHS is not a standard form (like or polynomial)?
A.Generating Functions
B.Characteristic Roots
C.Undetermined Coefficients
D.Guessing
Correct Answer: Generating Functions
Explanation:Generating functions can handle arbitrary sequences on the RHS by simply adding the corresponding generating function .
Incorrect! Try again.
35What is the exponential generating function (EGF) for the sequence ?
A.
B.
C.
D.
Correct Answer:
Explanation:EGF is defined as . Here , so .
Incorrect! Try again.
36Determine if its generating function is .
A.
B.
C.
D.
Correct Answer:
Explanation:Wait, this question is tricky depending on if it implies OGF or EGF. Usually 'generating function' alone implies OGF. If OGF, is coeff of . Expansion . Coeff is . If EGF, coeff of is . Given the options, usually discrete math courses teach OGF primarily unless specified. Let's assume OGF. Then . Option A. If it were EGF, the answer would be (Option B). However, is the standard EGF for . Let's refine the question to specify.
Incorrect! Try again.
37Determine the sequence if its Exponential Generating Function is .
A.
B.
C.
D.
Correct Answer:
Explanation:. Comparing coefficients, .
Incorrect! Try again.
38Solve for using generating functions. The closed form for is:
A.
B.
C.
D.
Correct Answer:
Explanation:. Multiply by , sum. .
Incorrect! Try again.
39The recurrence represents:
A.Derangements
B.Fibonacci numbers
C.Catalan numbers
D.Factorials
Correct Answer: Derangements
Explanation:This is the standard recurrence relation for the number of derangements of items.
Incorrect! Try again.
40If is the particular solution, and , the value is:
A.
B.
C.
D.
Correct Answer:
Explanation:Inverse operator rule: Replace with (base of exponential) if the denominator is not zero. Here replace with 4.
Incorrect! Try again.
41Identify the homogeneous linear recurrence relation with constant coefficients.
A.
B.
C.
D.
Correct Answer:
Explanation:Coefficients are constants (3 and 2), degree is 1 (linear), and no extra function of (homogeneous).
Incorrect! Try again.
42What is the particular solution for ? (Constant RHS)
A.
B.4
C.1/2
D.0
Correct Answer:
Explanation:Try . .
Incorrect! Try again.
43The sequence (Triangular numbers) has the generating function:
A.
B.
C.
D.
Correct Answer:
Explanation:The sequence is (shifted). Actually . Wait, standard indexing: . OGF is .
45The number of regions created by lines in a plane, where no two are parallel and no three intersect at a point, satisfies:
A.
B.
C.
D.
Correct Answer:
Explanation:The -th line intersects the previous lines at points, creating new segments, which divide existing regions into new regions.
Incorrect! Try again.
46In the operator method, is equivalent to:
A.
B.$1$
C.
D.Undefined
Correct Answer:
Explanation:This corresponds to the sum operator (inverse of difference ). .
Incorrect! Try again.
47The partial fraction expansion of helps in finding:
A.The coefficient of (the sequence )
B.The roots of the equation
C.The degree of the recurrence
D.The initial conditions
Correct Answer: The coefficient of (the sequence )
Explanation:Partial fractions allow us to express a rational generating function as a sum of simple geometric series, from which coefficients are easily extracted.
Incorrect! Try again.
48Which recurrence relation has characteristic roots ?
A.
B.
C.
D.
Correct Answer:
Explanation:Characteristic equation: .
Incorrect! Try again.
49If , what is for ?
A.
B.
C.
D.$0$
Correct Answer:
Explanation:. Series: . For , coeff is .
Incorrect! Try again.
50Solve the recurrence with .
A.$2$ if is even, if is odd
B.
C.
D.Oscillates between 2 and -2
Correct Answer: $2$ if is even, if is odd
Explanation:. It oscillates.
Incorrect! Try again.
51What is the generating function for the sequence of squares ?
A.
B.
C.
D.
Correct Answer:
Explanation:Start with . Apply operator twice. leads to .