GATE Overflow | Mock GATE | Test 1 | Question: 11

Question

Which one of the following best expresses the generating function sequence $\{a_n\}$, for the given closed form representation?
$$F(x) = \frac{1}{1-x-x^2}$$

• A. $a_n=a_{n-1}+3, n>0, a_0=1$
• B. $a_n=a_{n-1}+a_{n-2}, n>1, a_0=1, a_1=1$
• C. $a_n=2n+3, n>1$
• D. $a_n=2a_{n-1}+3, n>1, a_0=1$

Comments

Its a generating function for fibonacci series so option B is correct.

https://math.stackexchange.com/questions/338740/the-generating-function-for-the-fibonacci-numbers

Initially I solved like -

$\frac{1}{1-x-x^{2}} = \frac{1}{1-(x+x^{2})} = 1 + (x+x^2) + (x+x^2)^2+(x+x^2)^3+ ........$

I solved it till $x^3$ to get require coefficient value which was sufficient to select answer.

---

@Swapnil Naik is there any other easy method?

and a0 is given as 0?(we have 1 in expansion so coefficient of x^0 is 1)

---

I don't know any other method to find it yet, I will let you know if I find one.

Yes, I think $a_0$ should have been 1, as we are getting series {1,1,2,3,5,...}

---

@Arjun Sir, the question needs an edit I guess.. the closed form representation when $a_0=0$ is $F(x)=\frac{x}{1-x-x^2}$ and when $a_0=1$ then it is $F(x)=\frac{1}{1-x-x^2}$

Ref: https://gateoverflow.in/82451/gate1987-10b

Answer 1

check this out &&&&++++()()()()

Comments

is this valid?

---

The issue with the given method is that you can’t say that the sequence which you are getting is a fibonacci sequence.

Here, you are getting 1,1,2,3,5,8,13,…

Is it a Fibonacci sequence ?

What If 100^th term is not the sum of previous two terms ? How can you prove that it is a Fibonacci sequence based on some initial numbers ?

This method is mentioned in the above math.stackexchange link also but it is for understanding and might work in exams but mathematics does not work like that.

You need to prove the recurrence which a Fibonacci sequence follows and here you can’t get the remainder as 0 because Fibonacci sequence does not end somewhere. It is defined for all natural numbers.

Here, you have to do the reverse procedure to get the desired recurrence which you do to get the generating function from a recurrence.