1
vote
1answer
44 views

Rational Series VS Algebraic Series

I am reading a paper on combinatorics. It mentions some generating functions are rational series and others are algebraic series. I do not understand the difference, can someone help? EDIT $1$: The ...
12
votes
1answer
243 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
5
votes
2answers
73 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 + ...
0
votes
3answers
55 views

How do I simplify the formal power series $1+2x^2F(x)^2$?

I have this formal power series $$F(x)=1+2x^2F(x)^2$$ that I want to put into non-recursive form. I can expand, $$1+2x^2F(x)^2=1+2x^2(1+2x^2F(x)^2)^2= 1+2x^2+8x^4F(x)^2+8x^6F(x)^6$$ and I could ...
0
votes
1answer
59 views

Convergence of formal power series substitution

Prove that the substitution of formal power series $F(G(x))=\sum_{k\geq0}f_k \frac{G(x)^k}{n!}$ converges for every $F$ if and only if $G(0)=0$
3
votes
2answers
355 views

Formal power series, the Chain Rule and the Product Rule.

Definitons Let $$\mathbb{C}[[x]] := \left\{ \sum_{n\geq 0} a_n x^n : a_n \in \mathbb{C} \right\}$$ be the set of formal power series of $x$. Exercise i) If $F_1(x)$ and $F_2(x)$ are power series ...
2
votes
1answer
183 views

The Lagrange inversion formula (the proof from Wikipedia)

English Wikipedia gives a very short proof of the Lagrange Inversion Theorem, using the formal residue. However, I don't understand the second equality, $$k \, \mathrm{Res} (g^n \, X^{-k-1}) = k \, ...
1
vote
2answers
46 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} ...
1
vote
1answer
71 views

Coefficient power series problem #49

What is the coefficient of $x^n$ in the power series form of $(1-2x)^{1/3}$? This problem is taken from bona chapter 4, third edition.
0
votes
1answer
56 views

Coefficients in a pair of formal power series

Let's suppose I have formal power series $\sum_{k=1}^{\infty} (-1)^{k+1}a_k \sum_{j=0}^k (-1)^j\binom{k}{j} X^j=\sum_{n=0}^{\infty}C_n X^n$. I would like a clean way to write the formal sum ...
0
votes
0answers
52 views

Proof of the power of this series?

Suppose: $$x = 1 + v + (1+ a + b) v^2/ 2! + (1+2a+b)(1+a+2b)v^3/3! + (1+3a + b)(1+2a +2b)(1+a+3b) v^4 /4! + \ldots$$ Prove that: $$x^n = 1 + nv + n(n+ a + b) v^2/ 2! + n(n+2a+b)(n+a+2b)v^3/3! + ...
5
votes
2answers
190 views

Interval of convergence of $\sum\limits_{n\geq0} \binom{2n}{n} x^n$

We consider the power series $\displaystyle{\sum_{n\geq0} {2n \choose n} x^n}$. By Ratio Test, the radius of convergence is easily shown to be $R=\frac{1}{4}$. For $x=\frac{1}{4}$, Stirling ...
3
votes
2answers
110 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 ...
1
vote
1answer
57 views

Writing a sum as a fraction

Express $$\sum^{20}_{i=2}f(x)^i$$where $$f(x)=\sum_{i\geq 1}2^{i-1}x^{3i}$$ as a fraction of polynomials $p(x)/q(x)$ and simplify as much as possible. Hmm. How to do it? Wolfram is really stupid on ...
2
votes
4answers
104 views

How to use “results from partial fractions”?

Let ${a_n}$ be a sequence whose corresponding power series $A(x)=\sum_{i\geq 0}a_ix^i$ satisfies $$A(x)=\frac{6-x+5x^2}{1-3x^2-2x^3}$$ The denominator can be factored into $(1-2x)(1+x)^2$. Using ...
1
vote
2answers
102 views

Using mathematical induction to prove an identity related to combinatorics

Using Mathematical induction on $k$, prove that for any integer $k\geq 1$, $$(1-x)^{-k}=\sum_{n\geq 0}\binom{n+k-1}{k-1}x^n$$ How should I proceed? The tutorial teacher attempted this question and ...
2
votes
1answer
89 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 ...
1
vote
4answers
163 views

Proving an identity using formal power series

4. (a) Prove that $\dfrac{1-x^2}{1+x^3}=\dfrac{1}{1+\frac{x^2}{1-x}}$. (b) By expanding each side of the identity in (a) as a power series, and considering the coefficient of $x^N$, prove ...
-1
votes
1answer
65 views

Express the following power series as a raional function

Consider the following power series: $f(x) = \sum\limits_{i>=1} 2^{i-1}x^{3i}$ = $\ x^3 + 2x^6 + 4x^9 + ...$ $g(x) = \sum\limits_{i=2}^{20} f(x)^{i}$ Express both f(x) and g(x) as rational ...
0
votes
1answer
550 views

Calculating a coefficient for a formal power series

My textbook has a whole bunch of exercises on finding some coefficient inside a formal power series. Unfortunately, there aren't any examples on how to do so, especially since many of the series ...
1
vote
1answer
65 views

Power series of $f(x)=\sqrt{\frac{1+x}{1-x}}$

How do I find the power series form of $\,f(x)\,$: $$\displaystyle f(x)=\sqrt{\frac{1+x}{1-x}}$$ I tried to multiply the fraction by $\,\dfrac{1+x}{1+x}\,$ but it didn't help...
5
votes
3answers
348 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
3answers
196 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 \, \, ?$$
4
votes
1answer
101 views

A numeral system built around Dirichlet series, by analogy of how positional numeral systems are built around power series?

For any natural number and chosen base p, the number admits a unique expression of the form $a_np^n + ... + a_2p^2 + a_1p^1 + a_0$, where $a_k < p$ for all k. This property is effectively what ...
1
vote
3answers
72 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 ...
4
votes
2answers
223 views

Finding a closed form expression for this sum [duplicate]

For non-negative $n$, find $$ \sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}. $$ I can't figure this out. Any ideas?
2
votes
1answer
106 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 ...
2
votes
2answers
140 views

Evaluating $\sum_{i=0}^n(-1)^{n-i}{n \choose i}f(i)$

From Enumerative Combinatorics by Stanley: Evaluate $$\sum_{i=0}^n(-1)^{n-i}{n \choose i}f(i)$$ where $$\sum_{n\ge 0}\frac{f(n)x^{n}}{(n)!}=\exp\bigg(x+\frac{x^2}{2}\bigg)$$ I tried splitting ...
4
votes
0answers
128 views

Function composition and Bell polynomials

Suppose that we have the Taylor expansions : $$f(x)=\sum_{n=1}^{\infty}\frac{a_{n}}{n!}x^{n}$$ $$g(x)=\sum_{n=1}^{\infty}\frac{b_{n}}{n!}x^{n}$$ Then we have the standard result : ...
2
votes
1answer
146 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
285 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 ...
3
votes
1answer
119 views

Formal exponential of multivariate power series

I was wondering about this. Consider a formal power series $$\sum_{n=1}^{\infty} a_n x^n$$. We can find its formal exponential, given by $$\exp\left(\sum_{n=1}^{\infty} a_n x^n\right) = ...
1
vote
1answer
238 views

Exponential of formal power series and Bell polynomials

Wikipedia gives here the following formula for the exponential of a formal power series: $\exp \Big[\ \sum_{n=1}^\infty \frac{a_n}{n!} x^n\ \Big] = \sum_{n=0}^\infty \frac{B_n(a_1,\dots,a_n)}{n!} ...
3
votes
1answer
294 views

A sum involving permutation

Does there exist a nice closed form formula for the sum $$\sum_{k=0}^m P(m,k)x^k$$ where $P(m,k)=C(m,k)*k!$, $C(m,k)$ being the "m choose k" number. Formula given by Maple 11 is complicated. I ...
3
votes
3answers
198 views

Recurrence relations problem (1st order, linear, constant coeff, inhomogeneous)

okay im supposed to find a recurrence relation for $$ a_{n+1}= b \cdot a_n + c \cdot n \ \ \ \ \ \ \ \ \ \ \ \ \mathbf{(1)} $$ where $b$ and $c$ are constants. the method we learned in class was ...
15
votes
2answers
948 views

any pattern here ? (revised 2)

for any positive number $k$, I have a $(k+1)*(k+1)$ matrix. I wonder if these matrices follow any "obvious" pattern. My goal is to guess the elements for matrix with $k=5$ and above (most probably in ...