Generating Functions

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Generating Functions

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

greenplanet2050

1324 posts

greenplanet2050

#1 h Apr 29, 2025, 10:42 PM

Y by

So im learning generating functions and i dont really understand why $1+2x+3x^2+4x^3+5x^4+…=\dfrac{1}{(1-x)^2}$

can someone help

thank you

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

26 posts

Yiyj

#2 h Apr 29, 2025, 10:54 PM

Y by

Note that $1+2x+3x^2+\cdots$ is an arithmetico-geometric sequence. Then, we have the formula $\sum_{k=1}^{\infty} x_k = \dfrac{dg_2}{(1-r)^2} + \dfrac{x_1}{1-r},$ where $d$ is the common difference of the arithmetic sequence, $r$ is the common ratio of the geometric sequence, $g_2$ is the second term of the geometric sequence, and $x_k$ are the terms of the arithmetico-geometric sequence.

Plugging in $d=1, r=x, g_2=x, x_1=1$ , we get $1+2x+3x^2+\cdots=\dfrac{x}{(1-x)^2}+\dfrac{1}{1-x} = \dfrac{x}{(1-x)^2}+\dfrac{1-x}{(1-x)^2} = \boxed{\dfrac{1}{(1-x)^2}}.$ Hope that helped!

This post has been edited 1 time. Last edited by Yiyj, Apr 29, 2025, 10:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

381 posts

Shan3t

#3 h Apr 29, 2025, 11:00 PM

Y by

greenplanet2050 wrote:

So im learning generating functions and i dont really understand why $1+2x+3x^2+4x^3+5x^4+…=\dfrac{1}{(1-x)^2}$

can someone help

thank you

Let $1+2x+3x^2\cdots = S.\quad(1)$

Now multiply $S,$ by $x,$ to get:

$x+2x^2+3x^3+4x^4+\cdots = S\cdot x\quad(2)$

Just subtract equation $2$ from equation $1,$ to get $1+x+x^2+x^3\cdots = \frac{1}{1-x} = S-S\cdot x.$ Simplify this, gives $S(1-x)=\frac1{1-x}\implies S=\frac{1}{(1-x)^2}.$

This post has been edited 1 time. Last edited by Shan3t, Apr 29, 2025, 11:02 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

207 posts

#4 h Apr 30, 2025, 12:52 AM

Y by

Notice that $(1+x+x^2+x^3...)^2 = 1+2x+3x^2+4x^3...$ (this can be elementarily proven with induction by counting the pairs for each coefficient's term)

Since the value of a geometric sequence that goes $1+x+x^2+x^3...$ is $\frac{1}{1-x}$ , we square that to get our answer of $\frac{1}{(1-x)^2}$

This post has been edited 2 times. Last edited by martianrunner, Apr 30, 2025, 2:36 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

greenplanet2050

1324 posts

greenplanet2050

#5 h Apr 30, 2025, 1:18 AM

Y by

Thank you all!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

381 posts

Shan3t

#6 h Apr 30, 2025, 3:00 AM

Y by

greenplanet2050 wrote:

Thank you all!!

np

also @2bove sol very clean

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ohiorizzler1434

786 posts

ohiorizzler1434

#7 h Apr 30, 2025, 6:56 AM • 1 Y

Y by compoly2010

It's a highly technical concept that combines convergence of geometric sequences with calculus, to represent the power series of a function around a point!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2975 posts

#8 h Apr 30, 2025, 4:35 PM

Y by

In general, the ring $\mathbb{C}[x]$ of all polynomials with complex coefficients is spanned by the basis $\{p_n\}_{n=0}^\infty$ where $p_n(x)=(x+1)(x+2)\cdots(x+n)$ under finite linear combinations. Note that $p_0(x)=1$ since it is the empty product.

Using this and the power rule for derivatives, we can find a formula for $\sum_{n=0}^\infty p(n)x^n$ for any polynomial $p$ and any $x\in(-1,1)$ .

The idea is that $S_k(x)=\sum_{n=0}^\infty p_k(n)x^n=\sum_{n=0}^\infty\frac{d^k}{dx^k}x^{n+k}=\sum_{n=-k}^\infty\frac{d^k}{dx^k}x^{n+k}=\sum_{n=0}^\infty\frac{d^k}{dx^k}x^n=\sum_{n=0}^\infty\frac{d^k}{dx^k}x^n=\frac{d^k}{dx^k}\sum_{n=0}^\infty x^n=\frac{d^k}{dx^k}\frac{1}{1-x}=\frac{k!}{(1-x)^{k+1}}$ .

So all you have to do is write $p$ of degree $n$ , as $p=\sum_{k=0}^nc_kp_k$ .

Example:
Find $\sum_{n=0}^\infty(n^3+5n^2-3n+4)x^n$ .

Solution:
Use $p_0(n)=1$ , $p_1(n)=n+1$ , $p_2(n)=(n+1)(n+2)=n^2+3n+2$ , and $p_3=(n+1)(n+2)(n+3)=n^3+6n^2+11n+6$ .

$c_0p_0(n)+c_1p_1(n)+c_2p_2(n)+c_3p_3(n)=c_3n^3+(c_2+6c_3)n^2+(c_1+3c_2+11c_3)n+(c_0+c_1+2c_2+6c_3)\equiv n^3+5n^2-3n+4$
$\implies\begin{cases}c_3=1\\c_2+6c_3=5\\c_1+3c_2+11c_3=-3\\c_0+c_1+2c_2+6c_3=4\end{cases}\implies(c_0,c_1,c_2,c_3)=(11,-11,-1,1)$

Therefore $\sum_{n=0}^\infty(n^3+5n^2-3n+4)x^n=11S_0(x)-11S_1(x)-S_2(x)+S_3(x)=\frac{11}{1-x}-\frac{11}{(1-x)^2}-\frac{2}{(1-x)^3}+\frac{6}{(1-x)^4}=\frac{-11x^3+22x^2-9x+4}{(1-x)^4}$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a