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
3answers
504 views

General Leibniz rule for triple products

I have a question regarding the General Leibniz rule which is the rule for the $n^{th}$ derivative of a product and reads: $$ (f g)^{(n)}=\sum_{k=0}^{n} {n \choose k} \,f^{(k)} g^{(n-k)}. $$ ...
4
votes
3answers
662 views

Evaluate a sum with binomial coefficients: $\sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$

$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$ I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$ ...
4
votes
2answers
141 views

Expression for power of a natural number in terms of binomial coefficients

Is there a general expression for the pth power of a natural number k in terms of binomial coefficients? I found this identity in a high-school text, which was obtained by simply equating ...
4
votes
2answers
522 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
4
votes
2answers
606 views

No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the ...
4
votes
2answers
201 views

Why does $\binom{10}{7} = \frac{10!}{(10-7)!7!}$

We just learned that: $\dbinom{10}{7}= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}$, so that: If you throw a dice 10 ...
4
votes
2answers
112 views

Binomials in associative algebras

Given any associative algebra $A$ over a field of characteristic zero, $x\in A$ and $k\in \mathbb Z_+$, set $\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}$. It is not hard to see that is is still in ...
4
votes
3answers
134 views

$N^L$ vs. ${N+L\choose N}$

Any ideas on finding a good estimate/approximation for $A/B$ where $A = N^L$ and $B = {N+L\choose N}$?
4
votes
3answers
68 views

Find the sum of the $\sum_{m=k}^{+\infty}\binom{m}{k}(1-p)^k\cdot p^{m-k}$

Let $0<p<1$,Find the sum $$\sum_{m=k}^{+\infty}\binom{m}{k}(1-p)^k\cdot p^{m-k}$$
4
votes
3answers
117 views

Is $72!/36! -1$ divisible by 73?

Is $\frac{72!}{36!}-1$ divisible by the number 73? I am not getting a clue in which direction should I go, though I did small amount of work by converting the above expression in the below given form ...
4
votes
1answer
92 views

Find all natural solutions for $\binom mn=1984$

Find all positive integers $m$ and $n$ such that $${m \choose n}= 1984$$ My approach: It is easy to define $m=1984$ and $n=1$ or $1983$. But how to show that there are no other solutions or, if ...
4
votes
3answers
152 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 ...
4
votes
2answers
95 views

Multiplication Principle and Inclusion-Exclusion: $2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}$

I began to compose an unnecessarily complicated answer to this question: If we had 25 people all who have 2 different balls, how would you work out how many combinations there would be if we want ...
4
votes
3answers
503 views

Number of binary strings with $n$ ones and $m$ zeros

$f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros. Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$ I got to the point that: $$\sum_{a=0}^n ...
4
votes
3answers
321 views

Proving that $n\mid(nCr)$ for all $r$ ($1 \leq r \leq n-1$), only if $n$ is prime

I'm trying to prove that $n\mid(nCr)$ for all $r$ ($1 \leq r \leq n-1$) if and only if $n$ is prime. Now proving that if $n$ is prime then $n\mid(nCr)$ is pretty easy, but how would you go about ...
4
votes
3answers
131 views

Combinatorial interpretation of this number?

It is straightforward to show that if $m,n\in\mathbb{Z}$ and $m\geq n$, then $$m\mid \gcd(m, n)\binom{m}{n}.$$ I'm trying to find a combinatorial interpretation of this fact, but I can't seem to come ...
4
votes
3answers
136 views

Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$ I got this far before I got stuck: $\begin{eqnarray*} ...
4
votes
2answers
2k views

Conceptual proof that $p\choose k$ ($1 < k < p$) is divisible by $p$ when $p$ is prime? (I.e., no equations).

If $n,k\in \mathbf{N}$, then one defines $n\choose k$ to be the number of ways to choose $k$ elements from a set of size $n$. One can then show (by a combinatorial argument) that $${n\choose k} = ...
4
votes
5answers
221 views

The sum of the coefficients of $x^3$ in $(1-\frac{x}{2}+\frac{1}{\sqrt x})^8$

I know how to solve such questions when it's like $(x+y)^n$ but I'm not sure about this one: In $(1-\frac{x}{2}+\frac{1}{\sqrt x})^8$, What's the sum of the coefficients of $x^3$?
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 ...
4
votes
1answer
585 views

Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.
4
votes
2answers
234 views

Proof of $(2n)!/(n!)^2\le2^{2n}$ by mathematical induction?

How do I approach this problem using mathematical induction? $$\frac{(2n)!}{(n!)^2} \leq 2^{2n}$$
4
votes
4answers
205 views

Expansion concerning the binomial theorem

The question goes: Expand $(1-2x)^{1/2}-(1-3x)^{2/3}$ as far as the 4th term. Ans: $x + x^2/2 + 5x^3/6 + 41x^4/24$ How should I do it?
4
votes
1answer
111 views

Prove a theorem in combinatorics

I want to show that for $k=1,...,(n-1)$ we have : $\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}$ I have used induction on $k$, but I have not deduced the above relation.
4
votes
2answers
84 views

Is there a simpler way to compute this sum?

For any given positive integers $m$, $n$ and $q$, such that $m\leq n$ the following sum $$S_p= \sum_{p=0}^m(-1)^{p+q} \binom mp \binom mq \binom np \binom nq\frac{p! q! (m+n-p-q)!}{m! n!}$$ is equal ...
4
votes
2answers
126 views

Evaluate the summation involving binomials.

$\sum _{ i=0 }^{ 100 }{\binom{k}{i}}*{\binom{M-k}{100-i}*\frac{k-i}{M-100}}/{\binom{M}{100}}$ I wrote the first few terms but couldn't find any pattern and how to club the terms. Help.
4
votes
2answers
108 views

Show $\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$

As the title says... We are asked to show that $$\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$$ I tried with induction, but that seems to never work with these kind of questions. We need ...
4
votes
1answer
244 views

Proving $\binom{2n}{n}\ge\frac{2^{2n-1}}{\sqrt{n}}$

Prove that $$\binom{2n}{n}\ge\dfrac{2^{2n-1}}{\sqrt{n}}$$ By the way: I have see $$\binom{2n}{n}\ge\dfrac{4^n}{2n}=\dfrac{2^{2n-1}}{n}$$ proof: Applying the binomial theorem ...
4
votes
2answers
372 views

Compact form of sum (binomial coefficients)

Find compact formula of the following sum: $$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} $$ Could you give me any HINT how to start it? I've tried this way: $$ ...
4
votes
1answer
201 views

Primes Not Dividing $\binom{2n}{n}$

Let $n \geq 3$, show ${2n \choose n}$ is not divisible by $p$ for all primes $\frac{2n}{3} <p\leq n$ Note: This fact along with other facts about ${2n \choose n}$ are used in a proof of Bertrand's ...
4
votes
2answers
261 views

Binomial division

Looks very easy, but I can't make it: $s \geq 2$ and $w \geq 2$ are prime numbers. $k$ is a natural number and $k \leq \min \{s,w \}$ Show that $\binom{s+w}{k}-\binom{w}{k} - \binom{s}{k}$ can be ...
4
votes
2answers
2k views

How can I determine asymptotic growth of binomial coefficients?

Say I have a binomial coefficient $y=\binom{5n+3}{n+2}$ or $y=\binom{n^2+4}{3n}$ something of the sorts in terms of the variable $n$. How can I determine $f$ so that $y = O(f)$? Is there a general ...
4
votes
2answers
61 views

If $n$ is a product of primes, what is the number of divisors?

Let $n=p_1p_2...p_k$ Then the number of divisors is what? I assumed it was $1+ \binom k1+ \binom k2 + \binom k3 + ... + \binom kk=2^k$ Is this correct? Prove that the number of divisors is odd ...
4
votes
1answer
62 views

Prove $\sum_{k=0}^n\binom{2n+1}{2k}=4^n$

I once had to show that $\cos(x)\sin(x)=\frac{1}{2}\sin(2x)$ using the Cauchy product and relied on $$\sum_{k=0}^n\binom{2n+1}{2k}=4^n.$$ However I never came up with a proof why this is true - is ...
4
votes
5answers
280 views

Binomial Coefficients Proof: $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

Prove that $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$. I am trying to prove this by induction. I am having some difficulty after the induction step. Here is what I have so far: I start with ...
4
votes
2answers
139 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
4
votes
2answers
130 views

Evaluate $\sum\limits_{k=2}^n \frac{n!}{(n-k)!(k-2)!} $

Question is to Evaluate $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!} $$ What i have done so far is $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n \frac{(n-2)!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n ...
4
votes
1answer
162 views

Simplify $\sum_{k=0}^n \frac{1}{k!(n-k!)}.$

Is there a way to simplify the expression $$\sum_{k=0}^n \frac{1}{k!(n-k)!}?$$ This came up when I was trying to determine $\mathbb{P}(X+Y =r)$ given a joint mass probability $$m_{X,Y}(j,k) = ...
4
votes
6answers
102 views

Is $\sum_{i=1}^{n-1}i=\binom{n}{2}$?

How can I show that $$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$ This is what I have tried, but I do not know if it is correct: Proof. Let $n=2$. Then, $$ \begin{align} \sum_{i=1}^{1}i&=1\text{, ...
4
votes
3answers
2k views

Distributing identical objects to identical boxes

We have 6 identical things to be distributed in 4 identical boxes such that empty boxes are allowed the find the number of ways to distribute the things ?
4
votes
1answer
240 views

How do i reduce this expression of binomial coefficients

I was solving a problem and am stuck with this expression. Any leads on how can I simplify this expression? $$\frac{{\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} ...
4
votes
3answers
506 views

Combinatorial Proof Of Binomial Double Counting

Let $a$, $b$, $c$ and $n$ be non-negative integers. By counting the number of committees consisting of $n$ sentient beings that can be chosen from a pool of $a$ kittens, $b$ crocodiles and $c$ emus ...
4
votes
3answers
2k views

Using Binomial Theorem to prove identity

I need to prove the following using the binomial theorem $${n \choose k} = {n-2 \choose k} + 2{n-2 \choose k-1} + {n-2 \choose k-2}$$ The binomial theorem states $$(1+x)^n = \sum_{k=0}^n {n \choose ...
4
votes
2answers
512 views

Algebraic proof of a binomial sum identity.

I came across this identity when working with energy partitions of Einstein solids. I have a combinatorial proof, but I'm wondering if there exists an algebraic proof. $$\sum_{q=0}^N\binom{m + q - ...
4
votes
2answers
600 views

Proving ${p-1 \choose k}\equiv (-1)^{k}\pmod{p}: p \in \mathbb{P}$ [duplicate]

Possible Duplicate: Prove $\binom{p-1}{k} \equiv (-1)^k\pmod p$ The question is as follows: Let $p$ be prime. Show that ${p \choose k}\bmod{p}=0$, for $0 \lt k \lt p,\space ...
4
votes
2answers
1k views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$ [duplicate]

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
4
votes
1answer
175 views

Derive maximal sum of binomial terms

How to determine a positive value of variable $m$, so that the following formula is maximized. $$\frac{(1-q)^m}{\sum_{x=m/c}^{m}{\binom{m}{x} (1-q)^{m-x} q^x}}$$ where $1<c<m$, $0<q<1$, ...
4
votes
1answer
80 views

Series with a reciprocal of the central binomial coefficient

How can we prove the following identities $$\sum_{n=1}^\infty n^{-3}{\binom{2n}n}^{-1}=\pi\operatorname{Cl}_2\left(\frac{2\pi}{3}\right)-\frac{4}{3}\zeta(3)\tag{1}$$ $$\sum_{n=1}^\infty ...
4
votes
2answers
70 views

What does ${50}\choose{4}$ mean in statistics?

I have a test tomorrow in statistics and was wondering what the following means? $$\binom{50}{4}$$ My professor along with most of my classmates have a calculator they can just plug that into. The ...
4
votes
4answers
55 views

binomials product alternating sum calculation

I need to somehow prove that $\sum\limits_{k = 0}^{n - 1} {n \choose k} {3 n - k - 1 \choose 2 n - k}(-1)^k = (-1)^{n + 1} {2 n - 1 \choose n}$. I didn't manage to do it using induction or any ...