Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [generating-functions]

Generating functions are formed by making a series $\sum_{n\geq 0} a_n x^n$ out of a sequence $a_n$. They are used to count objects in enumerative combinatorics.

A generating function is a formal power series of the form \begin{equation*} f(x)=\sum^{\infty}_{n=0}a_nx^n \end{equation*} whose coefficients contain information about $a_n$, the sequence of numbers. For instance, suppose that the sequence is the Fibonacci sequence $0,1,1,2,3,5,8,\ldots$ Then$$f(x)=x+x^2+2x^3+3x^4+5x^5+\cdots,$$$$xf(x)=x^2+x^3+2x^4+3x^5+\cdots,$$and$$x^2f(x)=x^3+x^4+2x^5+\cdots.$$Then, it follows from the definition of the Fibonacci sequence that$$(1-x-x^2)f(x)=x$$This fact can be used to prove properties of the sequence, such as that its $n^\text{th}$ term is$$F_n = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt5},$$where $\varphi$ is the golden ratio.

4469 questions
2
votes
3 answers

Solve $a_n=2 a_{n-1} - a_{n-2} + 2^n$ using generating function

I'm preparing to an exam and trying to solve $a_n=2 a_{n-1} - a_{n-2} + 2^n$, where $a_0=0$ and $a_1=1$. This is my approach: Let $A(z)=\sum_{n \geq 0} a_{n+2} z^{n+2}$, then: $$\sum a_{n+2} z^{n+2} = 2 \sum a_{n+1} z^{n+2} - \sum a_n z^{n+2} +…
dash
  • 293
2
votes
2 answers

Question about generating functions

I have question about generating functions. I need to make this equation: $(\frac{1}{1+x})^n\centerdot(1+x)^{2n} = (1+x)^n$ in this form: $\sum\limits_{i=0}^{k}(-1)^iD(?,?)\binom{?}{?} = \binom{n}{k}$ How can I do this? Thanks in advance
EMDB1
  • 477
  • 2
  • 8
2
votes
1 answer

Wilf's Generatingfunctionology first example

in this book (https://www.math.upenn.edu/~wilf/DownldGF.html) I think I get the first example until the point: $$\frac{G(x)} x = 2G(x) + \frac 1 {1-x}$$ How is this equal to $$G(x) = \frac x {(1-x)(1-2x)} \text{ ?}$$ $$G(x) = \frac x {(1 - x)^2}$$…
bencemeszaros
  • 183
2
votes
3 answers

Generating Functions with composition

For a nonnegative integer $n$, a composition of $n$ means a partition in which the order of the parts matters. Consider the generating function $$C(x) = \sum_{n=0}^{\infty} c_nx^n,$$ where $c_n$ is the number of distinct compositions of $n$ (note…
user228320
  • 629
  • 5
  • 13
2
votes
0 answers

generating function question, method?

Write a closed formula for the generating function of the sequence $a_n=(2n+3)(-1)^n$ So first I try $A(z)=\sum_{z=0}^\infty (2n+3)(-1)^nz^n$ $=\sum_{n=0}^\infty [2(n+1)+1](-1)^nz^n$ $=2\sum_{n=0}^\infty (n+1)(-1)^nz^n + \sum_{n=0}^\infty…
user247641
  • 21
2
votes
0 answers

binomial expansion of $(1+x)^n \left(\dfrac{1}{x} -1\right)^m$

Let $n$ and $m$ be positive integers with $n \gt m$. Can you show that the constant term of $${(1+x)^n}\left(\frac{1}{x} - 1\right)^m$$ is not equal to zero?
hkju
  • 1,031
2
votes
0 answers

Generating function of a_n * b_n

I've been searching for the answer yet no luck. Please let me know if this is a duplicate. Let $A(x) = \sum a_n x^n$, $B(x) = \sum b_n x^n$, $C(x) = \sum a_n b_n x^n$. I am looking for the closed form of $C(x)$ in terms of $A(x)$ and $B(x)$. Thanks…
foobar
  • 91
2
votes
2 answers

Is generating function having use in recurence relations containing division in subscripts?

It's well known that generating functions are great to solve recurence relations in form $$a_n = A*a_{n-1} + B*a_{n-2} + \dots$$ But i was wondering what happens if recurence relation contains division in subscripts? It is: $$a_n = A*a_{\lfloor…
Krzysztof Lewko
  • 2,312
2
votes
1 answer

Generating function for sequence $a_n = \lceil \sqrt{n} \rceil $

In one of books for discrete mathematics i came across sum to calculate $$\sum_{k=0}^n \lceil \sqrt{n} \rceil$$ which was fairly easy, but this sum intrigued me what is generating function for $$\sum_{n=0}^\infty \lceil \sqrt{n} \rceil x^n $$ so…
Krzysztof Lewko
  • 2,312
2
votes
1 answer

Find the coefficient on x^10 in the following generating function

$\ {(1 − x^{14})\over (1 − x)}$ My thought was: $\ (1-x^{14})\over (1-x)$ $\ = (1 - x^{14}) ∑ x^n$ $\ = ∑ [x^n - x^{n+14}]$ But I'm not sure if I'm on the right path?
lily
  • 21
2
votes
1 answer

Generating Function for Integer Compositions

The Full Question (a) What is the generating function for the number of integer compositions with $2$ parts? (b) What is the generating function for the number of integer compositions with $3$ parts? (c) What is the generating function for the…
Dunka
  • 2,787
  • 12
  • 41
  • 69
2
votes
1 answer

The Finishing Step to Showing that $1/(1-4x)^{1/2}$ generates the sequence $\binom{2r}{r}$

The Full Question: Show that $(1-4x)^{-\frac{1}{2}}$ generates the sequence $\binom{2n}{n}$, $n\in \mathbb N$ My Research How to show that $1 \over \sqrt{1 - 4x} $ generate $\sum_{n=0}^\infty \binom{2n}{n}x^n $ Show $\sum\limits_{n=0}^{\infty}{2n…
Dunka
  • 2,787
  • 12
  • 41
  • 69
2
votes
1 answer

Find the first coefficients of the inverse series of $x+x^2\sqrt{1+x}$

This is exercise 2c from chapter 2 of Wilf's generatingfunctionology. The problem is to find the inverse series $g(x)$ of the series of $f(x)=x+x^2\sqrt{1+x}$ (i.e. $f(g(x))=g(f(x))=x$). I get nowhere with the solution he gives in the back of the…
Jack
  • 41
2
votes
1 answer

Determine generating function for given sequence.

Let $A(x) $ be generating function for sequence $a_n$ and let $s_n = \sum^{n}_{i=0} a_i $. Determine function generating sequence $a_n$ I am asking for an advice. The generating function makes me some problem. Thanks in advance.
user180834
  • 1,453
2
votes
3 answers

Prove, that generating function for $0,0,0,0,0,0,0,3,1,3,1,...$ is $\frac{x^7}{1-x} + \frac{2x^7}{1-x^2}$

Prove, that generating function for $0,0,0,0,0,0,0,3,1,3,1,...$ is $$\frac{x^7}{1-x} + \frac{2x^7}{1-x^2}$$ I have a really problem with understanding generating function, so I don't show my attempt so I am asking for advice. Thanks in advance.
user180834
  • 1,453
1 2 3
…
21 22