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)

9
votes
4answers
416 views

Orthogonality for Binomial Coefficients

Could somebody explain to me where these two formulas come from as applications of the binomial theorem? $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$ for non-negative integers $r\lt n$. And ...
9
votes
3answers
853 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 ...
9
votes
4answers
545 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
6answers
945 views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
9
votes
2answers
468 views

Can this sum be simplified: $ \sum_{k=0}^{n-1} { n -1 \choose k } (-2)^{k} (2n - k)! $?

Can this expression be further simplified : $ \sum_{k=0}^{n-1} { n -1 \choose k } (-2)^{k} (2n - k)! $? This is the coefficient of $x^{2n}$ in the formal power series expansion of $(1-2x)^{n-1} \times ...
9
votes
1answer
697 views

How to compute the asymptotic growth of $\binom{n}{\log n}$?

I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$ It sounds like it's something simple, but I can't get a nice expression I can use. Any ideas on how to do this?
9
votes
2answers
342 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
9
votes
3answers
527 views

Proving the sum of squares of sine and cosine using the Cauchy product formula

Here are the power series of sine and cosine: $$\sin(x) = \sum_{n=0}^{\infty} (-1)^n \frac {x^{2n+1}} {(2n+1)!}$$ and $$\cos(x) = \sum_{n=0}^{\infty} (-1)^n \frac {x^{2n}} {(2n)!}$$ How can it be ...
9
votes
4answers
244 views

An upper bound for $\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$?

Does anyone know of a reasonable upper bound for the following: $$\sum_{i = 1}^m \frac{\binom{i}{k}}{2^i},$$ where we $k$ and $m$ are fixed positive integers, and we assume that $\binom{i}{k} = 0$ ...
9
votes
4answers
303 views

Prove that $\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$ [duplicate]

Prove that $$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ What should I do for this equation? Should I focus on proving ...
9
votes
3answers
747 views

Obtaining binomial coefficients without “counting subsets” argument

I want to obtain the formula for binomial coefficients in the following way: elementary ring theory shows that $(X+1)^n\in\mathbb Z[X]$ is a degree $n$ polynomial, for all $n\geq0$, so we can write ...
9
votes
2answers
511 views

Derive a closed form for a sum with inverse binomial coefficients

First off, I would like to apologize again for the integral I posted several days ago involving $\zeta(5)$. I was careless and did not examine the decimals out far enough. With that said, I would ...
9
votes
4answers
246 views

Bounding ${(2d-1)n-1\choose n-1}$

Claim: ${3n-1\choose n-1}\le 6.25^n$. Why? Can the proof be extended to obtain a bound on ${(2d-1)n-1\choose n-1}$, with the bound being $f(d)^n$ for some function $f$? (These numbers ...
9
votes
2answers
87 views

When is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $n,m,j$?

As stated in the title: when is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $m,j,n$? I was thinking about this problem a couple of days ago because in all my years of ...
9
votes
3answers
139 views

Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$

This result, $$\prod_{k=1}^{\infty} \big\{\big(1+\frac1{k}\big)^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$$ is in a paper by Hirschhorn in the current issue of the Fibonacci Quarterly (vol. ...
9
votes
3answers
1k views

Proving $\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$ [duplicate]

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
9
votes
2answers
427 views

Sum of squares of binomial coefficients

I came across the following sum in reference to this question $$\sum_{n=0}^{\infty} \frac{1}{2^{5 n}} \binom{2 n}{n}^2 = \frac{\sqrt{\pi}}{\Gamma \left( \frac{3}{4}\right)^2}$$ The sum on the left ...
9
votes
2answers
99 views

How to prove $\sum_{i=1}^ki^k(-1)^{k-i}\binom {k+1}{i} =(k+1)^k$

How to prove $\sum_{i=1}^ki^k(-1)^{k-i}\binom {k+1}{i} =(k+1)^k$ where k is a positive integer. Any hints can help.
9
votes
2answers
310 views

An asymptotic expression of sum of powers of binomial coefficients.

Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ ...
9
votes
3answers
169 views

Combinatorial interpretation of identity: $\sum_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2$

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
9
votes
2answers
275 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
9
votes
3answers
225 views

A sum with binomial coefficients

Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$
9
votes
2answers
414 views

Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem. I have $n$ items that I can place on $m$ positions. $m$ ...
9
votes
1answer
108 views

Consecutive terms in Pascal's Triangle

is it known whether or not there are infinitely many pairs of consecutive terms in this sequence: http://oeis.org/A006987 ? The sequence is the list of numbers expressible in the form ...
9
votes
1answer
154 views

Binomial formula for $(x+1)^{1/3}$ (related to Newton's binomial theorem)

I know that $$\displaystyle \sqrt{1+x} = \sum_{j=0}^{\infty}\left( \frac{(-1)^{(j-1)}}{2^{2j-1}\cdot(2j-1)}\binom{2j-1}{j}x^j\right). $$ Now, I want to evaluate $\sqrt[3]{1+x}$ but stuck at some ...
9
votes
4answers
416 views

Evaluate a finite sum with four factorials

Given positive integers $k, m, n$ such that $1 \leq k \leq m \leq n$. Evaluate $$ \sum^{n}_{i\mathop{=}0}\frac{1}{n+k+i}\cdot\frac{(m+n+i)!}{i!(n-i)!(m+i)!}$$ Any hints? I'm stuck on ...
9
votes
0answers
172 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
8
votes
6answers
397 views

Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$ I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a ...
8
votes
4answers
389 views

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

I know that the expansion of $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k}$ equals to zero. But why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$ also equal to zero for $n \geq 2$? I've been ...
8
votes
4answers
293 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
8
votes
7answers
1k views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
8
votes
6answers
382 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
8
votes
4answers
234 views

Proving this binomial identity $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$

A teacher gave this as a homework question, and I have tried but haven't been able to arrive at a solution. $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$ Could someone prove it, or at least ...
8
votes
3answers
343 views

Intuitive explanation for a polynomial expansion?

Is there an ituitive explanation for the formula: $$ \frac{1}{\left(1-x\right)^{k+1}}=\sum_{n=0}^{\infty}\left(\begin{array}{c} n+k\\ n \end{array}\right)x^{n} $$ ? Taylor expansion around x=0 ...
8
votes
5answers
355 views

An interesting Sum involving Binomial Coefficients

How would you evaluate $$\sum _{ k=1 }^{ n } k\left( \begin{matrix} 2n \\ n+k \end{matrix} \right) $$ I tried using Vandermonde identity but I can't seem to nail it down.
8
votes
3answers
981 views

Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
8
votes
3answers
357 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
8
votes
5answers
398 views

Are there surprisingly identical binomial coefficients?

Suppose $\binom{n}{k}=\binom{n'}{k'}$ with $k \geq 2$, $k' \geq 2$, $n \geq 2k$ and $n' \geq 2k'$. Does it follow that $n=n'$ and $k=k'$? EDIT: Yup, ...
8
votes
3answers
286 views

When are products of binomial coefficients equal?

It's known that $\binom{n}{r} = \binom{n}{s}$ if and only if $r = s$ or $r = n - s$. If $n \neq m$, is it true that $\binom{n}{s} \binom{m}{r} = \binom{n}{k} \binom{m}{\ell}$ if and only if ($s = k$ ...
8
votes
2answers
101 views

Rough bound for sum $\binom{3n}{0}+\binom{3n}{1}+\cdots+\binom{3n}{n-1}$

Is it true that $$\frac{\dbinom{3n}{0}+\dbinom{3n}{1}+\cdots+\dbinom{3n}{n-1}}{2^{3n}}<\frac13$$ for all positive integers $n$? I've plotted the first few values of $n$ and noticed that the ...
8
votes
2answers
227 views

Find the sum of this series :$ \frac{1}{{1!2009!}} + \frac{1}{{3!2007!}} + \cdots + \frac{1}{{1!2009!}}$

Find the sum of this series : $$\sum\limits_{\scriptstyle 1 \leqslant x \leqslant 2009 \atop {\scriptstyle x+y=2010 \atop \scriptstyle {\text{ }}x,y{\text{ odd}} }} {\frac{1}{{x!y!}}} = ...
8
votes
2answers
557 views

Is there a combinatorial way to see the link between the beta and gamma functions?

The Wikipedia page on the beta function gives a simple formula for it in terms of the gamma function. Using that and the fact that $\Gamma(n+1)=n!$, I can prove the following formula: $$ ...
8
votes
3answers
250 views

A peculiar binomial coefficient identity

While inventing exercises for a discrete math text I'm writing I came up with this $$ \binom{\binom{n}{2}}{2}=3\binom{n+1}{4} $$ It's an easy result to prove, but it got me wondering Is this pure ...
8
votes
2answers
2k views

prime numbers in Pascal's triangle

Just wondering about this: Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$? From the first 18 lines it appears that this is ...
8
votes
5answers
9k views

Proving $ { 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} $

How to prove this binomial identity : $$ { 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} $$ The left hand side arises while solving a standard binomial problem the right hand ...
8
votes
3answers
243 views

Putting ${n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ in a closed form

As the title says, I'm trying to transform $\displaystyle{n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ into a closed form. My work: $\displaystyle\left(1 + ...
8
votes
3answers
417 views

Polynomial in $\mathbb{Q}[x]$ sending integers to integers?

We can view the binomial coefficient $\binom{x}{k}$ has a polynomial in $x$ with degree $k$. So taking some $f\in\mathbb{Q}[x]$, why is $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$, precisely when the ...
8
votes
4answers
530 views

Inequality with central binomial coefficients

For every even positive number $N$ we have: $$ {2N \choose N } < 2^N {N \choose N/2 } < 2 {2N \choose N } $$ (Furthermore, $\frac{2^N {N \choose N/2 }}{{2N \choose N }} \to \sqrt{2} $ for ...
8
votes
4answers
154 views

Prove: ${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-…(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$

Prove: $${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-...(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$$ $(2n+1)!!$ is a factorial of odd integers, ...
8
votes
4answers
761 views

Why does this expected value simplify as shown?

I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is: ...