0
votes
1answer
33 views

Generating functions of form $\sum_{n=0}^\infty a_n x^{kn}$

Let's consider generating function $$F(x) = (1+x)^r = \sum_{n=0} \binom{r}{n} x^n$$ And another generating function $$G(x) = (1+x^2)^r = \sum_{n=0} \binom{r}{n}x^{2n}$$ Please note those 2 functions ...
1
vote
1answer
44 views

Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...
2
votes
2answers
90 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
0
votes
3answers
54 views

Finding the Coefficient of X^9 in (1+x^3+X^8)^10

This is solved by the following approach e1 takes values 0 3 8 e2 takes values 0 3 8 .. .. .. . and finally it is said that we get 9 when we take ai=3.And the answer become 10c3. Can someone ...
3
votes
1answer
186 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
0
votes
2answers
65 views

generating function and binomial distribution - counting

I am trying to understand generating function. I have the following problem: There are 50 students in the International Mathematical Olympiad (IMO) training programme. 6 of them are to be selected to ...
1
vote
1answer
50 views

Express number of ways integer can be written as coefficient in generating series

Question: "Express the number of ways that an integer $n$ can be written as a sum of a cube of an integer $s\ge-1$ plus the fourth power of an integer $t$ plus the square of an odd integer $r$ as a ...
8
votes
2answers
163 views

Ordinary generating function for $\binom{3n}{n}$

The ordinary generating function for the central binomial coefficients, that is, $$\displaystyle \sum_{n=0}^{\infty} \binom{2n}{n} x^{n} = \frac{1}{\sqrt{1-4x}}$$ follows from the generalized ...
7
votes
4answers
323 views

Find closed form solution using generation function for the binomial coefficients

I don't have any idea how to start this problem. Could you give a hint? Find closed form solution using generation function for the binomial coefficients: $$a_n:=\sum_{k=0}^{n}\binom{n}{k}^2(-1)^k$$ ...
1
vote
1answer
96 views

Combinatorics - Find the coefficient of $x^{12}$ in…

Would someone be able to help me figure out these two binomial coefficient problems using generating functions? Its a rough concept for me to understand, so a good explanation would be very much ...
1
vote
1answer
61 views

Change of variable in an infinite sum

I'm currently trying to understand a derivation from WolframMathWorlds. I got to step 6 where a change of variable happens. You can see the equation here. I understand everything except how they get ...
1
vote
3answers
195 views

Is there a closed form for the sum $\sum_{k=2}^N {N \choose k} \frac{k-1}{k}$?

I am interested in finding a closed form for the sum $\sum_{k=2}^N {N \choose k} \frac{k-1}{k}$. Does anyone know if there is some Binomial identity that might be helpful here? Thank you.
1
vote
2answers
394 views

Generating Functions in Discrete Mathematics in Computer Science

Hey Guys can anyone help me with the following question in Discrete Structures in Mathematics, relating generating functions Find a closed form for the generating function for the sequence $\{a_n\}$, ...
2
votes
2answers
75 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
3answers
147 views

Proving an Identity involving $4^N$ [duplicate]

I am trying to prove the following identity: $$\sum_{k=0}^N\left({2 \, N - 2 \, k \choose N - k}{2 \, k \choose k}\right)=4^N$$ I have tried writing $4^N=2^{2N}=(1+1)^{2N}=(1+1)^N(1+1)^N$, and ...
0
votes
2answers
269 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with ...
2
votes
2answers
68 views

Finding the coefficient in the closed form of the generating function

I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form \begin{eqnarray*} ...
4
votes
2answers
211 views

Is there a closed form expression for the first half of the Binomial series?

I'm looking for a closed form expression for the sum $P_n(x) =\sum_{0\leq k\leq n/2}\binom{n}{k}x^k$, where $n$ is a given positive integer and $k$ runs over nonnegative integers between $0$ and ...
4
votes
4answers
301 views

The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$

A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
1
vote
1answer
160 views

Binomial expansion with only odd coefficients?

In William Feller's 1st book p.272 It said the generating function $\Phi$ satisfies \begin{equation*} qs\Phi^2(s) - \Phi(s) + ps = 0 \end{equation*} so it has two roots. The first root is unbounded ...
1
vote
2answers
199 views

Generating function with binomial coefficients

I want to derive formula for generating function $$\sum_{n=0}^{+\infty}{m+n\choose m}z^n$$ because it is very often very useful for me. Unfortunately I'm stuck: $$ f(z)=\sum_{n\ge 0}{m+n\choose ...
7
votes
1answer
308 views

Combinatorial Interpretation of Fractional Binomial Coefficients

My question is a bit imprecise - but I hope you like it. I even strongly think it has a proper answer. The binomial coefficient $\binom{\frac{1}{2}}{n}$ is strongly related to Catalan numbers - the ...
3
votes
2answers
202 views

Calculating a binomial sum

I came across this excercise in an old exam (in discrete math), and I don't know how to approach it: $$\sum_{k=0}^{10}\left(\frac{1}{2}\right)^k\left(-1\right)^k\binom{10}{k}$$ I know the answer is ...
1
vote
1answer
97 views

Generating Functions and the Negative Binom

I'm reading from 3 different sets of notes on generating functions and having a little trouble integrating their approaches. First, I'm used to working with the following definitions: ...
5
votes
1answer
185 views

About one generating function

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
2
votes
1answer
83 views

Is there a simple expression for this generating function that is almost like the binomial formula?

This is a curiosity I when looking at the binomial theorem. Say you have an ordinary generating function $\displaystyle\sum_{n,m\geq 0}\binom{n}{m}x^ny^m$. This looks kind of like ...
1
vote
1answer
137 views

On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2

Let $g_n=$ number of 2-regular graphs on $n$ vertices Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2 By a computation with the exponential generating function I think that ...
2
votes
1answer
172 views

Evaluating an expression using snake oil and convolutions gives different answers

I have to evaluate this expression $\sum \limits_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{n-k}$ using snake oil and convolutions. The problem is that I got two different results, could you help me to ...
2
votes
1answer
209 views

Evaluating an expression using snake oil

I have to evaluate this expression: $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{-k}$, (In the original question we had $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{k}$) this is what I have done: ...
4
votes
1answer
189 views

Evaluating the sum $\sum\limits_k \ k\binom{n}{k}^2$ using generating functions

I have to evaluate this expression $\sum\limits_k \ k\binom{n}{k}^2$ using generating function. Could you help me please? Also with some hints.
5
votes
3answers
210 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
3
votes
1answer
255 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
6
votes
3answers
630 views

Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
6
votes
0answers
269 views

Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
1
vote
1answer
252 views

Two generating functions involving binomial coefficients

Are any of you familiar with the closed form solutions for $\sum_{k=0}^{n} k C(n,k) x^k$ and $\sum_{k=0}^{n} k^2 C(n,k) x^k$ where $0 < x < 1$? Thanks!
4
votes
3answers
1k views

Combination problem with constraints

You have four containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, say...70L, 45L, 33L and 11L levels respectively. What is the formula that ...
7
votes
2answers
709 views

Squared binomial coefficient

I've got the following finite sum: $s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}^2p^k$ (esp. if $p$ is a function of $n$, like $p=\frac1{n}$), which can be rewritten as ...
7
votes
2answers
299 views

A binomial coefficient identity?

Suppose $p$, $k$ and $s$ are integers with $s,k \le p$. Consider the following polynomial in $x$ and $y$, $$ \sum_{\ell=0}^k \binom{s}{\ell} \binom{p-s}{k-\ell} x^\ell y^{p-\ell}$$ Does this ...
12
votes
6answers
798 views

Proving a binomial sum identity

Mathematica tells me that $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$ Although I have not been able to come up with a proof. Proofs, hints, or references are all ...