Question

Consider the recurrence relation a1=4, an=5n+an-1. The value of a64 is _________

(a) 10399

(b) 23760

(c) 75100

(d) 53700

The question was asked during an internship interview.

I'm obligated to ask this question of Advanced Counting Techniques in portion Counting of Discrete Mathematics

Answer 1

The correct option is (a) 10399

The explanation is: 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.