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)

14
votes
1answer
378 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 ...
13
votes
4answers
790 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 ...
13
votes
3answers
374 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.
13
votes
1answer
211 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
1answer
372 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 ...
13
votes
1answer
153 views

Prove $\sum_{i=0}^n \binom{n}{i}^2x^{n-i} = 0$ has $n$ negative roots

Let's $n \in \mathbb{Z^+}$, how to $\text{prove}|\text{disprove}$ that: the equation $\boxed{\sum_{i=0}^n \binom{n}{i}^2x^{n-i} = 0}$ has exactly $n$ distinct negative roots. My friend get ...
13
votes
2answers
230 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
338 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
1k 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
521 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
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 ...
12
votes
6answers
904 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
4answers
2k 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)
12
votes
3answers
381 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
620 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
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 ...
12
votes
3answers
330 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 ...
12
votes
2answers
387 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
2answers
394 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 ...
12
votes
2answers
247 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 ...
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
405 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
261 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*} ...
12
votes
1answer
278 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 ...
12
votes
1answer
704 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 ...
11
votes
3answers
816 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
3k 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 ...
11
votes
6answers
781 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 ...
11
votes
5answers
420 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
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?
11
votes
6answers
5k 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= ...
11
votes
4answers
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
326 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 ...
11
votes
3answers
209 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
417 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 ...
11
votes
4answers
294 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
5answers
229 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 ...
11
votes
4answers
841 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
5answers
212 views

Sum $\displaystyle \sum_{n=i}^{\infty} {2n \choose n-i}^{-1}$

$\displaystyle \sum_{n=i}^{\infty} {2n \choose n-i}^{-1}=\sum_{n=i}^{\infty} \frac {1}{{2n \choose n-i}}$ is a very interesting one. Here is what I have from WolframAlpha. $\displaystyle ...
11
votes
3answers
186 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.
11
votes
2answers
298 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 with playing numbers, I conjectured ...
11
votes
2answers
265 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} - ...
11
votes
2answers
534 views

Closed form for a sum involving binomial coefficients

Let $n,k$ be positive integers. Is there a closed form of the sum $$\sum_{s=0}^{k} \binom{n}{s} \binom{s}{k-s}\text{?}$$ By that I mean a representation which is free of sums and hypergeometric ...
11
votes
1answer
123 views

How find all postive integer number such $(n+k)\nmid \binom{2n}{n}$

Question: Find the all integer $k$,such there are exist infinitely many $n$ such $$(n+k)\nmid \binom{2n}{n}$$ This is china 2014 (CMO problem 4),it's have been end exam three hours ago. I ...
11
votes
3answers
310 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\left(\vphantom{\Huge A}\binom{n}{k}\right)$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
11
votes
1answer
298 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
656 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
586 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
9answers
533 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.