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)

7
votes
2answers
680 views

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
7
votes
1answer
483 views

proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$

I'm looking for a proof of this identity: $$ 1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k} $$ I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum ...
7
votes
2answers
169 views

Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I ...
7
votes
1answer
214 views

$\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof

Is there a simple combinatorial proof for the following identity? $$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$ where $m,j \geq 0$, $k \geq n \geq 0$.
7
votes
1answer
297 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
7
votes
2answers
309 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 ...
7
votes
1answer
175 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
7
votes
3answers
115 views

A binomial identity from Mathematical Reflections

Here is the problem: Let $m,n$ be positive integers with $n>m$. Prove that $\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$ This ...
7
votes
1answer
171 views

Determining when a certain binomial sum vanishes

Consider the following sum of signed binomial coefficients: $$S_{n,a,p} = \sum_{i \equiv a \mod p} \binom{n}{i}(-1)^i$$ ($n$ is a positive integer, $p$ is an odd prime, $a$ is between $0$ and ...
7
votes
1answer
1k views

Asymptotics of binomial coefficients and the entropy function

I found a question while I was trying to practice Combinatorics and Probabilistic methods.I tried to solve it with no success.. this is the question: Use the Stirling approximation of the ...
7
votes
3answers
274 views

Asymptotic difference between a function and its binomial average

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number. Dividing by $2^n$, we ...
7
votes
2answers
167 views

Does this really converge to 1/e? (Massaging a sum)

Short version: can we prove that $$\sum_{k=0}^n (-1)^k \binom{n}{k}^2 \frac{k!}{n^{2k}} \to \frac1e$$ as $n \to \infty$? Long version: First, consider $$a_n = \sum_{k=0}^n \frac{(-1)^k}{k!}$$ It is ...
7
votes
2answers
3k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
7
votes
5answers
206 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
7
votes
1answer
386 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 ...
7
votes
1answer
97 views

Is $(n+\ell)^{-1}\binom{kn}{n}$ an integer for only $(\ell,k)=(1,2)$?

Find all pairs $(\ell,k)$ of natural numbers, such that the number $\dfrac1{n+\ell}\dbinom{kn}{n}$ is an integer for all natural $n$. Is $(\ell,k)=(1,2)$ the only solution?
7
votes
1answer
248 views

Vandermonde identity in a ring

Let $R$ be a commutative $\mathbb{Q}$-algebra. For $r \in R$ and $n \in \mathbb{N}$ we can define the binomial coefficient $\binom{r}{n}$ as usual by $\binom{r}{0}=1$ and ...
7
votes
1answer
310 views

Asymptotics for sum of binomial coefficients from Concrete Mathematics

Concrete Mathematics EXERCISE 9.25: Supposing \[ S_n = \sum_{k=0}^n \binom{3n}k \] Prove that \[ S_n = \binom{3n}{n}\left(2-\frac4n+O\left(\frac1{n^2}\right)\right) \] This sequence also ...
7
votes
0answers
134 views

Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$

I found this question in an old problem set. There's no hint or solution mentioned. For $n \geq 3$, prove or disprove the existence of $(x,y,z) \in \mathbb N^3, ...
7
votes
1answer
274 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
6
votes
7answers
377 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
5answers
815 views

Simplify $\sum_{i=0}^n (i+1)\binom ni$

Simplifying this expression$$1\cdot\binom{n}{0}+ 2\cdot\binom{n}{1}+3\cdot\binom{n}{2}+ \cdots+(n+1)\cdot\binom{n}{n}= ?$$ $$\text{Hint: } \binom{n}{k}= \frac{n}{k}\cdot\binom{n-1}{k-1} $$
6
votes
4answers
1k views

Probability that given a 1000 page book with 1000 misprints, a page will have 3 misprints.

Setting A book of 1000 pages contains 1000 misprints. Estimate the chances that a given page contains at least three misprints. Solution My solution is ...
6
votes
5answers
383 views

Closed-form expression for $\sum_{k=0}^n\binom{n}kk^p$ for integers $n,\,p$

Is there a closed-form expression for the sum $\sum_{k=0}^n\binom{n}kk^p$ given positive integers $n,\,p$? Earlier I thought of this series but failed to figure out a closed-form expression in $n,\,p$ ...
6
votes
2answers
161 views

What is the coefficient of $x^{25}$ in $(x^3 + x + 1)^{10}$?

Here's what I have so far on the off chance that my thinking is correct... So using Vieta's the coefficient of the $x^{25}$ should be $-(r_1r_2r_3r_4r_5+r_1r_3r_4r_5r_6+...+r_6r_7r_8r_9r_{10})$ Since ...
6
votes
3answers
214 views

Short and intuitive proof that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$

The simple inequality that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$ has a number of different proofs. But is there a particularly intuitive, short and elegant proof that uses the natural ...
6
votes
5answers
255 views

Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?

I have run across the following multinomial series: $$ \sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} $$ Here, $d>1$. This seems like a formula which has either a well-known identity, ...
6
votes
2answers
71 views

Is there a “counting groups/committees” proof for the identity $\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$?

This is exercise number $57$ in Hugh Gordon's Discrete Probability. For $n \in \mathbb{N}$, show that $$\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$$ My algebraic solution: ...
6
votes
2answers
115 views

The value of $\binom{50}0\binom{50}1+\binom{50}1\binom{50}2+\dots+\binom{50}{49}\binom{50}{50}$ is

The value of $\binom{50}0\binom{50}1+\binom{50}1\binom{50}2+\dots+\binom{50}{49}\binom{50}{50}$ is? I tried this: ...
6
votes
2answers
294 views

Is there a binomial identity for this expression $\frac{\binom{r}{k}}{\binom{n}{k}}$?

What I'm trying to prove is this summation: $$\sum_{i=0}^{k} \dfrac{\dbinom{r}{i} \cdot \dbinom{n - r}{k - i}}{\dbinom{n}{k}} \cdot i = \dfrac{r}{n} \cdot k$$ I used induction on $k$ as follows: ...
6
votes
3answers
133 views

Bounds for $\binom{n}{cn}$ with $0 < c < 1$.

Are there really good upper and lower bounds for $\binom{n}{cn}$ when $c$ is a constant $0 < c < 1$? I know that $\left(\frac{1}{c^{cn}}\right) \leq \binom{n}{cn} \leq ...
6
votes
3answers
251 views

Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is $${n \choose k} {n-1 \choose k} k!.$$ Is there a ...
6
votes
3answers
219 views

How to understand this combinatorially: $\sum^{2k}_{i=0} \binom{4k}{2i} (-1)^{i}=2^{2k}(-1)^{k}$

The TAs in my department are stuck in assisting an undergraduate with the following problem: $$\sum^{2k}_{i=0} C^{4k}_{2i}(-1)^{i}=2^{2k}(-1)^{k}.$$ We tried to solve this via induction (obviously ...
6
votes
3answers
1k views

Inductive proof for the Binomial Theorem for rising factorials

I want to proove the following equality containing rising factorials $$(x+y)^\overline{n}\overset{(*)}{=}\sum_{k=0}^n\binom{n}{k}x^\overline{k}y^\overline{n-k}.$$ For $n=1$ this equality is ...
6
votes
4answers
5k views

How to simplify or calculate a formula with very big factorials

I'm facing a practical problem where I've calculated a formula that, with the help of some programming, can bring me to my final answer. However, the numbers involved are so big that it takes ages to ...
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$?
6
votes
1answer
291 views

Inequality involving factorial

I am trying to prove following inequality: $$\binom{n}{k}<(en/k)^k$$ I tried Stirling approximation but I could not get anything further. Then I get $$\binom{n}{k}\approx \frac{\sqrt{2\pi ...
6
votes
4answers
255 views

Truncated alternating binomial sum

It is easily checked that $\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the ...
6
votes
4answers
187 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$. ...
6
votes
1answer
321 views

Is this binomial coefficient identity known?

I stumbled across this identity involving binomial coefficients this morning: If $n$, $k$, $a$, and $b$ are positive integers and $n=a+b$, then $ \displaystyle \binom{n}{k} =\sum_{i=0}^k ...
6
votes
3answers
345 views

Yet another sum involving binomial coefficients

Let $k,p$ be positive integers. Is there a closed form for the sums $$\sum_{i=0}^{p} \binom{k}{i} \binom{k+p-i}{p-i}\text{, or}$$ $$\sum_{i=0}^{p} \binom{k-1}{i} \binom{k+p-i}{p-i}\text{?}$$ ...
6
votes
2answers
517 views

How to solve 0.5 choose 4?

I was solving this problem for homework. It says, in the problem, that if n is positive you use the generalized definition of binomial coefficients. In my case, n is positive so I just plugged n= 0.5 ...
6
votes
3answers
476 views

Binomial Theorem past exam question, what do I do?

I have trouble understanding what I'm supposed to do in some of these math questions. Here's an exam question from an old exam: Let $A$ be a set with $n$ elements. The number of subsets of $A$ with ...
6
votes
5answers
429 views

Choice Problem: choose 5 days in a month, consecutive days are forbidden

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand. Example 3.19. A medical student has to work in a hospital for five days in January. ...
6
votes
1answer
2k views

Using the Taylor expansion for ${(1+x)}^{-1/2}$, evaluate $\sum_{n=0}^\infty \binom{2n}{n} a^n$

Using the Taylor expansion for $${(1+x)}^{-1/2}$$ we have $${(1+x)}^{-1/2}= \sum_{n=0}^\infty \binom{-1/2}{n} (x^n)$$ for $|x|<1$. But if $|a| <1$, how can we use the above fact to find ...
6
votes
5answers
148 views

Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $

I need any hint with calculating of the sum $$ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}. $$ Maple give the strange unsimplified result $$ I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( ...
6
votes
5answers
265 views

Formula for $\sum_{k=0}^n k^d {n \choose 2k}$

If $d \geq 1$ is an integer, is there a general formula for $$\sum_{k=0}^n k^d {n \choose 2k}\,?$$ We know that $\sum_{k=0}^n k {n \choose 2k} = \frac{n2^n}{8}$ and $\sum_{k=0}^n k^2 {n \choose 2k} = ...
6
votes
2answers
282 views

a problem about binomial coefficients sum

I want to know how to caculate $\binom{2n}{0}^3-\binom{2n}{1}^3+\cdots+(-1)^k\binom{2n}{k}^3 \cdots+\binom{2n}{2n}^3$? The sum equals $ (-1)^{n}\binom{3n}{2n}\binom{2n}{n} $, but I donot know how to ...
6
votes
3answers
142 views

Help with a Binomial Identity: $\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = 2^{n+1}$

The following is a problem from the 5th edition of Niven's An Introduction to the Theory of Numbers: Problem 23 of Section 1.4 asks us to prove that $$\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = ...
6
votes
2answers
213 views

Wanted: Insight into formula involving binomial coefficients

There is the formula $$\sum_i (-1)^i\binom{a}{k+i}\binom{l+i}{b} = (-1)^{a+k} \binom{l-k}{b-a}.$$ Only finitely many summands are non-zero (those for $i\in\{b-l,\ldots,a-k\}$), so the sum is finite. ...