250+ TOP MCQs on Advanced Counting Techniques – Recurrence Relation

Discrete Mathematics Multiple Choice Questions on “Advanced Counting Techniques – Recurrence Relation”.

1. Consider the recurrence relation a₁=4, a_n=5n+a_n-1. The value of a₆₄ is _________
a) 10399
b) 23760
c) 75100
d) 53700

Answer: a
Clarification: a_n=5n+a_n-1
= 5n + 5(n-1) + … + a_n-2
= 5n + 5(n-1) + 5(n − 2) +…+ a₁
= 5n + 5(n-1) + 5(n − 2) +…+ 4 [since, a1=4]
= 5n + 5(n-1) + 5(n − 2) +…+ 5.1 – 1
= 5(n + (n − 1)+…+2 + 1) – 1
= 5 * n(n+1)/ 2 – 1
a_n = 5 * n(n+1)/ 2 – 1
Now, n=64 so the answer is a₆₄ = 10399.

2. Determine the solution of the recurrence relation F_n=20F_n-1 − 25F_n-2 where F₀=4 and F₁=14.
a) a_n = 14*5^n-1
b) a_n = 7/2*2ⁿ−1/2*6ⁿ
c) a_n = 7/2*2ⁿ−3/4*6ⁿ⁺¹
d) a_n = 3*2ⁿ−1/2*3ⁿ

Answer: b
Clarification: The characteristic equation of the recurrence relation is → x²−20x+36=0
So, (x-2)(x-18)=0. Hence, there are two real roots x₁=2 and x₂=18. Therefore the solution to the recurrence relation will have the form: a_n=a2ⁿ+b18ⁿ. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 4=a2⁰+b18⁰=a+b and 3=a2¹+b6¹=2a+6b. Solving this system gives b=-1/2 and a=7/2. So the solution to the recurrence relation is,
a_n = 7/2*2ⁿ−1/2*6ⁿ.

3. What is the recurrence relation for 1, 7, 31, 127, 499?
a) b_n+1=5b_n-1+3
b) b_n=4b_n+7!
c) b_n=4b_n-1+3
d) b_n=b_n-1+1

Answer: c
Clarification: Look at the differences between terms: 1, 7, 31, 124,…. and these are growing by a factor of 4. So, 1⋅4=4, 7⋅4=28, 31⋅4=124, and so on. Note that we always end up with 3 less than the next term. So, b_n=4b_n-1+3 is the recurrence relation and the initial condition is b₀=1.

4. If S_n=4S_n-1+12n, where S₀=6 and S₁=7, find the solution for the recurrence relation.
a) a_n=7(2ⁿ)−29/6n6ⁿ
b) a_n=6(6ⁿ)+6/7n6ⁿ
c) a_n=6(3ⁿ⁺¹)−5n
d) a_n=nn−2/6n6ⁿ

Answer: b
Clarification: The characteristic equation of the recurrence relation is → x²−4x-12=0
So, (x-6)(x+2)=0. Only the characteristic root is 6. Therefore the solution to the recurrence relation will have the form: a_n=a.6ⁿ+b.n.6ⁿ. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 6=a6⁰+b.0.6⁰=a and 7=a6¹+b.1.6¹=2a+6b. Solving this system gives a=6 and b=6/7. So the solution to the recurrence relation is, a_n=6(6ⁿ)−6/7n6ⁿ.

5. Find the value of a₄ for the recurrence relation a_n=2a_n-1+3, with a₀=6.
a) 320
b) 221
c) 141
d) 65

Answer: c
Clarification: When n=1, a₁=2a₀+3, Now a₂=2a₁+3. By substitution, we get a₂=2(2a₀+3)+3.
Regrouping the terms, we get a₄=141, where a₀=6.

6. The solution to the recurrence relation a_n=a_n-1+2n, with initial term a₀=2 are _________
a) 4n+7
b) 2(1+n)
c) 3n²
d) 5*(n+1)/2

Answer: b
Clarification: When n=1, a₁=a₀+2. By substitution we get, a₂=a₁+2 ⇒ a₂=(a₀+2)+2 and so on. So the solution to the recurrence relation, subject to the initial condition should be a_n=2+2n=2(1+n).

7. Determine the solution for the recurrence relation b_n=8b_n-1−12b_n-2 with b₀=3 and b₁=4.
a) 7/2*2ⁿ−1/2*6ⁿ
b) 2/3*7ⁿ-5*4ⁿ
c) 4!*6ⁿ
d) 2/8ⁿ

Answer: a
Clarification: Rewrite the recurrence relation b_n-8b_n-1+12b_n-2=0. Now from the characteristic equation: x²−8x+12=0 we have x: (x−2)(x−6)=0, so x=2 and x=6 are the characteristic roots. Therefore the solution to the recurrence relation will have the form: b_n=b2ⁿ+c6ⁿ. To find b and c, set n=0 and n=1 to get a system of two equations with two unknowns: 3=b2⁰+c6⁰=b+c, and 4=b2¹+c6¹=2b+6c. Solving this system gives c=-1/2 and b=7/2. So the solution to the recurrence relation is, b_n=7/2*2ⁿ−1/2*6ⁿ.

8. What is the solution to the recurrence relation a_n=5a_n-1+6a_n-2?
a) 2n²
b) 6n
c) (3/2)n
d) n!*3

Answer: b
Clarification: Check for the left side of the equation with all the options into the recurrence relation. Then, we get that 6n is the required solution to the recurrence relation a_n=5a_n-1 + 6a_n-2.

9. Determine the value of a2 for the recurrence relation a_n = 17a_n-1 + 30n with a₀=3.
a) 4387
b) 5484
c) 238
d) 1437

Answer: d
Clarification: When n=1, a₁=17a₀+30, Now a₂=17a₁+30*2. By substitution, we get a₂=17(17a₀+30)+60. Then regrouping the terms, we get a₂=1437, where a₀=3.

10. Determine the solution for the recurrence relation a_n = 6a_n-1−8a_n-2 provided initial conditions a₀=3 and a₁=5.
a) a_n = 4 * 2ⁿ – 3ⁿ
b) a_n = 3 * 7ⁿ – 5*3ⁿ
c) a_n = 5 * 7ⁿ
d) a_n = 3! * 5ⁿ

Answer: b
Clarification: The characteristic polynomial is x²−6x+8. By solving the characteristic equation, x²−6x+8=0 we get x=2 and x=4, these are the characteristic roots. Therefore we know that the solution to the recurrence relation has the form a_n=a*2ⁿ+b*4ⁿ, for some constants a and b. Now, by using the initial conditions a₀ and a₁ we have: a=7/2 and b=-1/2. Therefore the solution to the recurrence relation is: a_n = 4 * 2ⁿ – 1*3ⁿ = 7/2 * 2ⁿ – 1/2*3ⁿ.