**How to solve this Qs by Generating Function?**

The Gateway to Computer Science Excellence

+46 votes

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

+154 votes

Best answer

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

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

+5

I don't know "what are the methods for solving recurrence" so I can't say which is better to use or not use. Well, You can solve by the method you know, as answer will be same.

0

Solving by NH linear recurrence method is a bit time consuming for this one. I tried that one in exam, but did some calculation mistakes. The iterative method as Praveen sir did, is simpler in this case.

+2

This question can't be solved by method of linear non-homogeneous because this is not a linear recurrence relation. It involves a term having $n^2$.

+5

@Gaurav Sharma, here 'linear' is for terms of recurrence a(n), not for n. So, it is linear. It is non-homogeneous. It can be solved by that method. I did, and I got right answer, as anyone else would as well :D Just try once ;)

0

I am getting

a(n)=n^2+n+6 using recurrance method and got wrong answer.

can you show how you solved.

a(n)=n^2+n+6 using recurrance method and got wrong answer.

can you show how you solved.

0

use this u wll get right answer pg 523 of rosen 7th edition

Suppose that {an} satisfies the linear nonhomogeneous recurrence relation an = c1an−1 + c2an−2 +···+ ckan−k + F (n), where c1, c2,...,ck are real numbers, and F (n) = (btnt + bt−1nt−1 +···+ b1n + b0)sn, where b0, b1,...,bt and s are real numbers. When sis not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form (ptnt + pt−1nt−1 +···+ p1n + p0)sn. When s is a root of this characteristic equation and its multiplicity is m, there is a particular solution of the form nm(ptnt + pt−1nt−1 +···+ p1n + p0)sn.

Suppose that {an} satisfies the linear nonhomogeneous recurrence relation an = c1an−1 + c2an−2 +···+ ckan−k + F (n), where c1, c2,...,ck are real numbers, and F (n) = (btnt + bt−1nt−1 +···+ b1n + b0)sn, where b0, b1,...,bt and s are real numbers. When sis not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form (ptnt + pt−1nt−1 +···+ p1n + p0)sn. When s is a root of this characteristic equation and its multiplicity is m, there is a particular solution of the form nm(ptnt + pt−1nt−1 +···+ p1n + p0)sn.

+40 votes

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

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$

+23

By linear non homogenous recurrence relation

if a_{n} - a_{n-1}=f(n)

then solution a_{n}=a_{0} +$\sum_{i=1}^{n}$ f(i)

In question a_{n} -a_{n-1}=6n^{2}+2n

where f(n)=6n^{2}+2n

then a_{n}=a_{0}+6*$\sum_{i=1}^{n} i^2$ +2*$\sum_{i=1}^{n} i$

a_{n}=a_{0}+2n(n+1)^{2}

a_{0}=0;

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

n=99

a_{99}=198*10^{4}

so, k=198

+4

0

Can anyone tell me How #one get that line ??

a_{n }= a_{0} +$\sum_{i=1}^{n}$ f(i) ...

is it by substituting $a_{n } - a_{n-1}$ = 0 then $a_{n }= a_{n-1}$

$a_{1 }= a_{0}$ ....

$a_{2 }= a_{1}$ ....

$a_{n-1 }= a_{0}$

anyone ???

0

a_{n} = a_{n-1}

a_{n} - **a _{n-1}** = 0

**let a _{n} = x **after this line how come we got

x -**1** = 0

x = 1

0

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

+20 votes

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

0

0

Isn't the difference of the sum up to n terms of a series and n-1 terms of the series the nth term itself?

eg. for the AP 2,4,6,8 for the 4th term, (2+4+6+8)- (2+4+6) = 8

For the GP: 3,9,27,81 for the 3rd term, (3+9+27) - (3+9) = 27

eg. for the AP 2,4,6,8 for the 4th term, (2+4+6+8)- (2+4+6) = 8

For the GP: 3,9,27,81 for the 3rd term, (3+9+27) - (3+9) = 27

+11 votes

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

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

+8 votes

K = 198

Recurrence is solved by

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

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

Recurrence is solved by

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

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

0

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 :(

+6 votes

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

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

52,315 questions

60,436 answers

201,769 comments

95,247 users