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)

16
votes
5answers
807 views

Combinatorially showing $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$

I am trying to show that $\lim_{n\to \infty}{\frac{2n\choose n}{4^n}}=0$. I found that using stirling's approximation, I can get: $$ \lim_{n\to \infty}{\frac{2n\choose n}{4^n}}= \lim_{n\to \infty}{\...
16
votes
6answers
3k views

Elementary central binomial coefficient estimates

How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ? Does anyone know any better elementary estimates?
16
votes
4answers
987 views

How to solve $\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2$?

I have tried something to solve the series $$\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2.$$ My approach is : $$(1+x)^n=\binom{n}{0} + \binom{n}{1}x + \...
16
votes
3answers
323 views

What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?

Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$ where $n$ is an even positive integer. I tried using binomial identities, but since the binomial coefficient ...
16
votes
4answers
486 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 $...
16
votes
6answers
448 views

Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i ...
16
votes
4answers
555 views

Sum of binomial coefficients $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$

How do I prove the following identity: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$ I am trying to use inclusion-exclusion, and this will boil down to a sum like inclusion-...
16
votes
2answers
232 views

How find this sum $ \frac{1}{1999}\binom{1999}{0}-\frac{1}{1998}\binom{1998}{1}+\cdots-\frac{1}{1000}\binom{1000}{999}$

prove or disprove : $$S=\dfrac{1}{1999}\binom{1999}{0}-\dfrac{1}{1998}\binom{1998}{1}+\dfrac{1}{1997}\binom{1997}{2}-\dfrac{1}{1996}\binom{1996}{3}+\cdots-\dfrac{1}{1000}\binom{1000}{999}=\dfrac{...
16
votes
4answers
535 views

Limit of $\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1}\right)$

I'm trying to calculate the limit for the sum of binomial coefficients: $$S_{n}=\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1} \right).$$
16
votes
1answer
2k views

Combinatorial proof of $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$

Using the following equation: $$\sum_{k=0}^n {n \choose k}3^k=4^n$$ I need to prove that both sides of the equation solve the same combinatorial problem. It's easy to see that the right side of the ...
16
votes
2answers
539 views

Strehl identity for the sum of cubes of binomial coefficients

In 1993 Strehl showed that $$ \sum_k\binom nk^3=\sum_k\binom nk^2\binom{2k}n. $$ I’m interested in a combinatorial proof. Upd (Jan '14). Maybe the original question was too restrictive — I'm now ...
15
votes
6answers
965 views

How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?

I got stuck at the computation of the sum $$ \sum\limits_{k=0}^n (-1)^k{2n-k\choose k}. $$ I think there is no purely combinatorial proof here since the sum can achieve negative values. Could you ...
15
votes
4answers
3k views

$C(n,p)$: even or odd?

Can we determine if a binomial coefficient $C(n,p)$ is even or odd, without calculating its value? ($p\lt n$, $p$ and $n$ are positive integers)
15
votes
2answers
654 views

Sum with binomial coefficients and a square root

I encountered this sum from working on an integral: $$\sum_{k=0}^{n}\binom{n}{k}(-1)^{k}\sqrt{k}$$ I don't think it can be written as a hypergeometric function, because of this square root. Does ...
15
votes
2answers
454 views

Continuous generalization of $\sum_{k=0}^n {n \choose k} = 2^n$?

We know that $$\sum_{k=0}^n {n \choose k} = 2^n.$$ A continuous generalization of the formula would be $$\int_0^{n+1} \frac{\Gamma(n+1)}{\Gamma(n-x+1) \Gamma(x+1)} dx = 2^n?,$$ but this is incorrect ...
15
votes
3answers
290 views

Prove a combinatorial identity

Prove the combinatorial identity $$ \sum_{n_1+\ldots+n_m=n} \;\; \prod_{i=1}^m \frac{1}{n_i}\binom{2n_i}{n_i-1}=\frac{m}{n}\binom{2n}{n-m}, \enspace n_i>0,i=1,\ldots,m $$ I "discovered" this ...
15
votes
2answers
442 views

Show that $ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $

Show that $$ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $$ I don't know whether such identity already exists, or has been posted here before. I discovered this identity while ...
15
votes
1answer
195 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
14
votes
8answers
1k views

Proof of the Hockey-Stick Identity: $\sum_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's the name of this identity? Is it the identity of the Pascal's triangle ...
14
votes
4answers
13k views

Expected Value of a Binomial distribution?

If $\mathrm P(X=k)=\binom nkp^k(1-p)^{n-k}$ for a binomial distribution, then from the definition of the expected value $$\mathrm E(X) = \sum^n_{k=0}k\mathrm P(X=k)=\sum^n_{k=0}k\binom nkp^k(1-p)^{n-k}...
14
votes
10answers
9k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ${{n}...
14
votes
3answers
2k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
14
votes
7answers
1k views

Proving a binomial sum identity $\sum _{k=0}^n \binom nk \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}$

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 ...
14
votes
3answers
535 views

Evaluating a sum involving binomial coefficient in denominator

I came across the following sum: $$\sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)^2}\frac{4^k}{{2k \choose k}}$$ I thought that this can be evaluated using the expansion of $\dfrac{\sin^{-1}x}{\sqrt{1-x^...
14
votes
4answers
1k views

Combinatorial proof that binomial coefficients are given by alternating sums of squares?

A student recently asked whether there was a combinatorial proof of the following identity: $\begin{equation*} \sum^n_{k=1}(-1)^{n-k}k^2 = {n+1 \choose 2}. \end{equation*}$ I was in a rush and ...
14
votes
3answers
468 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
14
votes
2answers
633 views

Asymptotics of sum of binomials

How can you compute the asymptotics of $$S=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$ We have that $n \geq m$ and $n,m \geq 1$. A simple application of ...
14
votes
3answers
499 views

A relationship between matrices, bernoulli polynomials, and binomial coefficients

We define the following polynomials, for $n≥0$: $$P_n(x)=(x+1)^{n+1}-x^{n+1}=\sum_{k=0}^{n}{\binom{n+1}{k}x^k}$$ For $n=0,1,2,3$ this gives us, $$P_0(x)=1\enspace P_1(x)=2x+1\enspace P_2(x)=3x^2+3x+1\...
14
votes
2answers
367 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}\ , $$ ...
14
votes
1answer
186 views

Evaluating $\sum_{n=1}^\infty\frac{1}{n \binom{kn}{n}}$

For $k=1$, the series does not converge. When $k=2$, I can prove that: $$\sum_{n=1}^\infty\frac{1}{n \binom{2n}{n}}=\frac{\pi}{3\sqrt{3}}$$ Using the result of: $$\int_0^\infty \frac{x^ndx}{(x+1)^{...
14
votes
2answers
218 views

“Binomiable” numbers

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$? I've been thinking on this problem with a friend and ...
13
votes
12answers
774 views

Show that $ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$

I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$ Thanks in advance for any help.
13
votes
5answers
2k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
13
votes
4answers
1k views

How this operation is called?

This operation is similar to discrete convolution and cross-correlation, but has binomial coefficients: $$f(n)\star g(n)=\sum_{k=0}^n \binom{n}{k}f(n-k)g(k) $$ Particularly, $$a^n\star b^n=(a+b)^n$$...
13
votes
4answers
439 views

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

Show that $$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$ I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you
13
votes
6answers
572 views

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
13
votes
6answers
344 views

Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

How would I prove $$ \sum\limits_{\vphantom{\large A}i\,,\,j\ \geq\ 0}{n-i \choose j} {n-j \choose i} =F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of ...
13
votes
6answers
2k views

Proof: if $p$ is prime, and $0<k<p$ then $p$ divides $\binom pk$ [duplicate]

Question : If $p$ is prime, and $0< k< p$ show that $ p \mid {p \choose k}$ ${p \choose k}$ can be rewritten as: $${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot k(k-1)(k-2)\dots3\cdot2\...
13
votes
2answers
506 views

Asymptotics of the sum of squares of binomial coefficients

We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
13
votes
1answer
255 views

Fitting a closed curve on the roots of ${x \choose k}-c$

Let $${n \choose k} = \frac1{(n+1) \operatorname{B}(n-k+1, k+1)}.$$ be the generalized binomial coefficient, and here $\operatorname{B}$ is the Beta function. Let $f_{k,c}(x)$ be the following ...
13
votes
2answers
291 views

Proving a certain binomial identity with three parameters

I would like to prove the following identity: $$\sum_{m\geq 0} (-1)^{i-m}{m+k \choose m} {i-1 \choose m-1}{m+k+1 \choose j} = \sum_{m\geq 0} {m+k \choose k}{k+1 \choose i-m}{k+1 \choose j-m}$$ for ...
13
votes
1answer
283 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} e^{\log\...
13
votes
2answers
239 views

When $\frac{C(n, k)}{n^{k-1}} > 1$?

I came across this while considering the subset sum problem in relation to another problem. Define the ratio, $$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$ and the integer ...
13
votes
1answer
362 views

Binomial sum of $n$ terms in closed form

Can we calculate the given combinatorial sum in closed form? $$ \frac{\binom{2}{0}}{1}+\frac{\binom{4}{1}}{2}+\frac{\binom{8}{2}}{3}+\frac{\binom{16}{3}}{4}+\cdots+\frac{\binom{2^n}{n-1}}{n}$$
13
votes
3answers
2k views

Proving $k \binom{n}{k} = n \binom{n-1}{k-1}$

Suppose we want to prove $$ k \binom{n}{k} = n \binom{n-1}{k-1}$$ In the LHS we are choosing a team of $k$ players from $n$ players. Then we are choosing a captain. In the RHS we are choosing a ...
12
votes
7answers
574 views

Prove that $2^n < \binom{2n}{n} < 2^{2n}$

Prove that $2^n < \binom{2n}{n} < 2^{2n}$. This is proven easily enough by splitting it up into two parts and then proving each part by induction. First part: $2^n < \binom{2n}{n}$. The ...
12
votes
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
12
votes
4answers
2k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
12
votes
7answers
257 views

How prove this inequality $(1+\frac{1}{16})^{16}<\frac{8}{3}$

show that $$(1+\dfrac{1}{16})^{16}<\dfrac{8}{3}$$ it's well know that $$(1+\dfrac{1}{n})^n<e$$ so $$(1+\dfrac{1}{16})^{16}<e$$ But I found this $e=2.718>\dfrac{8}{3}=2.6666\cdots$ ...
12
votes
5answers
2k views

Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially

I have to give a combinatorial proof of $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$ I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have ...