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)

6
votes
4answers
886 views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
6
votes
6answers
4k views

Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
6
votes
2answers
412 views

Prove the identity $\sum\limits_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m} $

I need to prove $$\sum_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m} $$ using: $$(1-x)^{-m-1} (1-x)^{-q-1} = (1-x)^{-m-q-2} .$$ ok, generating function :$\frac1{(1-x)^{m+1}} = ...
5
votes
3answers
393 views

Dividing factorials is always integer

Is there a simple way to show that $$n!\over r!(n-r)!$$ is always an integer?
5
votes
2answers
333 views

What's the intuition behind this equality involving combinatorics? [duplicate]

What is the intuition behind $$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $$ ? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ ...
4
votes
5answers
250 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
4
votes
4answers
139 views

A binomial inequality with factorial fractions

Prove that $$\left(1+\frac{1}{n}\right)^n<\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{n!}$$ for $n>1 , n \in \mathbb{N}$.
4
votes
3answers
577 views

Alternating sign Vandermonde convolution

The well-known Vandermonde convolution gives us the closed form $\sum_{k=0}^n {r\choose k}{s\choose n-k} = {r+s \choose n}$. For the case $r=s$, it is also known that $\sum_{k=0}^n (-1)^k {r \choose ...
3
votes
2answers
113 views

when is $\frac{1}{n}\binom{n}{r}$ an integer

So I am considering for which values of n is $a_n =\frac{1}{n}\binom{n}{r}$ an integer for all $ 1\leq r \leq n-1 $. The first thing I did was to check the Pascal Triangle. So I guess n has to be ...
3
votes
3answers
93 views

Asymptotic of a sum involving binomial coefficients

Could you help me to find an asymptotic for this sum? $$ \sum_{k=0}^{n - 1} (-1)^k {n \choose k} {3n - k - 1 \choose 2n - k} = {n \choose 0} {3n - 1 \choose 2n} - {n \choose 1} {3n - 2 \choose 2n - ...
3
votes
4answers
253 views

Algebric proof for the identity $n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$

Prove the identity: $$n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$$ I tried using the binomial coefficients identity $2^n = \sum_{k=1}^n {n \choose k}$ but got stuck along the way.
3
votes
5answers
145 views

Calculate $\lim_{n\rightarrow +\infty}\binom{2n} n$

Calculate $$\lim_{n\rightarrow +\infty}\binom{2n} n$$ without use Stirling's Formula. Any suggestions please?
3
votes
3answers
230 views

Stirling Binomial Polynomial

Let $\{\cdot\}$ denote Stirling Numbers of the second kind. Let $(\cdot)$ denote the usual binomial coefficients. It is known that $$\sum_{j=k}^n {n\choose j} \left\{\begin{matrix} j \\ k ...
3
votes
3answers
93 views

Manipulation of a binomial coefficient

In obtaining a formula for the Catalan numbers I have got the expression $-\frac{1}{2}\binom{1/2}{n}(-4)^n$. All my efforts to show that this simplifies to $\frac{1}{n}\binom{2n-2}{n-1}$ have not ...
2
votes
2answers
163 views

Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?

I have the sum $$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$ but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try ...
2
votes
1answer
163 views

Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. ...
2
votes
1answer
510 views

Evaluate $\sum\limits_{k=0}^n \binom{n}{k}$ combinatorially

Please help me to evaluate combinatorially the following sum: $$\sum_{k=0}^n \binom{n}{k}$$ Thank you.
2
votes
4answers
1k views

Show that $\binom{2n}{ n}$ is divisible by 2? [duplicate]

Possible Duplicate: prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer Show that $\binom{2n}{ n}$ is divisible by 2? Any help would be appreciated..
2
votes
1answer
259 views

Question on Inverse Pochhammer Symbol

I struggled quite a while without success, so I highly appreciate if anybody can help me, proving that: $$ \frac{1}{\left(1+1/n \right)^{(M)}}=\sum_{k=0}^M \frac{(-1)^k}{k!(M-k)!(nk+1)}, $$ where ...
2
votes
1answer
330 views

Formula for binomial coefficients

Does someone know, if the subsequent formula holds for $m \ge n \ge i \ge 1$ and if yes, can give a reference. $$\sum_{k=i}^{m-n+i}\binom{k}{i}\binom{m-k}{n-i} = \binom{m+1}{n+1}$$ Thank you very ...
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 ...
7
votes
3answers
173 views

Prove inequality with binomial coefficient: $6 + \frac{4^n}{2 \sqrt{n}} \le \binom{2n}n$

I have to prove inequality, where $n \in N$ $$6 + \frac{4^n}{2 \sqrt{n}} \le {2n \choose n}$$ I have checked and it is true when $n\ge4$, however I have no idea how I should start. Can anyone give a ...
7
votes
4answers
341 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 = ...
6
votes
2answers
202 views

Challenge: How to prove this identity between bi- and trinomial coefficients?

This question is the continuation of its predecessor. Using the convention that trinomial coefficients $$ \binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1! k_2! k_3!} $$ are zero if $k_i<0$ or $\sum_i k_i\neq ...
6
votes
3answers
138 views

Bounds for $\binom{n}{cn}$ with $0 < c < 1$.

Are there really good upper and lower bounds for $\binom{n}{cn}$ when $c$ is a constant $0 < c < 1$? I know that $\left(\frac{1}{c^{cn}}\right) \leq \binom{n}{cn} \leq ...
5
votes
4answers
128 views

Proving $\binom{m}{n} + \binom{m}{n-1} = \binom{m+1}{n}$ algebraically

I am working through the exercises and have spent half a day on one problem so I decided to get some help because I can't figure it out. Show that if $n$ is a positive integer at most equal to $m$, ...
5
votes
4answers
357 views

Combinatorial Proof

I have trouble coming up with combinatorial proofs. How would you justify this equality? $$ n\binom {n-1}{k-1} = k \binom nk $$
5
votes
1answer
725 views

Calculation of the moments using Hypergeometric distribution

Let vector $a\in 2n $ is such that first $l$ of its coordinates are $1$ and the rest are $0$ ($a=(1,\ldots, 1,0, \ldots, 0)$). Let $\pi$ be $k$-th permutation of set $\{1, \ldots, 2n\}$. Define ...
4
votes
4answers
165 views

How to prove that $\sum_{r=0}^n\binom{n}{r}2^r=3^n$

I need help proving that $$\sum_{r=0}^n\binom{n}{r}2^r=3^n$$ I'm thinking this should use the idea that $\binom{n}{r}=\binom{n}{n-r}$ but I'm not sure how to proceed with it. Thanks in advance!
3
votes
2answers
142 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?
3
votes
2answers
2k views

How do I determine the possible number of combinations of two ordered sets?

I'm not quite sure what the mathematical term for what I'm asking is, so let me just describe what I'm trying to figure out. Let's say that I have two ordered sets of numbers $\{1, 2\}$ and $\{3, ...
2
votes
5answers
101 views

Prove $n\binom{p}{n}=p\binom{p-1}{n-1}$

Let $p\in \mathbb{R}$ and $n\in \mathbb{N}$ and $$\binom{p}{n}=\frac{p(p-1)(p-2)...(p-n+1)}{n!}$$ b) Prove $$n\binom{p}{n}=p\binom{p-1}{n-1}$$ Thanks for all the help with a! I definitely understand ...
2
votes
2answers
306 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
2
votes
2answers
159 views

Counting two ways, $\sum \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$

prove by counting two ways: I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for ...
2
votes
1answer
529 views

Proving an identity with a combinatorial proof

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity: $$\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$ The problem is that I ...
2
votes
3answers
2k views

Negative Binomial Coefficients

Is it true that Pascal's Rule holds for binomial coefficients with a negative upper index? With $n = -1$ and $k = 3$, for example, it appears not to hold.
2
votes
1answer
252 views

probability of rolling at least $n$ on $k$ 6-sided dice

Is there a simple form for the probability of rolling at least $n$ on $k$ 6-sided dice? Of course you can do it by recursion (see here). But is there a way to do it with just a few binomial ...
2
votes
1answer
668 views

Evaluate the Binomial Coefficient

Please help me evaluate the following Binomial coefficient using any known properties of Pascal triangle: $$ \binom{52}{4} - \binom{47}{4} + \binom{47}{5} $$
2
votes
3answers
2k views

Proof that binomial coefficient is a natural number [duplicate]

Possible Duplicate: Proof that a Combination is an integer What is the proof that the binomial coefficient is a natural number? $$k\ge0,n\ge k \implies {n \choose k} \in N,$$ I guess ...
1
vote
2answers
129 views

Kolmogorov-Zurbenko filter - Calculation of coefficients

I'm currently researching the Kolmogorov-Zurbenko filter and trying to implement it myself as a way to smooth one-dimensional signal strength values. The basic filter per se is pretty easy to ...
1
vote
1answer
36 views

Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$

Show that for $n \ge 2$, $\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n$ where $r_k = \frac{k^k}{(k-1)^{k-1}}$. This is a generalization of How to prove through induction which asks for a proof ...
1
vote
1answer
41 views

Calculating the sum of a binomial coefficient series

Calculate this: $$\bigl(\begin{smallmatrix} 80 \\0 \end {smallmatrix}\bigr)-\bigl(\begin{smallmatrix} 80 \\1 \end {smallmatrix}\bigr)+\bigl(\begin{smallmatrix} 80 \\2 \end ...
1
vote
1answer
103 views

Binomial Coefficient: monotonically decreasing in this range?

relating to this question, I'd like to ask a further one. Again we have $$f(x)={k-1 \choose x-1} p^x (1-p)^{k-x}$$ We know that this term is maximal for $x=kp$, before increasing, afterwards ...
1
vote
2answers
1k views

Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

I need to find a formula for the total number of ways to distribute $N$ indistinguishable balls into $k$ distinguishable boxes of size $S\leq N$ (the cases with empty boxes are allowed). So I mean ...
1
vote
5answers
3k views

Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$ The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$. Any help?
1
vote
0answers
187 views

how to solve the following expectation? closed-form expression or approximation

Suppose there is a binomial random variable $X\sim B(n-1,p)$,how to solve the following expectation $$E[(1- b^{X})^{m}]$$ where $b\in (0,1]$ and $m\in \mathbb{N} $ are all constants.I have tried my ...
1
vote
1answer
465 views

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

Please provide a combinatorial proof for the following: Prove the identity $$\sum_{i=0}^{k}{m+k-i-1 \choose k-i}{n+i-1 \choose i}={m+n+k-1 \choose k}$$ Hint: use idea of "selection with repetition". ...
1
vote
2answers
672 views

Maximum term of (a + b) ^ n

I would like a demonstration of the fact below. Being given real numbers a and b (nonzero) and a positive integer n, the order p, that occupies the maximum term (in absolute value) of the ...
0
votes
1answer
38 views

Equating coefficients of binomial expansion modulo p

In this answer: http://math.stackexchange.com/a/652909 Ted equates mod $p$ the coefficients of $$\sum_{n=0}^{pa} \binom{pa}{n} x^n$$ and $$\sum_{i=0}^{a} \binom{a}{i} x^{pi}$$ to get that ...
0
votes
3answers
48 views

Proving an inequality involving binomial coefficient

What is the best way of proving inequalities including binomial coefficients in general? Lets look at this example: $$\frac{n^k}{k^k}\leq\binom{n}{k}\leq\frac{n^k}{k!}$$ What I started with is: ...