Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

2
votes
1answer
54 views

When does $(x+y)^n+(x-y)^n\leq(2x)^n$ hold?

With $n\in\mathbb{N}$, what is the relation between $(x+y)^n+(x-y)^n\leq(2x)^n$ and the values of $x$ and $y$? Or mathematically: $(x+y)^n+(x-y)^n\leq(2x)^n\iff$ the values of $x$ and $y$ are such ...
2
votes
0answers
41 views

How to prove: $pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$

For any two distinct primes $p, q$ there is a unique integer $k$ such that: $$pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$$ Where $k$ is the smallest integer greater than $p$ that is relatively ...
0
votes
1answer
62 views

Is this possible or hopeless to try to prove?

If I have $x_1, ..., x_k=o(n)$ and $j=O(1)$. Is it possible to prove something like: $$\sum_{i=1}^k {n \choose j} \left(\frac{x_i}{n}\right)^j \left(1-\frac{x_i}{n}\right)^{k-j} \sim {n \choose j} ...
0
votes
0answers
22 views

Bounding a specific function of binomial coefficients

While trying to directly prove the existence of expander graphs (e.g. http://www.cs.toronto.edu/~avner/teaching/S6-2414/TUT2.pdf), one uses the following inequality: $$\sum_{s=1}^{n/2} ...
3
votes
1answer
50 views

Derivative of Binomial Coefficient wrt k

I've got $\binom{2N}{N-x}$ and I'd like to take the derivative with respect to x. I know that I can take the derivative of $\binom{n}{k}$ w.r.t. n using logarithmic differentiation, but that's not ...
3
votes
3answers
57 views

Sum of products of binomial coefficients

In a proof I've come across the following identity: $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$ I see that it's right, when plugging in numbers, but I don't see the ...
3
votes
2answers
234 views

How find this sum closed form?

Have this sum have close form $$f(n)=\sum_{k=0}^{n-1}\left(\left(\sum_{i=0}^{k}(-1)^i\binom{n}{i}\right)\cdot\left(‌​\sum_{j=k+1}^{n}(-1)^j\binom{n}{j}\right)\right)$$ Maybe this sum can use ...
4
votes
3answers
178 views

Closed form of a sum of binomial coefficients?

I have the following function: $T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same ...
4
votes
2answers
115 views

How prove this sum $\sum_{k=0}^{n-1}a_{k}b_{k}=\frac{n}{2}\binom{2n}{n}$

QUestion: show that $$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\cdots+\binom{n}{n}\right)=\dfrac{n}{2}\binom{2n}{n}$$ My idea: let ...
1
vote
0answers
23 views

How to get a nice approximation of $f(N,s)=\sum_{k=0}^{N}{N \choose k}{k \choose s-k+N}$ when $N>>1$ and $|s|<<N$?

I need to approximate the above sum in order to calculate $\mathbb{E}(s^2)$, which is the expectation value determined by the probability density function $f$ and the position $s$. Any idea?
0
votes
1answer
30 views

For each integer $s$, how many N-tuples with possible elements $\{0, 1, -1\}$ satisfy the condition that the sum of its elements is $s$?

So, we can find the answer using the generating function: $$f(x)=(1+x+x^{-1})^N=x^{-N}\sum_{k=0}^{N}\sum_{m=0}^{k}{N \choose k}{k \choose m}x^kx^m$$ and the number of N-tuples for each integer $s$ is ...
4
votes
4answers
74 views

Conjecture for product of binomial coefficient

Is it true that for any $n, k\in\mathbb N$ $$\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad?$$ I tested it for some small $k$ and $n$, but I don't know how to prove that it is true ...
0
votes
3answers
108 views

Given the sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for it?

Given a sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for this sequence? Is there any optimised approach? My approach: the given series is equal to summation of $\binom{n}{k}$ ...
0
votes
0answers
62 views

Generalized Leibniz Rule

Leibniz Rule states that, $$(f\cdot g)^{(m)}(x)=\sum_{k=0}^m \binom{m}{k} f^{(m-k)}(x)g^{(k)}(x).$$ Writing this with differentiation denoted by $D$, we might say $$D^m (fg) = \sum_{k=0}^m ...
6
votes
4answers
220 views

Truncated alternating binomial sum

It is easily checked that $ \sum_{i = 0}^n (-1)^i \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the truncated sum $\sum_{i=0}^{D} ...
0
votes
2answers
66 views

A summation with binomial coefficients

Evaluate There seemed to be some problem with stackexchange's math rendering but Ian corrected whatever error was there in the expression.Thanks $$5050 \frac {\left( \sum _{r=0}^{100} \frac ...
1
vote
1answer
34 views

How to find the limit superior of the nth root of the generalized binomial coefficient?

My book says that $$ \varlimsup_{n \to \infty} \sqrt[n]{\left|{\binom{\alpha}{n}} \right|} = 1 $$ where $\alpha \in \mathbb{R} \setminus \mathbb{N} \cup \{ 0 \} $ and $n \in \mathbb{N}$. Where ...
1
vote
1answer
71 views

Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ...
1
vote
4answers
127 views

The probability that after repeated random drawing from an urn, all balls left in the urn will be red

Problem An urn contains $p$ red and $q$ green balls. Balls are drawn one by one till balls left in the urn are all red. Prove that the probability of this event is $\dfrac {p}{p+q}$. Please note that ...
2
votes
1answer
81 views

A double sum with combinatorial factors

Let $n$, $p$ and $j$ be integers. As a byproduct of some other calculations I have discovered the following identity: \begin{equation} \sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} ...
0
votes
0answers
48 views

$\sum$ of binomial coefficients inequality

Let $m,n$ be positive integers with $m>n$. When is it true that $$m\cdot 5^{m-1}\cdot 3+\binom{m}{3}\cdot 5^{m-3}\cdot 3^3\cdot 2+\cdots +\binom{m}{2k+1}\cdot m^{m-2k-1}\cdot 3^{2k+1}\cdot ...
2
votes
0answers
27 views

Proving an inequality having binomial coefficients

Suppose that $0 \leq b \leq b+x < a$. How could I prove the inequality \begin{equation} \left(\frac{a-b-x}{a-x}\right)^x \leq \cfrac{\binom{a-x}{b}}{\binom{a}{b}} \leq \left(\frac{a-b}{a}\right)^x ...
3
votes
1answer
39 views

How to simplify a sum with binomial coefficients multiplied by $k^3/2^k$?

The sum is $$\sum_{k=5}^{\infty}\binom{k-1}{k-5}\frac{k^3}{2^{k}} $$ The first thing I thought of was the binomial coefficient. So I re-indexed it ...
0
votes
0answers
25 views

Lower bound for a relative of the central binomial coeff

The central binomial coefficients $\binom{2m}{m}$ have g.f. $\frac{1}{\sqrt{1-4z}}$ and lower bound $\frac{4^m}{\sqrt{4m}} \le \binom{2m}{m}$. I'm interested in a related integer series $$T(2m, m) = ...
1
vote
3answers
94 views

Simplifying $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}$

In trying to simplify my answer to a problem posted recently, I am trying to show that $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}=8\binom{24}{4}$. I know that ...
2
votes
1answer
58 views

Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$ \sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i} $$ The number ...
1
vote
0answers
67 views

A sum with binomial coefficients in the numerator and denominator.

I am struggling with a combinatorial sum as apart of a long statistical-mechanics derivation. I would appreciate any help. I seek the result of the following summation, for integer $\ell,n$, and ...
1
vote
2answers
46 views

Upper bound on $ \binom{a}{m+1}\sum ^m_{j=0} \binom{a-m-1}{j}/\binom{b}{j+m+1}$

Given $a,b,m$ such that $0<2m<a<b$. I would like to find out upper bound of $$S = \binom{a}{m+1}\sum ^m_{j=0} \frac{\binom{a-m-1}{j}}{\binom{b}{j+m+1}}$$ Anyone can help me please? Thank you ...
0
votes
1answer
29 views

Probability $\sum_{j=n+1}^{2n+1} {M \choose m+1}{M-m-1 \choose j-m-1}/{N \choose j} $

I have a prob. problem: A school has $N$ students in which $M$ students are leader (of each class in school), and $N>M$. There are $2n+1$ balls in the black box including $n+1$ blue balls and $n$ ...
4
votes
2answers
97 views

Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
1
vote
1answer
59 views

An upper bound and simplification for expression

I would like to find the upper bound (or simplification) of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}{n+1\choose j}{n \choose i}/{2n+1 \choose j+i}$$ where ...
1
vote
2answers
173 views

How find this sum $\sum_{i=0}^{2n}\binom{2n}{2i}\binom{2i}{i}y^{2i}$

Find the sum close form $$f(x)=\sum_{i=0}^{2n}\dfrac{\binom{2n}{2i}\binom{2i}{i}x^{2i}}{2^{2i}}$$ if we let $$\dfrac{x}{2}=y$$ then $$f(y)=\sum_{i=0}^{2n}\binom{2n}{2i}\binom{2i}{i}y^{2i}$$ ...
0
votes
2answers
64 views

Simplify the expression of binom

Any one knows how to simplify this expression or finding upper bound of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}$$ where $0<a<1$ is constant. Thanks a lot.
1
vote
1answer
32 views

Upper bound of $\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}$

I would like to find max (or sup.) of the sum: $$S=\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}.$$ I found $S\le \frac{1}{\sqrt{\pi n}}.2(n+1).4^n$ but It seems it's ...
5
votes
3answers
631 views

Why does this infinite series equal one?

Why does $$\sum_{k=1}^\infty \binom{2k}{k} \frac{1}{4^k(k+1)}=1$$ Is there an intuitive method by which to derive this equality?
1
vote
1answer
42 views

Is there a set of 69 length-6-sets out of 46 numbers [1..46] so that those length-6-sets “cover” all possible 1035 length-2-sets of 46 numbers?

1.) For this question, we have 46 numbers (balls, cards, whatever): {1,2,3,4 .... 45,46} ======================= 2.) Each length-6-set of 46 numbers ( e.g. {1,2,3,4,5,6} or {1,13,16,17,32,46 } ...
0
votes
2answers
19 views

Finding a particular term of a binomial expansion

How do I find the term involving $x^{10}$ in the expansion of: $$ (3+2x^2)^7 $$ I know from the binomial theorem that: $$ u_{n+1} = {^nC_r a^{n-r}x^r} $$ and that $n=7, a=3, x=2x^2, r=10$ in this ...
5
votes
3answers
95 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
3
votes
1answer
59 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
4
votes
2answers
62 views

Binomial dependent on a Poisson

I have been working on a problem with a binomial rv dependent on a poisson rv and have worked through to this point: $P(X=x) = \sum_{n=x}^{\infty} \dfrac{n!}{x!(n-x)!} p^x(1−p)^{n−x} ...
3
votes
1answer
74 views

Upper bound of $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
7
votes
6answers
241 views

Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$ I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a ...
3
votes
1answer
53 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
3
votes
2answers
91 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
2
votes
0answers
53 views

Sum and binomials

I have this sum ...
6
votes
2answers
189 views

Prove $(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j} $

I stumbled upon the identity $$(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j}. $$ The right-hand side is a polynomial. ...
1
vote
2answers
83 views

Partial sum of binomial

I 'm trying to figure out a closed form solution for the following summation: $\sum_{j=0}^{\omega} j{n \choose j}p^{j}(1-p)^{n-j}$ where $\omega < n$ Is there any closed form solution?
4
votes
2answers
121 views

Binomial expansion inequality

In a paper I am reading, there is a step that seems to come from the following inequality: $$(1+x)^\alpha \le 1+2^\alpha x,$$ where $0<x<1$. (Also, $3\le \alpha \le 9/2$ in the context of the ...
5
votes
1answer
123 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
1
vote
0answers
41 views

A Vandermonde like identity for binomial coefficients

The Vandermonde identity is given by $ \left(\begin{matrix} m + n \\ j \end{matrix}\right) = \displaystyle\sum_{j=0}^k \left(\begin{matrix} m \\ j \end{matrix}\right)\left(\begin{matrix} n \\ k-j ...