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

Question

State pigeonhole principle. Solve the recurrence relation an = 3an-1 &#8211;  3an-2 + an-3 with initial conditions a0=1 ,a1 = 3, a2=7.

Suresh Chand · Accepted Answer

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

State pigeonhole principle. Solve the recurrence relation a_n= 3a_n-1– 3a_n-2+ a_n-3 with initial conditions a₀=1 ,a₁= 3, a₂=7.

Leave your Answer:

Hits Counter

Question

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

Leave your Answer:

State pigeonhole principle. Solve the recurrence relation a_n= 3a_n-1– 3a_n-2+ a_n-3 with initial conditions a₀=1 ,a₁= 3, a₂=7.