State pigeonhole principle. Solve the recurrence relation a= 3an-1 –  3an-2 + an-3 with initial conditions a0=1 ,a= 3, a2=7.

This answer is restricted. Please login to view the answer of this question.

Login Now

Pigeonhole principle states taht if n items are put into m contines with n > m, then at least one container must contain more than one item. For example if one has three gloves then one must have at least two right hand gloves or at least two left hand gloves because one has three objects, but only two categories of handed ness to put then into.

Given recurrance relation is

an = 3an-1 – 3an-2 + an-3

Here, degree = 3

The characeristics equation is

r3 = 3r2 – 3r + 1

or, r3 – 3r2 – 3r + 1 = 0

Solving, We get

(r-1)(r-1)(r-1) = 0

r = 1 i.e. r1 = r2 = r3 = 1

Now, The general solution of homogenuous equation is:

an = A1r1n + A2nr2n + A3n2r3n

an = A11n + A2 . n . (1)n + A3 . n2 . (1)n

an = A1 + A2n + A3n2  ——–(i)

Given condition are

a0 = 0    ∴ n = 0

From equation (i):

a0 = A1 + A2 . 0 + A3 . 0

∴ A1 = 1   ——(ii)

Also,  a1 = 3    ∴ n = 1

a1 = A1 + A2 + A3

3 = 1 + A2 + A3

A2 + A3 = 2   ——–(iii)

Also, a2 = 7   ∴ n = 2

a2 = A1 + A2 . 2 + A3 . (2)2

7 = 1 + 2A2 + 4A3

2A2 + 4A3 = 6

A2 + 2A3 = 3   ——- (iv)

Solving equation (iii) and (iv), We get

A3 = 1 and A2 = 1

Hence, We get A1 = 1, A2 = 1 and A3 = 1

From equation (i), the general solution is

an = 1 + n + n2

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .