# Discrete Mathematics Questions and Answers – Advanced Counting Techniques – Recurrence Relation

«
»

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Advanced Counting Techniques – Recurrence Relation”.

1. Consider the recurrence relation a1=4, an=5n+an-1. The value of a64 is _________
a) 10399
b) 23760
c) 75100
d) 53700

Explanation: an=5n+an-1
= 5n + 5(n-1) + … + an-2
= 5n + 5(n-1) + 5(n − 2) +…+ a1
= 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
an = 5 * n(n+1)/ 2 – 1
Now, n=64 so the answer is a64 = 10399.

2. Determine the solution of the recurrence relation Fn=20Fn-1 − 25Fn-2 where F0=4 and F1=14.
a) an = 14*5n-1
b) an = 7/2*2n−1/2*6n
c) an = 7/2*2n−3/4*6n+1
d) an = 3*2n−1/2*3n

Explanation: The characteristic equation of the recurrence relation is → x2−20x+36=0
So, (x-2)(x-18)=0. Hence, there are two real roots x1=2 and x2=18. Therefore the solution to the recurrence relation will have the form: an=a2n+b18n. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 4=a20+b180=a+b and 3=a21+b61=2a+6b. Solving this system gives b=-1/2 and a=7/2. So the solution to the recurrence relation is,
an = 7/2*2n−1/2*6n.

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

Explanation: 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, bn=4bn-1+3 is the recurrence relation and the initial condition is b0=1.

4. If Sn=4Sn-1+12n, where S0=6 and S1=7, find the solution for the recurrence relation.
a) an=7(2n)−29/6n6n
b) an=6(6n)+6/7n6n
c) an=6(3n+1)−5n
d) an=nn−2/6n6n

Explanation: The characteristic equation of the recurrence relation is → x2−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: an=a.6n+b.n.6n. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 6=a60+b.0.60=a and 7=a61+b.1.61=2a+6b. Solving this system gives a=6 and b=6/7. So the solution to the recurrence relation is, an=6(6n)−6/7n6n.

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

Explanation: When n=1, a1=2a0+3, Now a2=2a1+3. By substitution, we get a2=2(2a0+3)+3.
Regrouping the terms, we get a4=141, where a0=6.

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

Explanation: When n=1, a1=a0+2. By substitution we get, a2=a1+2 ⇒ a2=(a0+2)+2 and so on. So the solution to the recurrence relation, subject to the initial condition should be an=2+2n=2(1+n).

7. Determine the solution for the recurrence relation bn=8bn-1−12bn-2 with b0=3 and b1=4.
a) 7/2*2n−1/2*6n
b) 2/3*7n-5*4n
c) 4!*6n
d) 2/8n

Explanation: Rewrite the recurrence relation bn-8bn-1+12bn-2=0. Now from the characteristic equation: x2−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: bn=b2n+c6n. To find b and c, set n=0 and n=1 to get a system of two equations with two unknowns: 3=b20+c60=b+c, and 4=b21+c61=2b+6c. Solving this system gives c=-1/2 and b=7/2. So the solution to the recurrence relation is, bn=7/2*2n−1/2*6n.

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

Explanation: 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 an=5an-1 + 6an-2.

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

Explanation: When n=1, a1=17a0+30, Now a2=17a1+30*2. By substitution, we get a2=17(17a0+30)+60. Then regrouping the terms, we get a2=1437, where a0=3.

10. Determine the solution for the recurrence relation an = 6an-1−8an-2 provided initial conditions a0=3 and a1=5.
a) an = 4 * 2n – 3n
b) an = 3 * 7n – 5*3n
c) an = 5 * 7n
d) an = 3! * 5n 