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)

11
votes
4answers
299 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
901 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
239 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
197 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
3answers
320 views

Proof of the identity $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Prove the identity: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$
11
votes
2answers
281 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
555 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
3answers
626 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 ...
11
votes
1answer
125 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
314 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
709 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
606 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
269 views

Why, conceptually, is it that $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$? [duplicate]

Why, conceptually, is it that $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}?$$ I know how to prove that this is true, but I don't understand conceptually why it makes sense.
10
votes
4answers
215 views

Inequality $\binom{2n}{n}\leq 4^n$

I would like to prove the following inequality, for $n=0,1,2,...$, $$ \binom{2n}{n}\leq 4^n.$$ I already proved it by induction, and I'm looking for another proof.
10
votes
3answers
400 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}$$
10
votes
3answers
609 views

Binomial Identity $\sum\binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$

I'm looking for a reference with the proof of the following binomial identity: $$\sum_{k=0}^n \binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$$ I've looked in a number of textbooks that have a ...
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
3answers
254 views

How to find sums like $\sum_{k=0}^{39} \binom{200}{5k}$

How do I find sums like these?-- $$S=\displaystyle\sum_{k=0}^{39} \dbinom{200}{5k}$$ that is, when there is a summation of binomial coefficients, but with jumps of some terms..?
10
votes
1answer
444 views

New Year Combinatorics

In the spirit of the festive period and in appreciation of the encouraging response to my X'mas Combinatorics problem posted recently, here's one for the New Year! Express the following as a ...
10
votes
2answers
344 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
1answer
819 views

Sum of product of binomial coefficient

Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$ I tried to use the multinomial theorem, but it doesn't seem applicable.
10
votes
6answers
193 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
3answers
531 views

proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$

I'm looking for a proof of this identity: $$ 1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k} $$ I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum ...
10
votes
2answers
131 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
3answers
415 views

Problem of limit with binomial coefficients

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to ...
10
votes
1answer
225 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
174 views

Interpretation of a combinatorial identity

I am trying to find an combinatorial interpretation for the following combinatorial identity involving iterated binomial coefficients, which appeared in the November 1980 edition of The American Math ...
10
votes
1answer
152 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
0answers
89 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
10
votes
0answers
147 views

Is the given binomial sum almost everywhere negative as $K\to\infty$?

The binomial sum is as follows: $$\mathcal {L}^K(\theta)= \sum_{i=\lceil{K/2}\rceil}^K \binom{K}{i}\theta^i\left((1-\theta)^{K-i}-\frac{1}{2}(1-\theta)^{-K}(1-2\theta)^{K-i}\right)$$ which can also ...
9
votes
6answers
332 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 ...
9
votes
5answers
461 views

factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

The successive difference of powers of integers leads to factorial of that power. I think this is the formula $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$ But I found no proof on internet. Please ...
9
votes
3answers
831 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
466 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
2answers
448 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
497 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
338 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
4answers
241 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
3answers
591 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
4answers
243 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
78 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
136 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
2answers
476 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
2answers
400 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
194 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
2answers
263 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
211 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
261 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
102 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
146 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 ...