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

---

excellant question which we can solve using recurrence relation expansion concept.

Answer 1

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

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

$=6n^2+2n+6(n-1)^2+2(n-1)+6(n-2)^2+2(n-2)+......+a_1$

$=6n^2+2n+6(n-1)^2+2(n-1)+6(n-2)^2+2(n-2)+......+6.1^2+2.1$

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

$=6\times \frac{n(n+1)(2n+1)}{6} \;+ \; 2 \times\frac{n(n+1)}{2}$

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

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

for $n=99 \; \;a_{99}=2\times 99 \times(99+1)^2 =198 \times 10^4$

Comments

SInce the summation starts from 2 shudn't we subtract the value 1 from each of the term ( sum of squares and sum of n natural numbers)

---

a1 value is 8 right where did it get substituted in the expansion?

---

8 is divied into 6 + 2

Answer 2

Here's the easiest way to solve this:

Taking $a_{n-1}$ to LHS,

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

Taking summation,

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

 

LHS becomes:

 $\sum a_{n} - \sum a_{n-1}= (a_{n}+\sum a_{n-1}) - \sum a_{n-1}=a_{n}$

so our equation reduces to:

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

Putting n = 99 as asked in the question,

$a_{99} = 99*100*199 + 99*100 = 1980000 = K * 10^{4} $

So K =198. Now wasn't this easy.?

---------------------------------------------------------------------------

p.s.:

$1+2+3+.....+n=\sum{n}=\frac{n(n+1)}{2}$

$1^{2}+2^{2}+3^{2}+.....+n^{2}=\sum{n^{2}}=\frac{n(n+1)(2n+1)}{6}$

$1^{3}+2^{3}+3^{3}+.....+n^{3}=\sum{n^{3}}=\left[\frac{n(n+1)}{2}\right]^{2}=\frac{n^{2}(n+1)^{2}}{4}$

Comments

Please check my above comment

You may add above step to your answer just for better understanding.

Your observation is very nice

thanks to giving such an awesome answer

---

$$\sum a_n - \sum a_{n-1} = (a_n + \sum a_{n-1}) - \sum a_{n-1} = a_n$$ is not correct, it is recurrence not partial sum, so $$\sum a_n - \sum a_{n-1}= a_n - a_1$$ if n starts from 2.
   so,$$a_n=a_1+6 \sum_{k=2}^{n} k^2 + 2 \sum_{k=2}^{n} k$$

---

This procedure was expected from us

Answer 3

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

Solution = Homogeneous Solution + Particular Solution .................$(1)$

$Homogeneous\ Solution$,
$a_n=a_{n-1}$
$a_n-a_{n-1}=0$

let, $a_n = x$
$x -1 = 0$
$x = 1$

$Homogeneous \ Solution=d*1^n = d$.......................................$(2)$

$ Particular\ Solution :$
Here, $F(x) = 6n^2 + 2n$                                  // Quadratic

let us assume, $a_n = (an^2 + bn + c)*n$         // here root of homogeneous solution is 1 so we have to multiply General quadratic solution by n. ........................$(3)$

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

$={n*(an^2 + bn + c) - (n-1)*(a(n-1)^2 + b(n-1) + c)}$
$= an^3 + bn^2 + cn - ( an^3 - a -3an^2 +3an + bn^2 + b - 2bn +cn - c )$
$= ( an^3 + bn^2 + cn - an^3 + a +3an^2 -3an - bn^2 - b + 2bn - cn + c )$
$= 3an^2 + (2b-3a)n + (a-b+c)$

Apply Principle of Homogeneity,

$3a =6$                $2b -3a= 2$                    $a-b+c =0$
 $a = 2$                        $b = 4$                                       $c = 2$

Now put values in equation $(3)$,

$Particular\ Solution = n*(2n^2 + 4n +2) = 2n^3 + 4n^2 + 2n$ ..................$(4)$

from equation $(1), (2)$ and $(4)$

Solution of recurrence  $= 2n^3 + 4n^2 + 2n +d$

here $a(1) = 8$                                                                 //given
by putting $n = 1, d=0$

Final Solution of recurrence $= 2n^3 + 4n^2 + 2n = 2n(n+1)^2$

Value of $a(99) = 2×99×(10)^4 = 198*10^4$

So, $K$ value is $198$

Comments

why to multiply by 'n' ??

---

@ jatin khachane 1 characteristic root of the equation is 1 means homogeneous solution will be constant ,particular solution have also constant part ($an^2+bn+c$) so to differentiate that multiply by n is done there.

---

That's the proper way....
Well explained :)

Answer 4

why is everyone doing this hard way?

This solution is given,but still

convert recurrence relation to an-(an-1)=6n^2+2n

now all you have to do is apply summation to RHS,

6n^2 converts to n(n+1)(2n-1) (6 gets cancelled) and 2n^2 converts to n(n+1)

so final equation is n(n+1)(2n+1)+n(n+1),putting n =99 answer comes as 1980000,  198*10^4

Comments

How u converted "6n^2 converts to n(n+1)(2n-1) (6 gets cancelled) and 2n^2 converts to n(n+1)"??

---

Its basically a summation of n^2 and 'n' ,comment below will demonstrate the step and reason to apply summation.

Answer 5

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

Comments

Nice Answer .

---

Proper answer

Answer 6

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.