GATE Overflow Test Series | Mock GATE | Test 2 | Question: 28

Question

The generating function for the sequence with recurrence relation $a_n=3a_{n-1}-a_{n-2}$ with initial terms $a_0=1$ and $a_1=5$ is.

• A. $\frac{1+2x}{1-3x+x^2}$
• B. $\frac{1-2x}{1-3x+x^2}$
• C. $\frac{1+2x}{1+3x+x^2}$
• D. $\frac{1+x}{1-3x+x^2}$

Answer 1

The ordinary generating function for the infinite sequence $\langle a_{0}, a_{1}, a_{2}, a_{3},\dots \rangle$ is the power series:

$G(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + \dots$

Given that $:a_{n} = 3a_{n-1} - a_{n-2},a_{0} = 1,a_{1} = 5$

$a_{n}- 3a_{n-1} + a_{n-2} = 0 \quad \rightarrow (1)$

Now $,a_{2} = 3a_{1} - a_{0} = 3(5) - 1 = 15 - 1 = 14$

$a_{3} = 3a_{2} - a_{1} = 3(14) - 5 = 42 - 5 = 37$

$a_{4} = 3a_{3} - a_{2} = 3(37) - 14 = 111 - 14 = 97$

We can write the ordinary generating function,

$G(x) = 1 + 5x + 14 x^{2} + 37x^{3} + 97x^{4} + \dots$

$-3xG(x) = -3x - 15x^{2} - 42x^{3} - 111x^{4} - \dots $

$x^{2}G(x) = \qquad x^{2} + 5x^{3} + 14 x^{4} + 37x^{5} + 97x^{6} + \dots$

Adding all the equations, we get,

$G(x) - 3xG(x) + x^{2}G(x) = 1 + 2x + 0$

$\implies (1 - 3x + x^{2})G(x) = 1 + 2x$

$\implies G(x) = \dfrac{1+2x}{1-3x+x^{2}}$

So, the correct answer is $(A).$

References:

• https://www.math.cmu.edu/~lohp/docs/math/2011-228/mit-ocw-generating-func.pdf
• https://www.youtube.com/watch?v=Pp4PWCPzeQs

Comments

good one

---

is there any way to solve all type generating func in one way?

Answer 2

Just Used the property of Generating function
G^n(0) = n! an
which means
G^n ==> n time differentiation for eg , G(0) =a0 , G’(0)= 1! a1 ,G’’(0) =2!a2
So here If u put G(0) in every option it gives ans 1 and they given a0 =1 so all option matches
Now if u take differentiation using u/v rule and put the value 0 , u have to match with a1 which is 5 , So option A only matches