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)

10
votes
1answer
165 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
1answer
129 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 ...
10
votes
2answers
341 views

Computing the last non-zero digit of ${1027 \choose 41}$?

I am working on the following problem: Let $x_n$ be a sequence of positive odd numbers. If $N$ is the number of ordered pairs $(x_1, x_2, x_3, \dots, x_{42})$ such that $$x_1 + x_2 + x_3 + \dots + ...
10
votes
2answers
240 views

How prove binomial cofficients $\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$

How prove this $$\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$$ This equation How prove it? Thank you I want take this ...
10
votes
2answers
562 views

Techniques for summing ratio of binomial coefficients

There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. ...
10
votes
1answer
376 views

Construction of generating function from identity

I am trying to solve identity involving binomials and Fibonacci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
9
votes
4answers
619 views

Show that $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$

The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one ...
9
votes
3answers
438 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
4answers
478 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
856 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
553 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
990 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
474 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
3answers
187 views

Is there a closed form or approximation to $\sum_{i=0}^n\binom{\binom{n}{i}}{i}$

I tried to calculate the sum $$ \sum_{i=0}^n\binom{\binom{n}{i}}{i} $$ but it seems that all my known methods are poor for this. Not to mention the intimate recursion, that is $$ ...
9
votes
1answer
743 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
344 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
563 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
247 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
318 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
819 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
526 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
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
1answer
467 views

Summation of an Infinite Series: $\sum_{n=1}^\infty \frac{4^{2n}}{n^3 \binom{2n}{n}^2} = 8\pi G-14\zeta(3)$

I am having trouble proving that $$\sum_{n=1}^\infty \frac{4^{2n}}{n^3 \binom{2n}{n}^2} = 8\pi G-14\zeta(3)$$ I know that $$\frac{2x \ \arcsin(x)}{\sqrt{1-x^2}} = \sum_{n=1}^\infty ...
9
votes
4answers
253 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
438 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
102 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
337 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
178 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
278 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
2answers
448 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
187 views

Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$

I found this question in an old problem set. There's no hint or solution mentioned. For $n \geq 3$, prove or disprove the existence of $(x,y,z) \in \mathbb N^3, ...
9
votes
1answer
156 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
0answers
100 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
9
votes
4answers
417 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 ...
8
votes
6answers
425 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
392 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
301 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
5answers
317 views

The $n^{th}$ root of the geometric mean of binomial coefficients.

$\{{C_k^n}\}_{k=0}^n$ are binomial coefficients. $G_n$ is their geometrical mean. Prove $$\lim\limits_{n\to\infty}{G_n}^{1/n}=\sqrt{e}$$
8
votes
6answers
391 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
400 views

Finding coefficient of polynomial?

The coefficient of $x^{12}$ in $(x^3 + x^4 + x^5 + x^6 + …)^3$ is_______? Somewhere it explain as: The expression can be re-written as: $(x^3 (1+ x + x^2 + x^3 + …))^3=x^9(1+(x+x^2+x^3))^3$ ...
8
votes
4answers
243 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
366 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
361 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
1k 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
361 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
401 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
2answers
595 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
290 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$ ...