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
2answers
12k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
4
votes
2answers
718 views

Why does $\sum\limits_{i=0}^k {k\choose i}=2^k$ [duplicate]

Possible Duplicate: Proving a special case of the binomial theorem Can anyone explain to me why $$\sum\limits_{i=0}^k {k\choose i}=2^k\,?$$ Thanks in advance
4
votes
4answers
191 views

How do I show that $\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$? [duplicate]

$$\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$$ I know how to "prove" it by interpretation (using the definition of binomial coefficients), but how do I actually prove it?
4
votes
3answers
155 views

Find the limit of $4^n\cdot\binom{2n}{n}/\binom{4n}{2n}$

I am trying to prove that $$f(n)=4^n\frac{\dbinom{2n}{n}}{\dbinom{4n}{2n}}$$ converges as $n\rightarrow\infty$. I have already tried to use the fact that, if $n, k \in\mathbb{N}, n\geq k\geq1,$ then ...
4
votes
2answers
71 views

Binomial Coefficients Combinatorics

For a positive integers n, prove that $$\displaystyle\sum\limits_{v=0}^n \frac{(2n)!}{(v!)^2 ((n-v)!)^2} = \binom{2n}{n}^2.$$ If somebody could please help me with this question, I would greatly ...
4
votes
4answers
394 views

${10 \choose 4}+{11 \choose 4}+{12 \choose 4}+\cdots+{20 \choose 4}$ can be simplified as which of the following?

${10 \choose 4}+{11 \choose 4}+{12 \choose 4}+\cdots+{20 \choose 4}$ can be simplified as ? A. ${21 \choose 5}$ B. ${20 \choose 5}-{11 \choose 4}$ C. ${21 \choose 5}-{10 \choose 5}$ D. ${20 ...
4
votes
3answers
105 views

What is the sum $\sum_{k=0}^{n}k^2\binom{n}{k}$? [duplicate]

What should be the strategy to find $$\sum_{k=0}^{n}k^2\binom{n}{k}$$ Can this be done by making a series of $x$ and integrating?
4
votes
2answers
1k views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
4
votes
3answers
800 views

Binomial Coefficients in the Binomial Theorem - Why Does It Work Question

to keep it simple: Given $(a+b)^3=\binom{3}{0}a^3+\binom{3}{1}a^2b+\binom{3}{2}ab^2+\binom{3}{3}b^3$ Could you please give me an intuitive combinatoric reason to why the binomial coefficients are ...
4
votes
3answers
157 views

Property of a polynomial $f\in\mathbb{Q}[X]$ such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$?

We can always view $\binom{x}{k}$ as a polynomial in $x$ of degree $k$. With this in mind, why is it so that a polynomial $f\in\mathbb{Q}[x]$ is such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$ ...
4
votes
3answers
248 views

Combinatorial proof of $\binom{n}{k} = \binom{n}{n-k}$

How do I prove this combinatorially? $$\displaystyle \binom{n}{k} = \binom{n}{n-k}$$
4
votes
3answers
76 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
5answers
274 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
112 views

Solve for $n$, where $n$ is a positive integer

I have $$ {n \choose 2} = 21 $$ and as the title mentions I have to solve for $n$, but so far all I have managed to get to is $$n^2 -n =42 $$ and from there I'm completely lost. Any hints would ...
4
votes
1answer
237 views

Binomial Summation

The sum $$ 1 + {n \choose 1}\cos \theta + {n \choose 2}\cos 2\theta + \cdots+ {n \choose n}\cos n\theta $$ is? I try to write this as the real part of $(1 + \cos \theta + i\sin \theta)^n$ but then ...
4
votes
3answers
148 views

Find a simple formula for

$$\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+...+\binom{n}{n-1}\binom{n}{n}$$ All I could think of so far is to turn this expression into a sum. But that does not necessarily simplify the ...
4
votes
2answers
3k views

Choosing a 5 member team out of 12 girls and 10 boys

We must choose a 5-member team from 12 girls and 10 boys. How many ways are there to make the choice so that there are no more than 3 boys on the team? The correct answer is $\binom{22}{5} - ...
4
votes
2answers
337 views

Combinatorial Proof for a $ p\mid\binom{p}{k} \ \ \ \ \ 0<k<p$ .

I'm looking for a combinatorial proof to the following statement: $$ p\mid\binom{p}{k} \ \ \ , \ \ 0<k<p \ \ \ \ \ \ \text{and} \ \ p \ \text{is prime}.$$ Thank you.
4
votes
2answers
1k views

Factorial division using Pascal's triangle.

I want to get values of factorial divisions such as 100!/(2!5!60!)(the numbers in the denominator will all be smaller than the numerator, and the sum of the ...
4
votes
2answers
41 views

Trouble understanding how this identity is derived: $\sum_{j=0}^{\infty}\binom{a+j}{j}x^j=(1-x)^{-a-1}$

$$\sum_{j=0}^{\infty}\binom{a+j}{j}x^j=(1-x)^{-a-1}$$ The $-a-1$ is throwing me off. Can anyone help me understand this identity. I have tried letting $m=-a-1$ and then applying the binomial ...
4
votes
3answers
135 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
4
votes
2answers
138 views

What does $\lim \limits_{n\rightarrow \infty }\sum \limits_{k=0}^{n} {n \choose k}^{-1}$ converge to (if it converges)? [duplicate]

How we can show if the sum of $$\lim_{n\rightarrow \infty }\sum_{k=0}^{n} \frac{1}{{n \choose k}}$$ converges and then find the result of the sum if it converges? Thanks for any help.
4
votes
4answers
141 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
447 views

Combinatorial proof for $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$?

I have to prove the following using a combinatorial proof: $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$ Ok, so here is what I have worked out so far: We ...
4
votes
3answers
2k views

Combination problem with constraints

You have four containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, say...70L, 45L, 33L and 11L levels respectively. What is the formula that ...
4
votes
2answers
6k views

Number of even and odd subsets [duplicate]

Suppose we have the following two identities: $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ $\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$ The first says that the number of subsets ...
4
votes
2answers
39 views

Let $f(n)=\sum_{r=0}^{n}\sum_{k=r}^{n}\binom{k}{r}$.If $f(n)=2047,$ then find the value of $n.$

Let $f(n)=\sum_{r=0}^{n}\sum_{k=r}^{n}\binom{k}{r}$.If $f(n)=2047,$ then find the value of $n.$ ...
4
votes
3answers
85 views

How to derive this binomial identity?

I believe the following is an identity (I've tested with a few random $m$ and $n$ values, could be wrong though): $$\sum_{k= 0}^{\infty}{m \choose k}{n \choose k}k=n\binom{m+n-1}{m-1}$$ but I'm not ...
4
votes
2answers
133 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} + ...
4
votes
4answers
198 views

What is the story behind ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$? [duplicate]

By exploring the inductive proof from this question I came to the point where I did not understand this step: $${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$ There is a wikipedia article but ...
4
votes
4answers
84 views

Proof $\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod{p}$

Proof that if $p$ is a prime odd and $k$ is a integer such that $1≤k≤p-1$ , then the binomial coefficient $$\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod p$$ This exercise was on a test and I could ...
4
votes
3answers
671 views

Integral with binomial coefficient

Is it possible to evaluate this integral without using the gamma function $$ \int_0^1 {a \choose b}x^b(1-x)^{a-b} dx$$ It looks a little like part of binomial theorem, but I don't have an idea how to ...
4
votes
4answers
127 views

How can I find $\sum\limits_{n=i+1}^\infty \binom{n-1}{i}\left (\frac{1}{3}\right)^{n}$?

In a probability proof I've arrived at the sum $\sum\limits_{n=i+1}^\infty \binom{n-1}{i} \left(\frac{1}{3}\right)^{n}$ where $i$ is constant. WolframAlpha gives a simple expression for this sum, but ...
4
votes
3answers
523 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
704 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
142 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
561 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
668 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
204 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
473 views

lacunary sum of binomial coefficients

I am sure there must be a known estimate for sums of the form: $$ S_d(n)=\sum_{j=0}^n \binom{dn}{dj} $$ where $d\ge 1$. For $d=1$, the answer is obvious. For $d=2$, the answer is here: Sum with ...
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
2answers
110 views

Solving ${98 \choose 30}+2{97 \choose 30}+3 {96 \choose 30}+…+68{31 \choose 30}={100 \choose q}$ for $q$

${98 \choose 30}+2{97 \choose 30}+3 {96 \choose 30}+...+68{31 \choose 30}={100 \choose q}$ Find the value of $q$? Could someone give me hint as how to solve this question?
4
votes
4answers
167 views

Li Shanlan's combinatorial identities

I am struggling to prove the following combinatorial identities: $$(1)\quad\sum_{r=0}^m \binom{m}{r}\binom{n}{r}\binom{p+r}{m+n} = \binom{p}{m}\binom{p}{n},\quad \forall n\in\mathbb N,p\ge m,n$$ ...
4
votes
3answers
132 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
98 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
144 views

Coefficient of the generating function $G(z)=\frac{1}{1-z-z^2-z^3-z^4}$

I am seeking the coefficient $a_n$ of the generating function $$G(z)=\sum_{k\geq 0} a_k z^k = \frac{1}{1-z-z^2-z^3-z^4}$$ The combinatorial background of this question is to solve the recurrence ...
4
votes
3answers
153 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
111 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
533 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 ...