The Gateway to Computer Science Excellence
+35 votes
7.3k views
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 __________.
in Combinatory by Loyal (7.2k points)
edited by | 7.3k views
+3

How to solve this Qs by Generating Function?

8 Answers

+129 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$
by Veteran (56.6k points)
selected by
0
why we are not soving this quest using conventional method for linear non-homogenous method?
+4
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$.
+2
@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
Got it. Thanks for correcting.
0
I am getting

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.
+1
Praveen saini,
you represented a1 as 6.1+2.1.
Can we do that? Because then a0 is unknown,how can we assume a0 to be 0.
a1=6.1+2.1+a0
(I think i will answer this myself , value of n cannot be negative because input size cannot be negative)
0
Since we don't know value of $a_{0}$...shouldn't the series be expanded till $a_{2}$ only?
0
great explanation !!
0

Well explained.Thanks:)

0
Thank you so much, sir, give Very good answer
0
use of a1 is missing , answer is correct but solving mistake
+34 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$
by Veteran (60.4k points)
edited by
+19

By linear non homogenous recurrence relation

if an - an-1=f(n)

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

In question an -an-1=6n2+2n

where f(n)=6n2+2n

then an=a0+6*$\sum_{i=1}^{n} i^2$ +2*$\sum_{i=1}^{n} i$

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

a0=0;

an=2n(n+1)2

n=99

a99=198*104

so, k=198

0
@One

How have u taken a0=0?

N can u provide any reference for the method u have mentioned?
+2
@VS

Substitute n=1 in original recurrence equation.

8 = 6 . 1 + 2 . 1 + $a_{0}$

Hence $a_{0}$ = 0
0

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

a= a0 +$\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

an = an-1 
an - an-1 = 0

let an = x after this line how come we got an-1 as 1 @Digvijay Pandey 

x -1 = 0 
x = 1

0
why to multiply by 'n' ??
0

 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.

0
That's the proper way....
Well explained :)
+8 votes
K = 198

Recurrence is solved by

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

a99 = (199)(99)(100) + (99)(100) = 1980000
by (457 points)
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 :(

0

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

0
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.
+7 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
by Active (2k points)
0
How u converted "6n^2 converts to n(n+1)(2n-1) (6 gets cancelled) and 2n^2 converts to n(n+1)"??
0
Its basically a summation of n^2 and 'n' ,comment below will demonstrate the step and reason to apply summation.
+7 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)$

 

We can write like this

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

 

Example for the above statement:

        For the $AP:2,4,6,8 $ to get the $4^{th}$ term, $(2+4+6+8)- (2+4+6) = 8$

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


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

by Active (3.3k points)
edited by
0

 

We know that $\sum a_{n} - \sum a_{n-1}$ is nothing but $a_{n}$,

How can you explain a bit more$?$

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
0

I'm not a sir

I'm also an aspirant like yours, please do not call me sir

Yes you are right

 $\sum a_{n} - \sum a_{n-1}$

We can write like this

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

0
Corrected.😁
+1
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
+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$
by Boss (10.6k points)
edited by
+4 votes

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

an = a0  + summation(f(n))[from a1 to an]

so here an = a+ summation(6n2 + 2n) and use the summation formula for n and n2.(here a0 = 0, derived using a1)

by Active (1.2k points)
0
@jatinmittal..cn u tell me the other forms also ?
0
No idea for any other forms.
+4 votes

watch step by step soln. of above problem 

by (113 points)
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,159 answers
193,767 comments
93,761 users