Question

Find the generating function from the recurrence relation given by

S(K) – 6 S( K – 1) + 5 S(K – 2) = 0, where S(0) = 1, S(1) = 2.​

Answer 1

Given recurrence relation :  S(K) – 6 S( K – 1) + 5 S(K – 2) = 0

$where$ $S(0) = 1$$, S(1) = 2$

$S(K) -6 S( K -1) + 5 S(K-2) =0$

$The$ $auxillary$ $equation$ $is$  $a^{2} -6a + 5 = 0$

$Factorizing$ $the$ $above$ $eqn$ $we$ $get$,

$(a-5)(a -1)=0$

$Hence$  $a=5,1$

$s^{H}$(k) = $A_{1}$$5^{k}$  + $A_{2}$$1^{k}$              -----------------$eq (1)$

$When$ $s(0)=1$        $s(0)$ = $A_{1} +A_{2}$                           $[ Since s(0)=1] Given$

$A_{1} +A_{2}=1$                          ---------------- $eq (2)$

$When$ $s(1)=2$         $s(1)$ =$5A_{1} +A_{2}$                         $[ Since s(1)=2 ] Given$

$5A_{1} +A_{2}=2$                       ----------------- $eq(3)$

$From (2) and (3) we get$

$A1 = 0.25\\A2 = 0.75$

$Using$ $the$ $above$ $given$ $eqn$ $and$ $subst.$  

$s^{H}(k) = (0.25)5^{k} + (0.75)1^{k} \\\\s^H(k)=\frac{1}{4} (5^{k} + 3)$

Hence the generating function is  $s^H(k)=\frac{1}{4} (5^{k} + 3)$