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

1. Consider the recurrence relation a_{1}=4, a_{n}=5n+a_{n-1}. The value of a_{64} is _________

a) 10399

b) 23760

c) 75100

d) 53700

View Answer

Explanation: a

_{n}=5n+a

_{n-1}

= 5n + 5(n-1) + … + a

_{n-2}

= 5n + 5(n-1) + 5(n − 2) +…+ a

_{1}

= 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

_{64}= 10399.

2. Determine the solution of the recurrence relation F_{n}=20F_{n-1} − 25F_{n-2} where F_{0}=4 and F_{1}=14.

a) a_{n} = 14*5^{n-1}

b) a_{n} = 7/2*2^{n}−1/2*6^{n}

c) a_{n} = 7/2*2^{n}−3/4*6^{n+1}

d) a_{n} = 3*2^{n}−1/2*3^{n}

View Answer

Explanation: The characteristic equation of the recurrence relation is → x

^{2}−20x+36=0

So, (x-2)(x-18)=0. Hence, there are two real roots x

_{1}=2 and x

_{2}=18. Therefore the solution to the recurrence relation will have the form: a

_{n}=a2

^{n}+b18

^{n}. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 4=a2

^{0}+b18

^{0}=a+b and 3=a2

^{1}+b6

^{1}=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

^{n}−1/2*6

^{n}.

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

View Answer

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, b

_{n}=4b

_{n-1}+3 is the recurrence relation and the initial condition is b

_{0}=1.

4. If S_{n}=4S_{n-1}+12n, where S_{0}=6 and S_{1}=7, find the solution for the recurrence relation.

a) a_{n}=7(2^{n})−29/6n6^{n}

b) a_{n}=6(6^{n})+6/7n6^{n}

c) a_{n}=6(3^{n+1})−5n

d) a_{n}=nn−2/6n6^{n}

View Answer

Explanation: The characteristic equation of the recurrence relation is → x

^{2}−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

^{n}+b.n.6

^{n}. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 6=a6

^{0}+b.0.6

^{0}=a and 7=a6

^{1}+b.1.6

^{1}=2a+6b. Solving this system gives a=6 and b=6/7. So the solution to the recurrence relation is, a

_{n}=6(6

^{n})−6/7n6

^{n}.

5. Find the value of a_{4} for the recurrence relation a_{n}=2a_{n-1}+3, with a_{0}=6.

a) 320

b) 221

c) 141

d) 65

View Answer

Explanation: When n=1, a

_{1}=2a

_{0}+3, Now a

_{2}=2a

_{1}+3. By substitution, we get a

_{2}=2(2a

_{0}+3)+3.

Regrouping the terms, we get a

_{4}=141, where a

_{0}=6.

6. The solution to the recurrence relation a_{n}=a_{n-1}+2n, with initial term a_{0}=2 are _________

a) 4n+7

b) 2(1+n)

c) 3n^{2}

d) 5*(n+1)/2

View Answer

Explanation: When n=1, a

_{1}=a

_{0}+2. By substitution we get, a

_{2}=a

_{1}+2 ⇒ a

_{2}=(a

_{0}+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_{0}=3 and b_{1}=4.

a) 7/2*2^{n}−1/2*6^{n}

b) 2/3*7^{n}-5*4^{n}

c) 4!*6^{n}

d) 2/8^{n}

View Answer

Explanation: Rewrite the recurrence relation b

_{n}-8b

_{n-1}+12b

_{n-2}=0. Now from the characteristic equation: x

^{2}−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

^{n}+c6

^{n}. To find b and c, set n=0 and n=1 to get a system of two equations with two unknowns: 3=b2

^{0}+c6

^{0}=b+c, and 4=b2

^{1}+c6

^{1}=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

^{n}−1/2*6

^{n}.

8. What is the solution to the recurrence relation a_{n}=5a_{n-1}+6a_{n-2}?

a) 2n^{2}

b) 6n

c) (3/2)n

d) n!*3

View Answer

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 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_{0}=3.

a) 4387

b) 5484

c) 238

d) 1437

View Answer

Explanation: When n=1, a

_{1}=17a

_{0}+30, Now a

_{2}=17a

_{1}+30*2. By substitution, we get a

_{2}=17(17a

_{0}+30)+60. Then regrouping the terms, we get a

_{2}=1437, where a

_{0}=3.

10. Determine the solution for the recurrence relation a_{n} = 6a_{n-1}−8a_{n-2} provided initial conditions a_{0}=3 and a_{1}=5.

a) a_{n} = 4 * 2^{n} – 3^{n}

b) a_{n} = 3 * 7^{n} – 5*3^{n}

c) a_{n} = 5 * 7^{n}

d) a_{n} = 3! * 5^{n}

View Answer

Explanation: The characteristic polynomial is x

^{2}−6x+8. By solving the characteristic equation, x

^{2}−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

^{n}+b*4

^{n}, for some constants a and b. Now, by using the initial conditions a

_{0}and a

_{1}we have: a=7/2 and b=-1/2. Therefore the solution to the recurrence relation is: a

_{n}= 4 * 2

^{n}– 1*3

^{n}= 7/2 * 2

^{n}– 1/2*3

^{n}.

**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__.