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)

4
votes
4answers
142 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
2answers
587 views

Limit of alternating sum with binomial coefficient

I need to find a limit, or approximation for $\sum\limits_{k=1}^{n} (-1)^k {n \choose k} \log(a+bk)$ for, say, an $a,b\in (0,10)$. It is not so important what values $a$ and $b$ have. It would be ...
3
votes
2answers
115 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
114 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 - 1}...
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
2answers
53 views

how many terms will there be once you collect terms with equal monomials? What is the sum of all the coefficients?

If you expand $(x_1+x_2+\cdots+x_k)^n$, how many terms will there be once you collect terms with equal monomials? What is the sum of all the coefficients? I'm kind of lost here. This came up with ...
2
votes
3answers
452 views

Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

I need to prove the following: If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$. I did the following steps: \begin{align} \require{...
2
votes
3answers
109 views

Gosper's Identity $\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1 $

The page on Binomial Sums in Wolfram Mathworld http://mathworld.wolfram.com/BinomialSums.html (Equation 69) gives this neat-looking identity due to Gosper (1972): $$\sum_{k=0}^n{n+k\choose k}[x^{n+1}(...
2
votes
1answer
44 views

Number of Elements in a Conjugacy Class of $S_N$ (Derivation)

Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is ...
2
votes
1answer
335 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 ...
2
votes
4answers
138 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
2
votes
3answers
52 views

Simplify triangular sum of triangular numbers: $\sum_{i=1}^{n}(\frac12i(i+1))$

I'd like to simplify this expression, which sums up the first $n$ triangular numbers: $$\sum_{i=1}^{n}(\frac12i(i+1))$$ which is equal to: $$\sum_{i=0}^{n}((n-i)(i+1))$$ Is it even possible without ...
1
vote
2answers
81 views

Prove equality between binomial coefficients.

Using the Binomial theorem, prove that: $$ \binom{m+n}{k}=\sum_{j=0}^k \binom{n}{j}\binom{m}{k-j},\; 0\leq k\leq m+n$$
1
vote
3answers
97 views

Number of terms in the expansion of $\left(1+\frac{1}{x}+\frac{1}{x^2}\right)^n$

Number of terms in the expansion of $$\left(1+\frac{1}{x}+\frac{1}{x^2}\right)^n$$ $\bf{My\; Try::}$ We can write $$\left(1+\frac{1}{x}+\frac{1}{x^2}\right)^n=\frac{1}{x^{2n}}\left(1+x+x^2\right)^n$...
7
votes
4answers
346 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 = \sum\limits_{k=0}^...
7
votes
3answers
184 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
2answers
290 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$.
6
votes
2answers
67 views

Find 2 sums with the binomial newton

Find the sum of: i)$\displaystyle\sum_{k=0}^{n} k^2$ $\left(\begin{array}{c} n\\k\end{array}\right)$ ii) $\displaystyle\sum_{k=1}^{n} \frac{2k+5}{k+1}$$\left(\begin{array}{c} n\\k\end{array}\right)$...
6
votes
3answers
139 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 \left(\frac{e}{c}\right)^...
6
votes
2answers
231 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 ...
5
votes
4answers
376 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
854 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 $$g=\...
5
votes
2answers
360 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$ ...
5
votes
1answer
160 views

Trying to solve the equation $\sum_{i=0}^{t}(-1)^i\binom{m}{i}\binom{n-m}{t-i}=0 $ for non-negative integers $m,n,t$

While considering a previous unanswered question, I started looking for the non-negative integer solutions $ m,n,t , (n\ge m)$ to the equation: $$ S(m,n,t)=\sum_{i=0}^{t}(-1)^i\binom{m}{i}\binom{...
5
votes
4answers
135 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$, ...
4
votes
4answers
174 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
3answers
533 views

A combinatorial proof that the alternating sum of binomial coefficients is zero

I came across the following problem in a book: Give a combinatorial proof of $$ {n \choose 0} + {n \choose 2} + {n \choose 4} + \, \, ... \, = {n \choose 1} + {n \choose 3} + {n \choose 5} + \, \, .....
3
votes
3answers
162 views

Combinatorial proof of an identity with squared binomial coefficients

Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please
3
votes
2answers
64 views

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$, $1 \le n < pq$, are divisible by $pq$? In particular, if $p$ and $q$ are distinct odd primes, and $n$ is even, does $pq \...
3
votes
3answers
246 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 \end{matrix}\...
3
votes
2answers
144 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
5answers
147 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?
2
votes
1answer
262 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
262 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
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
2answers
333 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
5answers
118 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
1answer
164 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
569 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 can'...
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 {smallmatrix}\bigr)-\bigl(\...
1
vote
2answers
197 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
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
3answers
60 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: $$\...
1
vote
2answers
114 views

Proof by induction $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n\cdot 2^{n-1}$ for each natural number $n$ [duplicate]

Prove by induction that $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n\cdot 2^{n-1}$ for each natural number $n$.
0
votes
1answer
104 views

Binomial Expression [duplicate]

Please give me feedback on my answer to this question. Question: For all $ n\geq1:\binom{2n}{0}+\binom{2n}{2}+\binom{2n}{4}+\cdots+\binom{2n}{2k}+\cdots+\binom{2n}{2n} $ is equal to $ \binom{2n}{1}+\...
0
votes
3answers
94 views

Binomial coefficient problem

I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this? I need to write this expression in a more simplified way: $\...
0
votes
1answer
191 views

Have you seen this formula for factorial?

Let $p$ always be a prime. $n! = \prod_{p\leq n}p^{\lfloor \frac{n}{p}\rfloor}$. Then $\binom{n}{r} = \prod_{p\leq r}p^{\lfloor n/p \rfloor -\lfloor (n-r)/p \rfloor - \lfloor r/p \rfloor} \times ...$...
0
votes
1answer
66 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 $$\binom{pa}...
0
votes
2answers
134 views

Revisited: Binomial Theorem: An Inductive Proof

I'm asked to use the fact that $\begin{pmatrix}n\\r\end{pmatrix}+\begin{pmatrix}n\\r-1\end{pmatrix}=\begin{pmatrix}n+1\\r\end{pmatrix}$ to show, by induction, that $$(a+b)^n=\begin{pmatrix}n\\0\end{...
0
votes
3answers
94 views

Another sum involving binomial coefficients.

Let both $a$,$b$ and $\theta$ be real numbers not equal to a negative integer. Let $m$ be a positive integer. I have shown that the following equality holds: \begin{eqnarray} &&S^{a}_{b,\...