GATE CSE 2005 | Question: 50

Question

Let $G(x) = \frac{1}{(1-x)^2} = \sum\limits_{i=0}^\infty g(i)x^i$, where $|x| < 1$. What is $g(i)$?

• A. $i$
• B. $i+1$
• C. $2i$
• D. $2^i$

Comments

Sumbody answer this ???b is the answer by putting x=0 but how to solve such types

---

Why don't use the same method?

https://en.wikipedia.org/wiki/Taylor_series

---

Yes but how to use compare them there are g(i) and Gx i know its easy but couldnt get it now

---

https://gateoverflow.in/88476/generating-function

---

 @Arjun sir has mentioned the correct link. We can use the Taylor series also.

We can write the Taylor series about origin for the given generating function as :

$f(x) = a_{0} x^{0} + a_{1} x^{1} +a_{2} x^{2}+a_3 x^3+........= \sum_{n}^{} \frac{f^{(n)}(0)}{n!}x^n$ for $n=0,1,2,3,....$

So, for any ordinary generating function,

sequence is : $ a_n= \frac{f^{(n)}(0)}{n!},$ for $n=0,1,2,3,.........$

Here, $f^{(n)}$ means $n^{th}$ derivative of $f$.

Now here, generating function $f(x)=\frac{1}{(1-x)^2}$  and

$ g(i)= \frac{f^{(i)}(0)}{i!},$ for $i=0,1,2,3,.........$

Now,

$f(x)= \frac{1}{(1-x)^2}$

$f'(x)= \frac{1\times2}{(1-x)^3}$

$f''(x)= \frac{1\times 2\times 3}{(1-x)^4}$

$f'''(x)= \frac{1\times 2\times 3 \times 4}{(1-x)^5}$

$.......$

$f^{(i)}(x)= \frac{1\times 2\times 3 \times .......\times (i+1)}{(1-x)^{i+2}}$ $\Rightarrow f^{(i)}(0)= (i+1)!$

So, $g(i) = \frac{f^{(i)}(0)}{i!} = \frac{(i+1)!}{i!} = i+1$

---

$\color{red}{\text{Detailed Video Solution:}}$ GATE 2005 Generating Function, Click HERE.

$\color{red}{\text{Generating Function Complete Playlist,}}$ ALL GATE Questions, Extended Binomial Theorem: https://youtube.com/playlist?list=PLIPZ2_p3RNHiu4mkROrhREYsslvp2lL5l 

Knowing the “Extended Binomial Theorem” makes Generating Function topic extremely easy. Watch the above playlist to learn everything, with Proof & Variations. 

---

Alternative Approach :

YOU NEED NOTHING NO GENERATING FUNCTION, NO EXTENTDED BINOMIAL THEOREM YOU JUST NEED Direct Mapping  with INFINITE AGP SUM:

{obviously it's very much necessary to know extended binomial theorem and coefficient, which Deepak sir taught very well and in-depth, but for this problem it can be solved in a much much faster and easier way}

---

The Intuition: Why map to an AGP series?

When tackling this problem, the intuition to use an Arithmetico-Geometric Progression (AGP) comes directly from observing two key parts of the given equation:

1. The Summation Structure: We are given the series as $\sum_{i=0}^{\infty} g(i)x^i$. This structure shows that it's just an AGP, where $x^i$ acts as the Geometric Progression (GP) term, and the coefficient $g(i)$ acts as the Arithmetic Progression (AP) term.

2. The Closed-Form Result: The generating function evaluates to $\frac{1}{(1-x)^2}$. This looks very similar to the standard formula for the sum of an infinite AGP: $\frac{a}{1-r} + \frac{dr}{(1-r)^2}$ (where $r = x$).

1. The Standard AGP Infinite Sum

For an infinite AGP series where $\vert{}x\vert{} < 1$:

$$S_{\infty} = a + (a+d)x + (a+2d)x^2 + \dots + (a+id)x^i + \dots$$

The sum is defined as:

$$S_{\infty} = \frac{a}{1-x} + \frac{dx}{(1-x)^2}$$

Note: In this standard series, the coefficient $g(i)$ for the $x^i$ term is always exactly $(a + id)$.

2. Equate to the Given Generating Function

We are given the function $G(x) = \frac{1}{(1-x)^2}$. Let's equate this directly to the standard AGP sum:

$$\frac{1}{(1-x)^2} = \frac{a}{1-x} + \frac{dx}{(1-x)^2}$$

To find $a$ and $d$, unify the right side under a common denominator:

$$\frac{1}{(1-x)^2} = \frac{a(1-x) + dx}{(1-x)^2}$$

$$\frac{1}{(1-x)^2} = \frac{a - ax + dx}{(1-x)^2}$$

$$\frac{1}{(1-x)^2} = \frac{a + (d-a)x}{(1-x)^2}$$

3. Solve for the Variables

Since the denominators match, we simply compare the numerators:

$$1 = a + (d-a)x$$

• Constant term: $a = 1$

• Coefficient of $x$: There is no $x$ term on the left side, so $d - a = 0 \implies d = 1$

4. Extract $g(i)$

We now know this specific AGP starts at $a = 1$ with a common difference $d = 1$.

To find $g(i)$, which is the coefficient of $x^i$, we plug these into our coefficient formula $(a + id)$:

$$g(i) = 1 + i(1)$$

$$g(i) = i + 1$$

Therefore, Option B is the correct answer.

---

superb!!!

Answer 1

$\frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + x^5 + \dots + \infty$

Differentiating it w.r.to $x$

$\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + 5x^4 + \dots + \infty$

$\sum_{i=0}^{\infty} g(i)x^i = g(0) + g(1)x + g(2)x^2 + g(3)x^3 + \dots + \infty$

Comparing above two, we get $g(1) = 2, g(2) = 3 \color{red}{\Rightarrow g(i) = i+1}$

Correct Answer: B

Comments

Some important $GF:$

---

good approach.....

---

At least write copy paste from ROSEN. LOL

Answer 2

Using the extended Binomial theorem, we can write it as:

$(1-x)^{-2} = \sum_{i = 0}^{\infty}$${-n \choose k}(-x)^k$

From, this the coefficient can be written as: ${n+i-1} \choose i$, where $i = 2$

Therefore, $g(i) = \frac{(i+1)!}{i!} = i+1$

Comments

How can you take combination of negative numbers, like you did in $-n \choose k$ and how did you arrive at $n+i-1 \choose i$? Please elaborate your answer.

---

@rawan https://www.youtube.com/watch?v=ZyUb5UxBA9Q&index=13&list=PLDDGPdw7e6Aj0amDsYInT_8p6xTSTGEi2&t=0s

Check this out. 

---

Great approach. That’s what I call an answer.

---

it wil be where n = 2

Answer 3

We can use Maclaurin series $1/(1-x) = 1+x+x^{2}+x^{3}+x^{4}+...$

differentiating both side by x gives $1/(1-x)^{2} = 0+1+2x+3x^{2}+4x^{3}+...$

comparing this with given equaion $1/(1-x)^{2} = \sum g(i)x^{i} = g(0)+g(1)x+g(2)x^{2}+g(3)x^{3}+...$

$g(i)=i+1$

Option B

Answer 4

Option B) is the answer 

Answer 5

$G(x)=\frac{1}{(1-x)^2} = (1-x)^{-2}$

Now we can expand $(1-x)^{-2}$ using negative binomial series theorem

$(1-x)^{-2}$

$= 1 +2x + \left ( \frac{1}{1*2}\ 2*3\  \right )x^2+ \left ( \frac{1}{1*2*3}\ 2*3*4\  \right )x^3+ \left ( \frac{1}{1*2*3*4}\ 2*3*4*5\  \right )x^4+...$

$= 1x^0+ 2x^1 +3x^2 + 4x^3+...$

We can clearly see that $g(i)$ is $i+1$

$\therefore$ Option $B.$ is correct answer.

Answer 6

Lets solve this using backtracking

With practice you will learn how to get G(x)