GATE Overflow Test Series | Discrete Mathematics | Test 3 | Question: 6

Question

What is the solution to the recurrence relation $a_{n} = a_{n-1} + n$ with $a_{0} = 0$?

• A. $a_{n} = \dfrac{n(n-1)}{2} $
• B. $a_{n} = \dfrac{(n-1)(n+1)}{2} $
• C. $a_{n} = \dfrac{(n-1)(n+1)}{4} $
• D. $a_{n} = \dfrac{n(n+1)}{2} $

Answer 1

This recurrence is actually calculating the sum of the first $n$ natural numbers which is given by $\dfrac{n.(n+1)}{2}.$
We can formally prove this as follows.

• $a_{n} = a_{n-1} + n \rightarrow(1)$
• $a_{n-1} = a_{n-2} + n-1 \rightarrow(2)$
• $a_{n-2} = a_{n-3} + n-2 \rightarrow(3)$

Substitute the value in equation $(1)$, and get the term,

• $a_{n} = a_{n-1} + n $
• $a_{n-1} = a_{n-2} + n-1 + n $
• $a_{n-2} = a_{n-3} + n-2 + n-1 + n$
• $\hspace{1.5cm}\vdots$
• for $i^{th}$ term,
• $a_{n} = a_{n-i} + \big(n-(i-1)\big) + \big(n-(i-2)\big) + \dots (n-1) + (n-0)$

Given that $a_{0} = 1\implies i = n.$

• $a_{n} = a_{0} + \big(n-(n-1)\big) + \big(n-(n-2)\big) + \dots (n-1) + (n-0)$
• $a_{n} = a_{0} + 1 + 2 + 3 + \dots + n $
• $a_{n} = 0 + 1 + 2 + 3 + \dots + n $
• $a_{n} = \dfrac{n(n+1)}{2} $

So, the correct answer is $(D)$.

Answer 2

The recurrence relation becomes 

t(n)= t(n-1)+n

     and can be resolved using substitutions. Hence t(n)= n(n+1)/2    option D is correct