The GATE Grind

GATE 2016 CS (CS1) – Question 37

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Numerical answer

Consider the recurrence relation $a_1 = 8$, $a_n = 6n^2 + 2n + a_{n-1}$. Let $a_{99} = K \times 10^4$. The value of $K$ is ________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 197.9 to 198.1

Explanation

Unroll $a_n=a_{n-1}+6n^2+2n$ with $a_1=8$. Since $6(1)^2+2(1)=8$, the initial value fits the same formula, so
$$a_n=\sum_{k=1}^{n}(6k^2+2k).$$

Use $\sum k^2=\dfrac{n(n+1)(2n+1)}{6}$ and $\sum k=\dfrac{n(n+1)}{2}$ with $n=99$:
$$a_{99}=6\cdot\frac{99\cdot100\cdot199}{6}+2\cdot\frac{99\cdot100}{2}=1{,}970{,}100+9{,}900=1{,}980{,}000.$$

$1{,}980{,}000=198\times10^4$, so $K=\mathbf{198}$.

More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions

All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →