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
100 views

What is the coefficient of $z^k$ in ${z+n-1 \choose n}$ for $1 \leq k \leq n$?

What is the coefficient of $z^k$ in ${z+n-1 \choose n}$ for $1 \leq k \leq n$? Thanks. I'm currently looking into Stirling numbers of the first kind, as it seems there is a connection.
2
votes
1answer
85 views

Wellner Inequality

Working on an exercise from Shorack's Probability for Statisticians, Ex 4.6 (Wellner): Suppose $T \simeq$ Binomial$(n,p)$. Then use the inequality $$\mu(|X| \ge \lambda) \le ...
4
votes
2answers
847 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
5
votes
0answers
136 views

Some rare binomial identities

Long ago , I once saw a nontrivial appealing binomial type of identity that I never saw again. It was something along the line of $\Sigma$$\binom{a(x)}{b(y)}$= where $a$ and $b$ where polynomials not ...
2
votes
2answers
186 views

Simplify $\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$

I am trying to simplify an expression involving summation as follows: $$\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$$ where $n$ is an integer, and $x$ is a positive real number. At a first ...
5
votes
7answers
4k views

How do I compute binomial coefficients efficiently?

I'm trying to reproduce [Excel's COMBIN function][1] in C#. The number of combinations is as follows, where number = n and number_chosen = k: $${n \choose k} = \frac{n!}{k! (n-k)!}.$$ I can't use ...
6
votes
0answers
156 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
16
votes
4answers
418 views

Prove that $n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $

Basically I had some fun doing this: 0 1 1 6 7 6 8 12 19 6 27 18 37 6 64 24 61 125 etc. starting with ...
3
votes
2answers
4k views

Find the coefficient of $x^3y^2z^3$ in the expansion $(2x+3y-4z+w)^9$

The exercise says: In the expansion $(2x+3y-4z+w)^9$, find the coefficient of $x^3y^2z^3$. The formula to find the coefficient of $x_1^{r_1}x_2^{r^2}\dots x_k^{r_k}$ in $(x_1+x_2+\dots+x_k)^n$ ...
1
vote
2answers
2k views

Combinatorial proof of an identity [duplicate]

Possible Duplicate: Combinatorially prove something I have to give a combinatorial proof of the identity: $$\sum_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$$ I can use prove it using the binomial ...
6
votes
7answers
382 views

Find the coefficient of $\sqrt{3}$ in $(1+\sqrt{3})^7$?

I just want to ask you if my solution is correct. Here's the problem, Using the Binomial Theorem, find the coefficient of $\sqrt{3}$ in $(1+\sqrt{3})^7$. Solution: The binomial theorem is, ...
6
votes
3answers
178 views

What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$?

What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$ in terms of $d$? Does the limit exist? Is there a simple upper bound interms of $d$?
4
votes
1answer
497 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
1
vote
2answers
83 views

binomial theorem: find coef. xy

Given: $$ \left(x-\dfrac{1}{2y}\right)^8\left(x+\dfrac{1}{2y}\right)^4 $$ Using binomial theorem, what is the coefficient of xy in the expansion? I've tried to do it but I couldn't. Could you ...
4
votes
3answers
2k views

Using Binomial Theorem to prove identity

I need to prove the following using the binomial theorem $${n \choose k} = {n-2 \choose k} + 2{n-2 \choose k-1} + {n-2 \choose k-2}$$ The binomial theorem states $$(1+x)^n = \sum_{k=0}^n {n \choose ...
1
vote
0answers
110 views

Binomial coefficient intervals (inequality)

For given $N$, $x$ and $k$ such that $0\leq x<N$ and $2\leq k\leq \left\lfloor \frac{N+1-2x}{2}\right\rfloor $, does it exist $p,$ $2\leq p\leq \left\lfloor \frac{N+1}{2}\right\rfloor $ such that ...
6
votes
4answers
189 views

Help evaluating a limit

I have the following limit: $$\lim_{n\rightarrow\infty}e^{-\alpha\sqrt{n}}\sum_{k=0}^{n-1}2^{-n-k} {{n-1+k}\choose k}\sum_{m=0}^{n-1-k}\frac{(\alpha\sqrt{n})^m}{m!}$$ where $\alpha>0$. ...
2
votes
3answers
692 views

Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$. ...
3
votes
2answers
1k views

Number of triangles inside given n-gon?

How many triangles can be drawn all of whose vertices are vertices of a given n-gon and all of whose sides are diagonals ( not sides ) of the n-gon ? How many k-gons can be drawn in such a way ?
2
votes
1answer
195 views

Given $y$ and $x \choose y$, how to find $x$? [duplicate]

Possible Duplicate: How to reverse the $n$ choose $k$ formula? Given integers $y\geq 0$ and $z>0$, is there a good way to find an integer $x\geq y$ such that $z=\binom x y$? I could ...
9
votes
2answers
421 views

Techniques for summing ratio of binomial coefficients

There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. ...
3
votes
2answers
101 views

What is the exponent of the last term of $(2x^2+3y^3)^{10}$?

What is the exponent of the last term of: $$(2x^2+3y^3)^{10}$$ Hi! I'm sorry if this question seems a bit amateurish. I'm quite confused with this question that was asked in a quiz about binomial ...
4
votes
5answers
496 views

Spivak's Calculus - Exercise 4.a of 2nd chapter

4 . (a) Prove that $$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$ Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$. I'm having a hard time trying to solve the problem ...
0
votes
2answers
225 views

generating function of multinomial coefficient

How to express this series in closed form? $$\sum_{i=1}^{\infty}\frac{(3i)!}{(i!)^3}x^{i}$$ Motive of the generating function is to evaluate the number of the paths from the $(0,0,0)$ to $(n,n,n)$ ...
4
votes
1answer
256 views

Inequality involving sums of fractions of products of binomial coefficients

Let $n\in\mathbb{N}$. For $0\le l\le n$ consider \begin{equation} b_l:=4^{-l} \sum_{j=0}^l \frac{\binom{2 l}{2 j} \binom{n}{j}^2}{\binom{2 n}{2 j}}\text{.} \end{equation} Do you know a technique how ...
3
votes
0answers
100 views

Simplifying the sum with binomial coefficients [duplicate]

Possible Duplicate: Identity involving binomial coefficients Simplify the sum: $$\sum_{k=0}^n {2k\choose k}{2n-2k\choose n-k}$$ So we can denote $a_n=\sum_{k=0}^n {2k\choose ...
2
votes
1answer
87 views

Criterion for Wolstenholme Primes

Wolstenholme Theorem is a nice theorem that states that every prime $p >3$ satisfies: $$\binom{2p}{p} \equiv 2 \pmod {p^3}$$ A Wolstenholme prime is a prime $p$ such that $\binom{2p}{p} \equiv 2 ...
4
votes
1answer
196 views

Primes Not Dividing $\binom{2n}{n}$

Let $n \geq 3$, show ${2n \choose n}$ is not divisible by $p$ for all primes $\frac{2n}{3} <p\leq n$ Note: This fact along with other facts about ${2n \choose n}$ are used in a proof of Bertrand's ...
2
votes
1answer
376 views

No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the ...
3
votes
2answers
199 views

what is the easiest way to represent $ \sqrt{1 + x} $ in series

How to expand $ \sqrt{1 + x}$. $$ \sum_{n = 0}^\infty {{\left ( 1 \over 2\right )!}x^n \over n! \left({1 \over 2 }- n\right )!} = 1 + \sum_{n = 1}^\infty {{\left ( 1 \over 2\right )!}x^n \over n! ...
16
votes
3answers
1k views

Alternating sum of squares of binomial coefficients

I know that the sum of squares of binomial coefficients is just ${2n}\choose{n}$ but what is the closed expression for the sum ${n}\choose{0}$$^2$ - ${n}\choose{1}$$^2$ + ${n}\choose{2}$$^2$ + ... + ...
1
vote
0answers
289 views

The Lucas Theorem and facts

I have studied the Lucas theorem and I encountered the following facts. How to deduce the following facts from The Lucas theorem? (1) If d, q > 1 are integers such that , $$\binom{nd}{md}$$ ...
2
votes
1answer
324 views

proof of a finite sum involving a binomial coefficient and a variable.

I found that the following equation holds for integers $l$, $k$, and any $x \neq 0,1$, $$\tag{1} \sum\limits_{l = 0}^k {\left( { - 1} \right)^l } \left( {\begin{array}{*{20}c} k \\ l \\ ...
2
votes
3answers
546 views

Two inequalities with binomial coefficients

I have two inequalities that I can't prove: $\displaystyle{n\choose i+k}\le {n\choose i}{n-i\choose k}$ $\displaystyle{n\choose k} \le \frac{n^n}{k^k(n-k)^{n-k}}$ What is the best way to prove ...
1
vote
0answers
192 views

Lucas' theorem Consequence

Lucas' theorem consequence $$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$ $$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$ $$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$ ...
0
votes
2answers
651 views

Prove $\sum_{k=0}^{n}\binom{n}{k} = 2^{n}$ combinatorially [duplicate]

Possible Duplicate: Proving a special case of the binomial theorem Prove the identity using a combinatorial argument: $$\sum_{k=0}^{n}\binom{n}{k} = 2^{n}$$ I'm not sure how to do a ...
0
votes
5answers
182 views

Prove by induction: $2^n = C(n,0) + C(n,1) + \cdots + C(n,n)$ [duplicate]

This is a question I came across in an old midterm and I'm not sure how to do it. Any help is appreciated. $$2^n = C(n,0) + C(n,1) + \cdots + C(n,n).$$ Prove this statement is true for all $n ...
1
vote
2answers
513 views

modified $\sum{k{n \choose k}}$ closed form expression

There is probably something stupidly simple I'm missing, but I'm trying to find a closed form for: $$ 2\sum_{k=1}^{(n-1)/2} k \, {n \choose k} \hspace{1cm} (n\textrm{ is odd}) $$ Anyone know how to ...
17
votes
3answers
515 views

A three variable binomial coefficient identity

I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following: $$ \sum_{i+j+k=n} ...
1
vote
2answers
576 views

Limit of binomial coefficient

I would like to find the limit $$ \lim_{n \to \infty} \binom{s}{n+1} = \lim_{n \to \infty} \frac{s (s-1) \cdots (s-n)}{(n+1)!} , $$ where $s \in \mathbb C$. Actually, it would be enough to show that ...
1
vote
1answer
182 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
220 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 ...
3
votes
1answer
401 views

Three problems with binomial coefficients

I found three difficult problems for me, involving binomial coefficients. They are extremely interesting I think, but I don't know if I have enough knowledge to manage. Seem really hard, can you help ...
3
votes
4answers
862 views

Alternating sum of binomial coefficients

Calculate the sum: $$ \sum_{k=0}^n (-1)^k {n+1\choose k+1} $$ I don't know if I'm so tired or what, but I can't calculate this sum. The result is supposed to be $1$ but I always get ...
3
votes
0answers
144 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
2
votes
2answers
348 views

Does this qualify as a proof? (Spivak's 'Calculus')

I'm working through Spivak's 'Calculus' at the moment, and a question about series confused me a bit. I think I have the solution, but I'm not sure if my "proof" holds. The question is: Prove ...
2
votes
1answer
306 views

Going from binomial distribution to Poisson distribution

Why does the Poisson distribution $$\!f(k; \lambda)= \Pr(X=k)= \frac{\lambda^k \exp{(-\lambda})}{k!}$$ contain the exponential function $\exp$, while its relation to the binomial distribution would ...
0
votes
1answer
520 views

Multi binomial theorem application

If i have the polynomial expression $(a_1x+b_1y+c_1)^p. (a_2x+a_2y+c_2)^d$, and with assumptions $a_1+b_1<<c_1$ , $a_2+b_2<<c_2$, can i expand this as a product of binomials using the ...
11
votes
1answer
302 views

A binomial identity

I was wandering if someone knows an elementary proof of the following identity: $$ \frac{(a)_n (b)_n}{(n!)^2} = \sum_{k=0}^n (-1)^k {1-a-b \choose k} \frac{(1-a)_{n-k}(1-b)_{n-k}}{((n-k)!)^2}\ , $$ ...
3
votes
4answers
261 views

Computing a sum of binomial coefficients

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a lot ...