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)

7
votes
6answers
368 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
4answers
4k views

Derivation of binomial coefficient in binomial theorem.

How was the binomial coefficient of the binomial theorem derived? $$\frac{n!}{k!(n-k)!}$$
7
votes
3answers
2k 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
3answers
515 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
376 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
223 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
752 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
352 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
5answers
7k 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 ...
7
votes
4answers
633 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
366 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
399 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
330 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
3answers
434 views

Some trouble with the induction

Prove, that for any positive integer $n \geqslant 2$ we have the inequality $$ \frac{ 4^n }{ n+1 } < \frac{ (2n)! }{ (n!)^2 }.$$ For $n=2$ the inequality is true. Directly just take and ...
7
votes
3answers
515 views

Find the Pascal's Limit [closed]

Let $P_{n}$ be the product of the numbers in row of Pascal's Triangle. Then evaluate $$ \lim_{n\rightarrow \infty} \dfrac{P_{n-1}\cdot P_{n+1}}{P_{n}^{2}}$$
7
votes
4answers
678 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
5answers
474 views

Choice Problem: choose 5 days in a month, consecutive days are forbidden [duplicate]

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand. Example 3.19. A medical student has to work in a hospital for five days in January. ...
7
votes
4answers
316 views

Truncated alternating binomial sum

It is easily checked that $\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the ...
7
votes
5answers
405 views

The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$

A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
7
votes
4answers
881 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
362 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
215 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
2answers
987 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
249 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
139 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
3answers
148 views

Show that $p \in \left[\frac{4^m}{2\sqrt{m}},\frac{4^m}{\sqrt{2m+1}}\right]$

If the number of ways in which $m$ identical apples can be put in $2m$ boxes, so that no box contains more than one apple, is $p$, prove that $$p \in ...
7
votes
2answers
94 views

Roots of a polynomial whose coefficients are ratios of binomial coefficients

Prove that $\left\{\cot^2\left(\dfrac{k\pi}{2n+1}\right)\right\}_{k=1}^{n}$ are the roots of the equation $$x^n-\dfrac{\dbinom{2n+1}{3}}{\dbinom{2n+1}{1}}x^{n-1} + ...
7
votes
1answer
199 views

Closed-form expression for $\sum_{n=1}^{k} (-1)^{n+1}n^2(n^2-1)\binom{2k}{k-n}$?

Wolframalpha tells me that $$\sum_{n=1}^{k} (-1)^{n+1}n^2(n^2-1)\binom{2k}{k-n}=0$$ for $k>2$ However I have not been able to come up with a proof and I simply don't see how to do it. Does anyone ...
7
votes
2answers
300 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
384 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
366 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} ...
7
votes
2answers
223 views

About one generating function

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
7
votes
2answers
715 views

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
7
votes
2answers
16k views

Negative Exponents in Binomial Theorem

I'm looking at extensions of the binomial formula to negative powers. I've figured out how to do $n \choose k$ when $n < 0 $ and $k \geq 0$: $${n \choose k} = (-1)^k {-n + k - 1 \choose k}$$ So ...
7
votes
3answers
178 views

Show that there are infinitely many integers such that $ \binom{m}{n-1} = \binom{m-1}{n} $

This question comes from the 1st Brazilian's IMO TST of 2004. I have found no solutions of it online, though I have developed one. After getting to $ mn = (m-n)(m-n+1) $, my solution relies on the ...
7
votes
2answers
193 views

Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I ...
7
votes
1answer
233 views

$\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof

Is there a simple combinatorial proof for the following identity? $$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$ where $m,j \geq 0$, $k \geq n \geq 0$.
7
votes
1answer
2k views

Intuition behind negative combinations

Take $\binom{n}{r}$. It denotes how in how many different ways you can choose $r$ elements from a set of $k$ elements. For case $\binom{4}{3}$ which evaluates to $\frac{4!}{3!(4-3)!}=4$, it perfectly ...
7
votes
1answer
318 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
7
votes
2answers
312 views

A binomial coefficient identity?

Suppose $p$, $k$ and $s$ are integers with $s,k \le p$. Consider the following polynomial in $x$ and $y$, $$ \sum_{\ell=0}^k \binom{s}{\ell} \binom{p-s}{k-\ell} x^\ell y^{p-\ell}$$ Does this ...
7
votes
1answer
249 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
7
votes
1answer
180 views

Determining when a certain binomial sum vanishes

Consider the following sum of signed binomial coefficients: $$S_{n,a,p} = \sum_{i \equiv a \mod p} \binom{n}{i}(-1)^i$$ ($n$ is a positive integer, $p$ is an odd prime, $a$ is between $0$ and ...
7
votes
3answers
281 views

Asymptotic difference between a function and its binomial average

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number. Dividing by $2^n$, we ...
7
votes
2answers
251 views

Category of binomial rings

A binomial ring is a commutative ring $R$ such that (1) the additive group of $R$ is torsionfree and (2) $n!$ divides $x(x-1)\dotsc(x-n+1)$ for all $n \in \mathbb{N}$ and $x \in R$. We may then define ...
7
votes
2answers
219 views

Does this really converge to 1/e? (Massaging a sum)

Short version: can we prove that $$\sum_{k=0}^n (-1)^k \binom{n}{k}^2 \frac{k!}{n^{2k}} \to \frac1e$$ as $n \to \infty$? Long version: First, consider $$a_n = \sum_{k=0}^n \frac{(-1)^k}{k!}$$ It is ...
7
votes
5answers
217 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
7
votes
1answer
433 views

Combinatorial Interpretation of Fractional Binomial Coefficients

My question is a bit imprecise - but I hope you like it. I even strongly think it has a proper answer. The binomial coefficient $\binom{\frac{1}{2}}{n}$ is strongly related to Catalan numbers - the ...
7
votes
1answer
329 views

Asymptotics for sum of binomial coefficients from Concrete Mathematics

Concrete Mathematics EXERCISE 9.25: Supposing \[ S_n = \sum_{k=0}^n \binom{3n}k \] Prove that \[ S_n = \binom{3n}{n}\left(2-\frac4n+O\left(\frac1{n^2}\right)\right) \] This sequence also ...
7
votes
1answer
342 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
7
votes
0answers
144 views

Characterization of Sequences with Integral Binomial Coefficients

For any sequence of positive integers $\{ a_i \}_{i \ge 1}$ we can define the generalized binomial coefficients $\binom{n}{k}_{a}$ as follows: $$m!_a = a_1 a_2 \cdots a_m, \binom{n}{k}_a = ...