GATE CSE 2016 Set 1 | Question: 27

Question

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 __________.

Comments

How to solve this Qs by Generating Function?

---

@Warrior

https://gateoverflow.in/39714/gate2016-1-27?show=332838#a332838

Answer 1

K = 198

Recurrence is solved by

an = (2n+1)(n)(n+1) + n(n+1)

a99 = (199)(99)(100) + (99)(100) = 1980000

Comments

Plz tell me where I am wrong in this approach. I am unable to get the correct answer :

T(1) = 8

T(n) = T(n-1) + 6n^2 + 2n

T(n-1) = T(n-2) + 6(n-1)^2 + 2(n-1)       ..................

After substitution , 

T(n) = T(n-i) + 6{n^2 + (n-1)^2 + (n-2)^2 + .... + (n-(i+1))^2} + 2{n + (n-1) + (n-2) + .... + (n-(i+1))}

if n-i = 1 => i = n-1 

Substitute this in above equation , 

T(n) = T(1) + 6{n^2 + (n-1)^2 + (n-2)^2 + .... + ( n-( (n-1) + 1 ))^2} + 2{n + (n-1) + (n-2) + .... + (n-( (n-1) + 1))}

T(n) = T(1) + 6{n^2 + (n-1)^2 + (n-2)^2 + .... + (0)^2} + 2{n + (n-1) + (n-2) + .... + (0))}

T(n) = 8 + sum of squares upto n terms + sum of natural number upto n terms

This way the term 8 stays in the equation and doesnt go away. Plz help :(

---

i think  T(n) should be  T(n-i) + 6{n^2 + (n-1)^2 + (n-2)^2 + .... + (n-(i-1))^2} + 2{n + (n-1) + (n-2) + .... + (n-(i-1))}

---

Same doubt as yours. Please explain why term a1 was not substituted by 8 in the best marked answer

Edit: I got it now. My bad. Went wrong with computation.

Answer 2

$a_{n} - a_{n-1} = 6n^2 + 2n$

$a_{2} - a_{1} = 6*(2)^2 + 2*(2)$

$a_{3} - a_{2} = 6*(3)^2 + 2*(3)$

$a_{4} - a_{3} = 6*(4)^2 + 2*(4)$

$.$

$.$

$.$

$.$

$a_{n} - a_{1} = 6*(n)^2 + 2*(n)$

on adding we get

$a_{n} - a_{1} = 6*[2^2 +3^2 + 4^2 + ...+ n^2] + 2*[2 + 3 + 4 + 5 + ...n]$

$a_{n}  = 6*[2^2 +3^2 + 4^2 + ..+ n^2] + 2*[2 + 3 + 4 + 5 + ...n] +a_{1} $

$a_{n}  = 6*[2^2 +3^2 + 4^2 + ...+ n^2] + 2*[2 + 3 + 4 + 5 + ...n] + 8 $

$a_{n}  = 6*[2^2 +3^2 + 4^2 + ...+ n^2] + 2*[2 + 3 + 4 + 5 + ...n] + 6*1^2 + 2*1 $

$a_{n}  = 6*[1^2 + 2^2 +3^2 + 4^2 + ...+ n^2] + 2*[1 + 2 + 3 + 4 + 5 + ...n]  $

$a_{n}  = 6*( n * ( n+1) * (2n+1) )/6 + (2*n*(n+1))/2$

$a_{n}  = n * ( n+1) * (2n+1)  + n*(n+1)$

$a_{n}  = n * ( n+1) * (2n+1  + 1)$

$a_{n}  = 2*n * ( n+1)^2$

on putting n = 99, we get

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

$a_{n}  = 198 * ( 100)^2$

$a_{n}  = 198 * ( 10)^4$

$K = 198$

Answer 3

$a_{n} = 6n^{2} + 2n+a_{n-1}\rightarrow(1)$

$a_{1} = 8,a_{0} = 0$

We can rewrite the equation $(1),$ and get

$\implies a_{n}-a_{n-1} = 6n^{2} + 2n$

$a_{1}-a_{0} = 6(1)^{2} + 2(1)$

$a_{2}-a_{1} = 6(2)^{2} + 2(2)$

$a_{3}-a_{2} = 6(3)^{2} + 2(3)$

$a_{4}-a_{3} = 6(4)^{2} + 2(4)$

$\:\:\:\:\:\:\:\:\Large\vdots$

$a_{98}-a_{97} = 6(98)^{2} + 2(98)$

$a_{99}-a_{98} = 6(99)^{2} + 2(99)$

________________________________________________________

$a_{99}-a_{0} = 6\left[1^{2} + 2^{2} + 3^{2} + \dots + 99^{2} \right] + 2\left[1+2+3+\dots + 99 \right]$

$\implies K \times 10^{4} - 0 = 6\left[\dfrac{99\times 100 \times 199}{6}\right]  + 2\left[\dfrac{99\times 100}{2}\right] $

$\implies K \times 10^{4} =9900 \times 199 +9900$

$\implies K \times 10^{4} =9900 (199 +1)$

$\implies K \times 10^{4} =9900 \times 200$

$\implies K \times 10^{4} =1980000$

$\implies K \times 10^{4} =198\times 10^{4}$

$\therefore K = 198$

So, the correct answer is $198.$

Answer 4

If the relation is like the one given i.e. a_n - a_n-1 = f(n), the we can use the formula:

a_n = a₀  + summation(f(n))[from a₁ to a_n]

so here a_n = a₀ + summation(6n² + 2n) and use the summation formula for n and n².(here a₀ = 0, derived using a₁)

Comments

@jatinmittal..cn u tell me the other forms also ?

---

No idea for any other forms.