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
View Answer

Answer: a
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.
advertisement

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
View Answer

Answer: b
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
View Answer

Answer: c
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
View Answer

Answer: b
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
View Answer

Answer: c
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.
advertisement

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
View Answer

Answer: b
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
View Answer

Answer: a
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
View Answer

Answer: b
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
View Answer

Answer: d
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.
advertisement

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
View Answer

Answer: b
Explanation: The characteristic polynomial is x2−6x+8. By solving the characteristic equation, x2−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 an=a*2n+b*4n, for some constants a and b. Now, by using the initial conditions a0 and a1 we have: a=7/2 and b=-1/2. Therefore the solution to the recurrence relation is: an = 4 * 2n – 1*3n = 7/2 * 2n – 1/2*3n.

Sanfoundry Global Education & Learning Series – Discrete Mathematics.

To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn