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)

8
votes
2answers
690 views

Binomial coefficients: how to prove an inequality on the $p$-adic valuation?

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used: $$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln ...
8
votes
1answer
390 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?
8
votes
2answers
200 views

Ordinary generating function for $\binom{3n}{n}$

The ordinary generating function for the central binomial coefficients, that is, $$\displaystyle \sum_{n=0}^{\infty} \binom{2n}{n} x^{n} = \frac{1}{\sqrt{1-4x}}$$ follows from the generalized ...
8
votes
4answers
240 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 ...
8
votes
1answer
291 views

Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$. LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset. RHS: We are ...
8
votes
3answers
340 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 ...
8
votes
3answers
123 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. ...
8
votes
1answer
408 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 ...
8
votes
1answer
284 views

Smallest constant in exponent so that limit of sum is $0$

I am trying to work out the smallest constant $c>0$ so that $$\lim_{n \to \infty} \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}} =0 .$$ ...
8
votes
3answers
173 views

How can we find the gcd for elements (binomial coefficient)?

$\gcd\left(\binom{2n}1,\binom{2n}3,\binom{2n}5,\ldots,\binom{2n}{2n-1}\right)$ i want to know what is specialty of such a series.I am not able to generalize the problem solution.Is there any rule for ...
8
votes
2answers
273 views

Binomial identity

I'd like to get a hint to prove the following identity: $$\tag{1}\sum_{\nu}(-1)^{\nu}\displaystyle \binom{a}{\nu}\binom{n-\nu}{r}=\binom{n-a}{n-r} .$$ The original statement reads "By specialization ...
8
votes
2answers
358 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 ...
8
votes
2answers
265 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 + ...
8
votes
2answers
191 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}.$$
8
votes
1answer
192 views

Evaluate $\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$

Evaluate $$\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$$ I don't understand where to start. Please help.
8
votes
2answers
173 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 ...
8
votes
1answer
344 views

Derivation of bound on expression involving binomial coefficient from Erdős and Rényi 1959

I'm in the process of working through Erdős and Rényi's 1959 article "On Random Graphs I". In the proof of the first Lemma, equation 14 gives a bound on an expression involving several binomial ...
8
votes
1answer
428 views

$\binom{n}{k} : \binom{n}{k+1} : \binom{n}{k+2} = a : b : c$

It is a rather surprising fact (to me, at least) that $\displaystyle \binom{14}{4} = 1001$; $\displaystyle \binom{14}{5} = 2002$; $\displaystyle \binom{14}{6} = 3003$. Actually, this is the only ...
8
votes
2answers
117 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$ ...
7
votes
10answers
2k views

How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?

I am trying to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$ but am not able to think something except induction,which is of-course not necessary (I think) here, so I am ...
7
votes
7answers
753 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 ...
7
votes
2answers
718 views

Finding $\lim\limits_{n \to \infty} \sum\limits_{k=0}^n { n \choose k}^{-1}$

We know that $$ 2^n= (1+1)^n = \sum_{k=0}^n {n \choose k}$$ I was asked to solve this limit, $$\lim_{n \to \infty} \ \sum_{k=0}^n {n \choose k}^{-1}=? \quad \text{for} \ n \geq 1$$
7
votes
5answers
293 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}$$
7
votes
6answers
343 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 ...
7
votes
6answers
260 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 ...
7
votes
3answers
1k views

Proof of a combinatorial identity: $\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? ...
7
votes
4answers
133 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 ...
7
votes
4answers
470 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 ...
7
votes
3answers
479 views

Hard elementary combinatorics problem

How does one compute (without brute force) the smallest integer $n$ such that $\binom{2n}{1}(-3)^0 + \binom{2n}{3}(-3)^1 + \binom{2n}{5}(-3)^2 + \cdots + \binom{2n}{2n-1}(-3)^{(n-1)} = 0$?
7
votes
5answers
355 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, ...
7
votes
2answers
211 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!}}} = ...
7
votes
3answers
687 views

Summation Identity: $\sum_{i=1}^ni^3 = \left( \frac{n(n+1)}{2} \right)^2$

I have to prove: $$\sum\limits_{i = 1}^n i^3 = \Bigg( \frac{n(n+1)}{2}\Bigg)^2$$ Using the following: $$n^3 = 6 {n \choose 3} + 6 {n \choose 2} + n \quad \forall n \in \mathbb{N}$$ My work is that ...
7
votes
2answers
344 views

Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$

I need to estimate the asymptotics of $$\sum_{k=0}^{n} {\binom n k}^a, \quad a>2, \quad a \in \mathbb{N}$$ In particular, I'm pretty much interested in $a=4$ case, but if the general solution ...
7
votes
4answers
538 views

Find closed form solution using generation function for the binomial coefficients

I don't have any idea how to start this problem. Could you give a hint? Find closed form solution using generation function for the binomial coefficients: $$a_n:=\sum_{k=0}^{n}\binom{n}{k}^2(-1)^k$$ ...
7
votes
4answers
360 views

Showing that $\lceil (\sqrt{3} + 1)^{2n} \rceil$ is divisible by $2^{n+1}$.

I have a question which has fluxommed me and my pals for the past few days. Any help or solution is welcome Show using Binomial theorem that the integer just after $(3^{1/2} + 1)^{2n}$ is divisble ...
7
votes
4answers
316 views

Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$ I know that $$2^n = ...
7
votes
4answers
335 views

The binomial formula and the value of 0^0

Here is the text from Knuth's The Art of computer programming, 1.2.6 F formula 14: Knuth doesn't give the proof of the statement. So, I tried to write it myself. To make binomial formula equal to ...
7
votes
4answers
437 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 ...
7
votes
4answers
602 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: ...
7
votes
4answers
794 views

partial sum involving factorials

Here is an interesting series I ran across. It is a binomial-type identity. $\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}}{(n-k)!}=4^{n}\cdot n!$ I tried all sorts of playing around, ...
7
votes
3answers
348 views

Yet another sum involving binomial coefficients

Let $k,p$ be positive integers. Is there a closed form for the sums $$\sum_{i=0}^{p} \binom{k}{i} \binom{k+p-i}{p-i}\text{, or}$$ $$\sum_{i=0}^{p} \binom{k-1}{i} \binom{k+p-i}{p-i}\text{?}$$ ...
7
votes
3answers
210 views

Combinatorics question: Show divisibility

Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$. How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product ...
7
votes
4answers
160 views

How prove this inequality $(1+\frac{1}{16})^{16}<\frac{8}{3}$

show that $$(1+\dfrac{1}{16})^{16}<\dfrac{8}{3}$$ it's well know that $$(1+\dfrac{1}{n})^n<e$$ so $$(1+\dfrac{1}{16})^{16}<e$$ But I found this $e=2.718>\dfrac{8}{3}=2.6666\cdots$ ...
7
votes
2answers
869 views

Squared binomial coefficient

I've got the following finite sum: $s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}^2p^k$ (esp. if $p$ is a function of $n$, like $p=\frac1{n}$), which can be rewritten as ...
7
votes
2answers
248 views

Expansion of $ (a_1 + a_2 + \cdots + a_k)^n $

Is there an expansion for the following summation? $$ (a_1 + a_2 + \cdots + a_k)^n $$
7
votes
3answers
132 views

How to prove the following limit: $\lim_{n \to +\infty} 4^n\left[\sum_{k=0}^n (-1)^k{n\choose k}\ln (n+k)\right]=0$?

How to prove the following limit: $$\lim_{n \to +\infty} 4^n\left[\sum_{k=0}^n (-1)^k{n\choose k}\ln (n+k)\right]=0?$$
7
votes
2answers
279 views

Combinatorial argument for the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$

I am looking for the combinatorial argument for the identity: \begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1} \end{equation} This is easy to show algebraically as: \begin{equation} \binom{n}{k} ...
7
votes
2answers
359 views

A Curious Binomial Sum Identity without Calculus of Finite Differences

Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$, \begin{align} \binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} ...
7
votes
2answers
331 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
7
votes
2answers
332 views

Simplify $\sum_{k=1}^{n} {k\choose m} {k}$

$\sum_{k=1}^{n} {k\choose m} {k}$ I have tried to expand it, but the m is pretty annoying. Any ideas to get rid of the summation and give a simple formula? There is a part before $\sum_{k=1}^{n} ...