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)

55
votes
2answers
3k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is ...
46
votes
5answers
3k views

$n$th derivative of $e^{1/x}$

I am trying to find the $n$'th derivative of $f(x)=e^{1/x}$. When looking at the first few derivatives I noticed a pattern and eventually found the following formula $$\frac{\mathrm d^n}{\mathrm ...
42
votes
2answers
3k views

Identity for convolution of central binomial coefficients

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
37
votes
3answers
1k views

Solutions to $\binom{n}{5} = 2 \binom{m}{5}$

In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says: On National Public Radio, the Weekend Edition program posed the following probability problem: Given a certain number of ...
30
votes
3answers
4k views

The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that: the product of non-adjacent vertices is constant. the greatest common ...
28
votes
1answer
1k views

X'mas Combinatorics

Inspired the various** algebraic X'mas greetings sent to me over the festive period, I thought I would try to devise one of my own. $$\Large ...
28
votes
2answers
4k views

How do I count the subsets of a set whose number of elements is divisible by 3? 4?

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that $\displaystyle \sum_{k=0}^{n} {n ...
27
votes
7answers
2k views

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Let $m,n\ge 0$ be two integers. Prove that $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$ where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = ...
27
votes
2answers
605 views

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

Wolfram MathWorld states that $$ \sum_{n=1}^{\infty} \frac{1}{n^{3} \binom{2n}{n}} = \frac{ \pi \sqrt{3}}{18} \Big[ \psi_{1} \left(\frac{1}{3} \right) - \psi_{1} \left(\frac{2}{3} \right) \Big]- ...
26
votes
7answers
2k views

Prove: $\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx$ for $0 \leq k \leq n$

I would like your help with proving that for every $0 \leq k \leq n$, $$\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx . $$ I tried to integration by parts and to get a pattern or to ...
24
votes
6answers
1k views

Proofs of $\lim\limits_{n \to \infty} \left(H_n - 2^{-n} \sum\limits_{k=1}^n \binom{n}{k} H_k\right) = \log 2$

Let $H_n$ denote the $n$th harmonic number; i.e., $H_n = \sum\limits_{i=1}^n \frac{1}{i}$. I've got a couple of proofs of the following limiting expression, which I don't think is that well-known: ...
24
votes
2answers
2k views

How to reverse the $n$ choose $k$ formula?

If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below: $$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$ What if I want to go the ...
22
votes
3answers
2k views

Is there a direct proof of this lcm identity?

The identity $\displaystyle (n+1) \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \text{lcm}(1, 2, ... n+1)$ is probably not well-known. The only way I know how to prove ...
21
votes
6answers
7k views

prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the first n even ...
21
votes
1answer
690 views

A Combinatorial Proof of Dixon's Identity

Dixon's Identity states: $$ \sum_{k} (-1)^k\binom {a+b}{b+k}\binom{b+c}{c+k}\binom{c+a}{a+k} = \binom{a+b+c} {a,b,c}$$ A bit of history: The case $a=b=c$ was proved by Dixon in 1891 using ...
20
votes
3answers
502 views

How prove this sum $\sum_{n=1}^{\infty}\binom{2n}{n}\frac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}$

show that $$\sum_{n=1}^{\infty}\binom{2n}{n}\dfrac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}=5+4\sqrt{2}\left(\log{\dfrac{2\sqrt{2}}{1+\sqrt{2}}}-1\right)$$ where ...
20
votes
4answers
2k views

“Binomial theorem”-like identities

There are several identities which resemble the binomial theorem. For starters, we have the binomial theorem itself: $$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$$ But I just learned from the ...
20
votes
0answers
748 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: $n,k$ are natural numbers and $k\le n$. $t$ is taken over all ...
19
votes
5answers
8k views

Proof that a Combination is an integer

From its definition a combination $(^n_k)$, is the number of distinct subsets of size k from a set of n elements. This is clearly an integer, however I was curious as to why the equation ...
19
votes
6answers
1k views

Exercise from Comtet's Advanced Combinatorics: prove $27\sum_{n=1}^{\infty }1/\binom{2n}{n}=9+2\pi \sqrt{3}$

In exercise 36 Miscellaneous Taylor Coefficients using Bernoulli numbers on pages 88-89 of Louis Comtet's Advanced Combinatorics, 1974, one is asked to obtain the following explicit formula for the ...
19
votes
2answers
876 views

Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem

In the recent question "What's the probability that a sequence of coin flips never has twice as many heads as tails?" I argue in my answer that the number of ways $S(n)$ to obtain twice as many heads ...
19
votes
2answers
13k views

A comprehensive list of binomial identities?

Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
19
votes
4answers
583 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} ...
19
votes
1answer
2k views

A proof of Wolstenholme's theorem

This was inspired by this question. I tried to use the identity $${2n \choose n}=\sum_{k=0}^n {n \choose k}^2$$ (see this question) to prove that $$\binom{2p}p\equiv2\pmod{p^3}$$ if $p\gt3$ is ...
18
votes
6answers
2k views

Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: ...
18
votes
7answers
4k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...
18
votes
3answers
13k views

Combinatorial proof of summation of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Can you guys help me prove this? There is a way of proving this logically but I was hoping to find a more "mathematical" proof, if possible. $$\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n ...
18
votes
6answers
605 views

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

How do I prove the following identity directly? $$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$ I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized ...
18
votes
1answer
711 views

How to prove a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
17
votes
4answers
391 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
17
votes
2answers
346 views

On computing: $ \gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right)$

I would like to calculate $$ d=\gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right) $$ We have: $$ \sum_{k=0}^{n-1}{2n \choose 2k+1}=2^{2n-1} $$ $$ d=2^k, 0\leq k\leq2n-1 $$ ...
17
votes
1answer
417 views

What is the binomial sum $\sum_{n=1}^\infty \frac{1}{n^5\,\binom {2n}n}$ in terms of zeta functions?

We have the following evaluations: $$\begin{aligned} &\sum_{n=1}^\infty \frac{1}{n\,\binom {2n}n} = \frac{\pi}{3\sqrt{3}}\\ &\sum_{n=1}^\infty \frac{1}{n^2\,\binom {2n}n} = ...
17
votes
5answers
547 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ I don't know how to prove this at all. Could you show me how ...
16
votes
8answers
2k views

Proving $\sum\limits_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$

Show that $$\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$$ So for odd $n$ we have an even number of terms. So $\binom{n}{k} = \binom{n}{n-k}$ which have opposite signs. Thus the sum is $0$. For even $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$ + ... + ...
16
votes
4answers
630 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
6answers
401 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
438 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
2answers
426 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
16
votes
4answers
568 views

Proving that $\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\frac{1}{2}n^n$

How can we prove that $$\displaystyle\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\dfrac{1}{2}n^n$$ where $\displaystyle\binom{n}{i}=\dfrac{n!}{i!(n-i)!}$. This inequality is very interesting. I ...
16
votes
4answers
530 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).$$
15
votes
5answers
644 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 ...
15
votes
4answers
2k 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?
15
votes
5answers
485 views

Sum with binomial coefficients: $\sum_{k=1}^m \frac{1}{k}{m \choose k} $

I got this sum, in some work related to another question: $$S_m=\sum_{k=1}^m \frac{1}{k}{m \choose k} $$ Are there any known results about this (bounds, asymptotics)?
15
votes
2answers
5k views

Approximating the logarithm of the binomial coefficient

We know that by using Stirling approximation: $\log n! \approx n \log n$ So how to approximate $\log {m \choose n}$?
15
votes
4answers
479 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 ...
15
votes
2answers
378 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
2answers
569 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
1k views

Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...