0
votes
2answers
40 views

Problem understanding notation

I'm learning about generating functions and in the opening explanations my book (and various sources) claim: $$a_n = 1 \forall n \in \mathbb{N}_0, \ \ \ f(x) = \frac{1}{1-x}$$. I read this as: ...
5
votes
2answers
65 views

Closed form of generating function consisting of power of two binomials

Let $g(x)$ be infinite formal power series and $$g(x) = (1 + x)(1 + x^2)\cdots(1 + x^{2^k})\cdots$$ Show that $(1 - x) g(x) = 1$. My book gives following proof: Using a fact that $(1 - x^k)(1 + ...
1
vote
1answer
24 views

Find the closed formula for the number of ways to get n dollars using coins of 1, 2 and 5 dollars

Ok, this is going to be a long one. So, using generating functions I have to find a closed formula for the number of ways to get n dollars if I have infinite amounts of coins of 1, 2 and 5 dollars. ...
1
vote
1answer
55 views

Proof that the series for the generating function of the partition function converges?

For $|q| < 1$, the generating function of the partition function $p(n)$ is given by $$ \sum_{n=0}^\infty p(n) q^n = \prod_{k=1}^\infty {1 \over 1-q^k}. \tag{1} $$ I have an intuitive ...
0
votes
1answer
48 views

generating function of a sequence

There are n lines drawn in a plane such that no 2 lines are parallel and no 3 lines are concurrent. If the plane is then divided into an regions prove that a1=2 a2=4 a(n)=a(n-1)+n for n>=2 Find the ...
1
vote
2answers
37 views

Multiplicative Inverse for Generating Function

I have a question based on Irreducible and Connected Permutations. I was able to use the notion of connected permutations to construct a combinatoric proof for \begin{equation} ...
3
votes
1answer
232 views

How to identify this power series as $k\sin(k/x)$?

In this question, a functional equation is solved for functions with a power series. We find a recursive formula: (copied from the answer by user achille hui) \begin{align} ( 2^1 - 3 ) a_2 &= 0\\ ...
4
votes
1answer
67 views

Why do convergence issues not play a role when talking of generating functions

This question has been on my mind for some while now. Perhaps it has a very simple answer. When we talk of generating functions we take a series $\sum a_ix^i$ and do not usually bother about it as a ...
1
vote
1answer
56 views

Generating function of $(n+1) 2^n a_n$

Given that $f(x)$ is the generating function of $a_n$ ($f(x)=\sum_{n=0}^{\infty}a_n x^n$), find the generating function of $(n+1) 2^n a_n$. The generating function with $n\ge0$ is: ...
0
votes
2answers
70 views

What is $\sum_{k=0}^\infty k^2\cdot x^k$?

I was learning generating functions and met this summation. I used maple and it gave $-\frac{x(x+1)}{(x-1)^3}$, but how does it get here? I've forgotten most of the knowledge about series. Does anyone ...
2
votes
2answers
139 views

The meaning of Generating functions

I had a look to this video on the field of series and sequences which I know not much about! This guy looked for the generating function of $a_n = 2a_{n-1} + 4a_{n-2}$ with $a_0=1$ and $a_1=3$. The ...
2
votes
3answers
88 views

Power series for $(1+x^3)^{-4}$

I am trying to find the power series for the sum $(1+x^3)^{-4}$ but I am not sure how to find it. Here is some work: $$(1+x^3)^{-4} = \frac{1}{(1+x^3)^{4}} = \left(\frac{1}{1+x^3}\right)^4 = ...
0
votes
2answers
37 views

algebraic manipulation question

$M_{z_n}(t)$ is a particular moment generating function, and it is given that $\lambda_n$ approaches $\infty$ as $n$ approaches $\infty$: Could someone help me see how the above was derived?
1
vote
1answer
95 views

Trying to find more information about “Darboux's method/theorem” on coefficients of an analytic function

My supervisor briefly showed me a statement of something she called "Darboux's theorem," but I am having trouble finding more information about it on the internet. Here is what I have written down ...
3
votes
2answers
100 views

Change of a variable in a generating function

Assuming I have a generating function $$\sum_n c(m,n,k)x^n=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$ (mentioned in this answer where $c$ represents the number of compositions of $n$ to $k$ parts of ...
2
votes
1answer
85 views

Combinatorics of the Zeta function of a variety

I want to know if there is a good combinatorial interpretation of what the Zeta function of a variety $X$ over a finite field $\mathbb{F}_p$ counts. It is defined as $$\exp\sum N_j/j\,t^j,$$ where ...
5
votes
3answers
306 views

Compositions of $n$ with largest part at most $m$

This is a problem from Stanley's Enumerative Combinatorics that I'm failing at a bit (lot): Let $\bar{c}(m,n)$ denote the number of compositions of $n$ with largest part at most $m$. Show that ...
1
vote
2answers
98 views

Expanding $\frac{1}{1-z-z^2}$ to a power series.

How would you expand the analytic function $$\frac{1}{1-z-z^2}$$ to a series of the form $$\sum_{k=0}^\infty a_k z^k \, \, ?$$
3
votes
1answer
101 views

Bivariate generating functions and diagonal like recurrences

I'm trying to solve recurrences of the type $$a(n,m) = \sum_{k=0}^{m} a(n-k,k), \qquad a(n,0)= a(0,m)=1 \qquad (A_0)$$ with the help of generating functions, but I get stuck quite early on. If I ...
1
vote
3answers
70 views

Coefficients of series given by generating function

How to find the coefficients of this infinite series given by generating function.$$g(x)=\sum_{n=0}^{\infty}a_nx^n=\frac{1-11x}{1-(3x^2+10x)}$$ I try to expand like Fibonacci sequences using geometric ...
2
votes
2answers
707 views

Using Generating Functions to Solve Recursions

I have the recursion $A(n) = A(n-1) + n^2 - n$ with initial conditions $A(0) = 1$. I attempted to solve it using generating functions and I'm not quite sure I have it right, so I thought I might ask ...
2
votes
1answer
102 views

Coefficients of Generating Functions

This problem is from Stanley's Enumerative Combinatorics: Volume 1. page 115 here for those desirous of context (prettier conTeXt). Anyway, it asks for fixed $j,k\in \mathbb{Z}$ to show that ...
1
vote
3answers
46 views

Rational polynomial from coefficents

Given two polynomials $$ p(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{n-1}x^{n-1} \\ q(x) = b_0 + b_1 x + b_2 x^2 + \ldots + b_{n}x^{n} $$ And the series expansion from their rational polynomial $$ ...
2
votes
1answer
143 views

applying multi-section formula to find convergence

The question asks to use the multi-section technique to determine if $$\sum_{n>=0} (a^n)/(4n +1)!$$ converges, and to provide a finite expression for the exact value of the series. The multi ...
2
votes
0answers
282 views

Prove that sum is finite with the help of generating function

Please help me to prove that the following sum is finite $$ \sum_{j=2l-2}^{\infty}j!\, a_j^{(l)}, $$ here the generating function of $\displaystyle{a_j^{(l)}}$ is ...
4
votes
4answers
140 views

Bell Numbers: How to put EGF $e^{e^x-1}$ into a series?

I'm working on exponential generating functions, especially on the EGF for the Bell numbers $B_n$. I found on the internet the EGF $f(x)=e^{e^x-1}$ for Bell numbers. Now I tried to use this EGF to ...
1
vote
1answer
203 views

Fibonacci Generating Function of a Complex Variable

So I'm doing work on the Fibonacci Numbers, and I came across this problem for the generating function for the recursive fibonacci numbers. I have two questions: 1. Why is it useful to use a ...
4
votes
4answers
153 views

Expansion of $x^4\over1+x^2$ into a power series

I calculated the generating function $A(x)$ of the recurrence $a_n = a_{n-2} - 2a_{n-3}$, $(n \ge 0, a_0 = a_1 = 0, a_2 = 2)$ and I have no clue on how to expand it into a power series in order to ...
0
votes
5answers
2k views

How to find closed form expression for a power series.

How can I find a closed form expression for the following series: $$ \sum_{n\geq 1} n! x^n $$
0
votes
1answer
89 views

How can we take a power series and multiply each term, i.e. $c_n x^n$ by $y^n$?

In other words, given a power series $f(x)$, is there an alternative to taking $\lim_{x\to{x y}}f(x)$? I ask this because I thought that there may be a way to replace the limit by integration, or ...
6
votes
1answer
598 views

Equation about generating functions and subfactorial

Suppose $G_n(w)$ is a formal power series (really a probability generating function, see the following explanation) of variable $w$, try to solve out $G_n(w)$ for all $n\ge0$ from the ...
6
votes
3answers
267 views

When can we plug an arbitrary number into an equation on formal power series

We often ignore convergence when manipulating formal power series. We can add, substract, multiply, divide, differentiate, and do functional composition on such formal sums without worrying about ...
14
votes
3answers
638 views

Solving a difficult recursion via generating functions

I have been trying to solve the recurrence: \begin{align*} a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3}, \end{align*} where $a_0=5$, via generating functions with little success. My progress until now is ...
0
votes
0answers
87 views

Is there any way to create (a closed form for) this power series/generating function?

There is a fairly simple pattern to it. $$1 y + $$ $$(1 + 1x)y^2+ $$ $$(1+1x+1x^2 + 1x^3)y^3 + $$ $$(1+1x+\dots+1x^7)y^4 + $$ $$(1+1x+\dots+1x^{15})y^5 + $$ $$\dots$$ Does anyone know of a way ...
3
votes
3answers
507 views

How to get closed form from generating function?

I have this generating function: $$\frac{1}{2}\, \left( {\frac {1}{\sqrt {1-4\,z}}}-1 \right) \left( \,{ \frac {1-\sqrt {1-4\,z}}{2z}}-1 \right)$$ and I know that $\frac {1}{\sqrt {1-4\,z}}$ is ...
3
votes
2answers
225 views

how to find generating function with nested sums

I'm trying to figure out the generating function for this power series.. I have a few ideas but can't get any result.. $$\sum_{n=2}^\infty \left(\sum_{k=1}^{n} ((n-k)(k-1)M_{k-1}) z^n\right) $$ ...
3
votes
7answers
324 views

how to find this generating function

this is the power series: $$\sum_{i=0}^\infty n(n-1)^2 (n-2) z^n.$$ how can I find a generating function from it? I could use the third derivative but the $n-1$ is squared so I don't know what to ...
0
votes
0answers
160 views

Where can I find more information on the Hadamard Product (of Generating Functions)?

I've been messing around with generating functions, power series, and related series, and I've come across a simple method of using two "roots of unity filters" to calculate the Hadamard product. A ...
1
vote
1answer
188 views

Formal Power Series

Say I differentiate this twice: $$\dfrac{1}{1+3x} = 1 - 3x + 9x^2 -\cdots+ (-3)^n x^n+\cdots $$ I got $$\dfrac{18}{(1+3x)^3} = 18 - 162x + \cdots + n\cdot(n-1)(-3)^nx^{n-2}+\cdots$$ If I wanted ...
3
votes
2answers
580 views

Turning a closed-form generating function back to ordinary power series

If I know the formal power series, I know how to find the closed form: $$\displaystyle F = \sum_{n=0}^{\infty} {X^n} = 1 + X^1 + X^2 + X^3 + ...$$ $$\displaystyle F \cdot X = X \cdot ...
8
votes
5answers
422 views

Formal power series - a question

I've been reading generationgfunctionology by Herbert S. Wilf (you can find a copy of the second edition on the author's page here). On page 33 he does something I find weird. He wants to shuffle the ...
34
votes
3answers
2k views

Factorial and exponential dual identities

There are two identities that have a seemingly dual correspondence: $$e^x = \sum_{n\ge0} {x^n\over n!}$$ and $$n! = \int_0^{\infty} {x^n\over e^x}\ dx.$$ Is there anything to this comparison? (I ...
0
votes
2answers
130 views

How to solve the following system?

I need to find the function c(k), knowing that $$\sum_{k=0}^{\infty} \frac{c(k)}{k!}=1$$ $$\sum_{k=0}^{\infty} \frac{c(2k)}{(2k)!}=0$$ $$\sum_{k=0}^{\infty} \frac{c(2k+1)}{(2k+1)!}=1$$ ...
2
votes
1answer
191 views

Product of bivariate generating functions

The product of two univariate generating functions is simply given by the Cauchy product. $$ A(x) = \sum_{n=0} a_n x^n $$ $$ B(x) = \sum_{n=0} b_n x^n $$ $$ A(x)B(x) = C(x) = \sum_{n=0} x^n c_n ...
6
votes
4answers
1k views

Formal power series coefficient multiplication

Given that I have two formal power series: $$ A(x) = \sum_{k \ge 0} a_k x^k $$ $$ B(x) = \sum_{k \ge 0} b_k x^k $$ The Cauchy Product gives a series $$ C(x) = \sum_{k \ge 0} c_k x^k $$ $$ c_k = ...