NEOCODE

Math MCQs

Recurrence Relation

1. Which of the following is a linear homogeneous recurrence relation of order 2

a) a_n = 2a_n-1 + 3 b) a_n = 3a_n-1 - a_n-2 c) a_n = a²_n-1 + a_n-2 d) a_n = 2a_n+1

2. What is the characteristic equation of the recurrence relation a_n = 5 a_n-1 - 6a_n-2?

a) r² - 5r + 6 = 0 b) r² + 5r - 6 = 0 c) r² - 6r + 5 = 0 d) r² + 6r - 5 = 0

3. What is the initial condition required to solve the recurrence relation a_n = 2a_n-1 + 3?

a) only a₀ b) both a₀ and a₁ c) Any two consecutive terms d) No initial conditions needed

4. Which technique is often used to solve linear homogeneous recurrence relations?

a) Induction b) Generating functions c) The characteristic root method d) Substitution method

5. The Fibonacci sequence is defined by which recurrence relation?

a) a_n = a_n-1 + a_n-2 b) a_n = 2a_n-1 - a_n-2 c) a_n = a_n-1 + n d) a_n = 2a_n-1

Modelling with Recurrence Relation

6. What is the recurrence relation for the Tower of Hanoi problem?

a) T(n) = 2T(n-1) + 1 b) T(n) = T(n-1) + n c) T(n) = T(n-2) + 2 d) T(n) = 3T(n-1)

7. How does binary search’s recurrence relation look?

a) T(n) = T(n/2) + c b) T(n) = 2T(n/2) + c c) T(n) = T(n-1) + n d) T(n) = nT(n-1)

8. Which recurrence relation describes the number of subsets of a set with n elements?

a) S(n) = 2S(n-1) b) S(n) = S(n-1) + S(n-2) c) S(n) = S(n-1) + n d) S(n) = nS(n-1)

9. Which recurrence relation models the cost of a recursive binary search?

a) T(n)=T(n/2)+c b) T(n)=T(n−1)+c c) T(n)=2T(n/2)+c d) T(n)=T(n/2)−c

10. A savings account starts with $1000 and earns 5% interest per year. Which recurrence relation models the account balance?

a) B_n = 1.05B_n-1 b) B_n = B_n-1 + 0.05 c) B_n = B_n-1 - 0.05 d) B_n = 1.05B_n-1 + 1000

Mixed Questions

11.The solution to the recurrence relation a_n = 3a_n-1 -2a_n-2 is

a) Geometric sequence b) Exponential sequence c) Polynomial sequence d) Fibonacci sequence

12. What is the closed-form solution of the recurrence relation a_n = a_n-1 + d(arithmetic sequence)

a) a_n = a₀ + dn b) a_n = a₀ * dⁿ c) a_n = a₀ + d^n-1 d) a_n = a₀n + d

13. Which recurrence relation models the number of ways to tile a 2×n board using 2×1 dominoes?

a) T(n)=T(n−1)+T(n−2) b) T(n)=2T(n−1) c) T(n)=T(n−1)+n d) T(n)=T(n−1)−T(n−2)

14. What’s the solution to the recurrence relation a_n = 2a_n-1 with a₀ = 3

a) a_n = 3 * 2ⁿ b) a_n = 2n + 3 c) a_n = 3n² d) a_n = 3 + 2n

15. In modeling the growth of a bacteria colony that triples every hour, the recurrence relation would be:

a) B_n = 3B_n-1 b) B_n = B_n-1 + 3 c) B_n = B³_n-1 d) B_n = 3n

Your Score: /15