+1 vote
278 views
Use generating function to solve the recurrence relation $a_k=3{a_{k-1}} + 2$ with initial conditions $a_0=1$.

edited | 278 views
+2

@Abhinavg ,please correct me if anything is wrong..

0
Yes it is right but we have to do more to reach to a general form , and apply partial fraction after that ,  as done by pankaj_vlr.
+1

using linenar non homogenous method, assume k=n

0
with generating function :)
0
:P , life will be easy :D
0
life will be easy when we don't need to do by non-homogenous eq method or generating function. Maybe some time-saving solutions.
0
plz,how question solved using complementary and particular function? can you provide proper link or pdf for this theory.
0
0

## 1 Answer

+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$
by Boss (10.8k points)
edited
0
$a_{k}-a_{k-1}=2$

how??
0
$T\left ( n \right )=3T\left ( n-1 \right )+2$

$T\left ( n-1 \right )=3T\left ( n-2 \right )+2$

$T\left ( n-2 \right )=3T\left ( n-3 \right )+2$

...................................

replacing in T(n)

$T\left ( n \right )=3T\left ( n-1\right )+2$

$T\left ( n \right )=3\left [ 3T\left ( n-2\right )+2 \right ]+2$

$T\left ( n \right )=3^{2}T\left ( n-2 \right )+3.2+2$

$T\left ( n \right )=3^{3}T\left ( n-3 \right )+3^{2}.2+3.2+2$

--------------------------------------------------------------------------------

$T\left ( n \right )=3^{n}T\left ( 1 \right )+3^{n-1}.2+......3^{2}.2+3.2+2$

$T\left ( n \right )=3^{n}.1+3^{n-1}.2+......3^{2}.2+3.2+2$

$T\left ( n \right )=3^{n}+2\left [ 3^{n-1}+......3^{2}+3+1 \right ]$

$T\left ( n \right )=3^{n}+2\frac{3^{n-1}-1}{3-1}$

$T\left ( n \right )=3^{n}+3^{n-1}-1$
0
actually, it is $a_{k} - 3a_{k-1} = 2$
0

its ak - 3ak-1 = 2 ,rest is done right , maybe he missed there.

I was stuck at the partial fraction part .

0
@pankaj

yes mostly correct

check this line

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

how $a_{k-1}$??

according to ur equation it should be $a_{k}$
0
we need $x^k$ not $x^{k+1}$
0
given in the question

+1 vote
1 answer
1
0 votes
0 answers
2
+2 votes
1 answer
3
+1 vote
1 answer
4