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)

12
votes
6answers
826 views

Proving a binomial sum identity

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 ...
12
votes
3answers
318 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
12
votes
3answers
515 views

How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer ...
12
votes
4answers
1k 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 ...
12
votes
1answer
322 views

Proof of $\sum_{n=1}^\infty \frac{1}{n^4 \binom{2n}{n}}=\frac{17\pi^4}{3240}$

Recently, I was able to prove that $$\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}}= \frac{\pi^2}{18}$$ But does anybody know ...
12
votes
2answers
335 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 ...
12
votes
1answer
1k 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 ...
12
votes
2answers
340 views

Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$ is the following "committee" argument, which seems the most common. There are $\binom{n}{k}$ ...
12
votes
1answer
672 views

Counting subsets with r mod 5 elements

Some time ago Qiaochu Yuan asked about counting subsets of a set whose number of elements is divisible by 3 (or 4). The story becomes even more interesting if one asks about number of subsets of ...
12
votes
0answers
432 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 ...
11
votes
5answers
465 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 ...
11
votes
3answers
521 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 ...
11
votes
4answers
1k 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 ...
11
votes
5answers
409 views

How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$

Let $p \in \mathbf{N}$. I don't know how to prove that $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ and $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$ ...
11
votes
3answers
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 ...
11
votes
3answers
306 views

Prove that $\,\,\displaystyle\inf_{n\in\mathbb N}\sum_{k=0}^{p}\lvert\sin{(n+k)^p}\rvert>0$

For any positive integer number $p$, show that $$\inf\left\{ {\left\vert\sin{(n^p)}\right\vert+\left\vert\sin{(n+1)^p}\right\vert+\cdots+ \left\vert\,\sin{(n+p)^p}\right\vert\, :\,n\in ...
11
votes
3answers
201 views

Calculating $\sum_{0\le k\le n/2} \binom{n-k}{k}$

I would like to evaluate: $$\sum_{0\le k\le n/2}\binom{n-k}{k}$$ Any idea?
11
votes
4answers
277 views

Determine $\displaystyle \lim_{n \to \infty}{{n} \choose {\frac{n}{2}}}\frac{1}{2^n}$, where each $n$ is even

For each positive even integer $n$, set $$P_n = \displaystyle {{n} \choose {\frac{n}{2}}}\frac{1}{2^n}.$$ Show that $\displaystyle \lim_{n \to \infty} P_n$ exists and determine its value. Here's ...
11
votes
4answers
777 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 ...
11
votes
2answers
279 views

A conjecture including binomial coefficients

Question: $$\sum_{k=1}^{n}k\binom{2n}{n+k}=\frac n2\binom{2n}{n}$$ is true for every $n\in \mathbb N$? If this is true, then how can we prove this? When I was playing numbers, I conjectured ...
11
votes
2answers
348 views

Sum of binomial coefficients

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 ...
11
votes
2answers
224 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 ...
11
votes
1answer
7k 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 ...
11
votes
1answer
207 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 ...
11
votes
3answers
284 views

Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
11
votes
1answer
273 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}\ , $$ ...
11
votes
1answer
618 views

Factorial canceling on expansion of binomial coefficients on Concrete Mathematics

On Concrete Mathematics section 5.5, which is teaching the hypergeometric functions, generalized factorials is defined as: \[ \frac 1 {z!} = \lim_{n \to \infty} \binom{n+z}{n}n^{-z} \] where \[ ...
10
votes
6answers
533 views

Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$ [duplicate]

I need to evaluate, for a certain worded question: If n is even $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n}$$ If n is odd ...
10
votes
6answers
724 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 ...
10
votes
3answers
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?
10
votes
3answers
295 views

Computing: $\lim\limits_{n\to\infty}\left(\prod\limits_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$

I try to compute the following limit: $$\lim_{n\to\infty}\left(\prod_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$$ I'm interested in finding some reasonable ways of solving the limit. I don't find any ...
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
10
votes
4answers
376 views

Show that if $\prod\limits_{k=1}^{n}(x+a_k)=\sum\limits_{k=0}^{n} {n\choose k}a^k_kx^{n-k}$ then $a_1=a_2=a_3=…=a_{n-1}=a_n$

Let $a_0=1$. Prove that, if $$\prod_{k=1}^{n}(x+a_k)=\sum_{k=0}^{n} {n\choose k}a^k_kx^{n-k}=x^n+{n\choose 1}a_1x^{n-1}+{n\choose 2}a^2_2x^{n-2}+....+a^n_n,$$ then ...
10
votes
7answers
474 views

Summation simplification $\sum_{k=0}^{n} \binom{2n}{k}^2$

$\sum_{k=0}^{n} \binom{2n}{k}^2$ So i'm trying to simplify this one and I'm stuck in nowhere. Some kind of tip would be appreciated. Thanks! :)
10
votes
2answers
279 views

Show that $\displaystyle\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 this $$ \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.
10
votes
2answers
329 views

The integral $\int_0^1 \frac{(x+1)^n-1}{x} dx$

I know that the integral $\int_0^1 \frac{(x+1)^n-1}{x} dx,$ for $n \in \mathbb{Z}^+$, can be evaluated by expanding the numerator with the binomial theorem and integrating term by term. You get the ...
10
votes
2answers
162 views

Prove the identity $ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$

$$ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$$ Class themes are: Generating functions and formal power series.
10
votes
6answers
176 views

A limit on binomial coefficients

Let $$x_n=\frac{1}{n^2}\sum_{k=0}^n \ln\left(n\atop k\right).$$ Find the limit of $x_n$. What I can do is just use Stolz formula. But I could not proceed.
10
votes
2answers
117 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
10
votes
2answers
249 views

The Fermat prime 257 and binomial sum $\sum_{n=0}^\infty \frac{(-1)^n}{\binom {8n}{4n}}$?

We have, $\begin{aligned} \sum_{n=0}^\infty \frac{(-1)^n}{\binom n{n/2}} &= \frac{4}{27}(9-\pi\sqrt{3}\,)\\[2.5mm] \sum_{n=0}^\infty \frac{(-1)^n}{\binom {2n}n} &= \frac{4}{5} - ...
10
votes
1answer
222 views

Evaluating $\sum_{k=0}^n \binom{n}{k} 2^{k^2}$

Can someone please help me simplifying this sum $$\sum_{k=0}^n \binom{n}{k} 2^{k^2}$$ Wolframalpha fails (see here). Thanks in advance. The sum counts the number of (labelled) digraphs (with ...
10
votes
1answer
135 views

Can this product be written so that symmetry is manifest?

Let $i,$ $j,$ $k$ be nonnegative integers such that $i+j+k$ is even. The expression $$(-1)^{j+k}\binom{i+j+k}{i,j,k}\prod_{\ell=0}^{k-1} \frac{i-j+k-2\ell-1}{i+j+k-2\ell-1}$$ apparently computes the ...
10
votes
3answers
581 views

Prove the lecturer is a liar…

I was given this puzzle: At the end of the seminar, the lecturer waited outside to greet the attendees. The first three seen leaving were all women. The lecturer noted " assuming the attendees are ...
10
votes
1answer
193 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*} ...
9
votes
9answers
381 views

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

I need a hand in showing that $$ \sum_{n=2}^m {n \choose 2} = {m+1 \choose 3}$$ Thanks in advance for any help.
9
votes
4answers
2k 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 ...
9
votes
3answers
292 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
9
votes
2answers
3k 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}$?
9
votes
4answers
344 views

Binomial Theorem Identities

What's the actual difference between these two formulas (they're both in the chapter regarding binomial theorem). They're from two different textbooks : $${n\choose k}+{n\choose k+1}={n+1\choose ...
9
votes
3answers
786 views

Simplify $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$

Can this sum be simplified: $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$ Or at least is there a simple fairly tight upperbound? EDIT So I think this sum is more easily bounded than I ...