GATE CS 2016 Set 1 Q27 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We are given the recurrence relation:

$$a_1 = 8$$

$$a_n = 6n^2 + 2n + a_{n-1} \quad \text{for } n \ge 2$$

By unfolding the recurrence, we can express $a_n$ as a summation:

$$a_n = a_1 + \sum_{i=2}^{n} (6i^2 + 2i)$$

Notice that for $i = 1$, the term $6i^2 + 2i$ evaluates to:

$$6(1)^2 + 2(1) = 8 = a_1$$

Thus, we can rewrite the entire expression as a single summation starting from $i = 1$:

$$a_n = \sum_{i=1}^{n} (6i^2 + 2i)$$

Using the standard summation formulas:

• $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
• $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

We substitute these formulas into the expression for $a_n$:

$$a_n = 6 \left[ \frac{n(n+1)(2n+1)}{6} \right] + 2 \left[ \frac{n(n+1)}{2} \right]$$

$$a_n = n(n+1)(2n+1) + n(n+1)$$

Factoring out $n(n+1)$:

$$a_n = n(n+1) \left[ (2n+1) + 1 \right]$$

$$a_n = n(n+1)(2n+2)$$

$$a_n = 2n(n+1)^2$$

Now, we calculate $a_{99}$ by substituting $n = 99$:

$$a_{99} = 2 \times 99 \times (99+1)^2$$

$$a_{99} = 198 \times (100)^2$$

$$a_{99} = 198 \times 10^4$$

Comparing this with $a_{99} = K \times 10^4$, we get:

$$K = 198$$