edited by
3,155 views
1 votes
1 votes
Use generating function to solve the recurrence relation $a_k=3{a_{k-1}} + 2$ with initial conditions $a_0=1 $.
edited by

1 Answer

2 votes
2 votes
$eq.1 \rightarrow$  $G(x) = \sum_{k = 0}^{\infty }a_{k}x^k$

 multiply $G(x)$ with $3x$, we get

$eq.2 \rightarrow$  $3x.G(x) = \sum_{k = 0}^{\infty }3.a_{k}.x^{k+1}$

 

$eq.1 - eq.2$

 

$(1-3x).G(x) = \sum_{k = 0}^{\infty }a_{k}x^{k} - \sum_{k = 0}^{\infty }3.a_{k}.x^{k+1}$

                     $= a_{0} + \sum_{k = 1}^{\infty }a_{k}x^{k} - \sum_{k = 1}^{\infty }3a_{k-1}x^{k}$

                     $= a_{0} + \sum_{k = 1}^{\infty }(a_{k} - 3a_{k-1})x^{k}$

                     $= 1 + \sum_{k = 1}^{\infty }2x^{k}$                                              $\because a_{k} - 3a_{k-1} = 2$

                     $= 1 + 2\sum_{k = 1}^{\infty }x^{k}$

                     $= 1 + 2x/1-x$                                                       $\because$ sum of infinite GP

                     $= (1 - x + 2x)/1-x$

                     $= (1 + x)/1-x$

 

$G(x)= (1 + x)/(1-x)(1-3x)$

 

By using partial fraction,

$(1 + x)/(1-x)(1-3x) = A/(1-x) + B/(1-3x)$

$(1 + x)/(1-x)(1-3x) = (A+B) + (-3A -B)/(1-x)(1-3x)$

on comparing $LHS$ and $RHS$, we get

$A+B = 1$

$-3A-B = 1$

on solving these equation, we get $A = -1$ and $B = 2$

 

$(1 + x)/(1-x)(1-3x) = -1/(1-x) + 2/(1-3x)$

 

$-1/(1-x) + 2/(1-3x) = -\sum_{k=0}^{\infty }x^k + 2\sum_{k=0}^{\infty } 3^kx^k$       $\because  1/(1-ax) = \sum_{k=0}^{\infty } a^kx^k$

$\sum_{k=0}^{\infty } (2.3^k - 1)x^k$

 

coefficient of $x^k$ is $2.3^k - 1$

 

$a_{k} =  2.3^k - 1$
edited by

Related questions

1 votes
1 votes
1 answer
4
Ayush Upadhyaya asked Sep 27, 2018
661 views
Find the closed form for the generating function for the sequence $\{a_n\}$ where(a)$a_n=\binom{n}{2}$ for $n=0,1,2....$(b)$a_n=\binom{10}{n+1}$ for $n=0,1,2....$