The Gateway to Computer Science Excellence
+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 $.
in Combinatory by (455 points)
edited by | 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 by
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
198,338 comments
105,026 users