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)

5
votes
2answers
330 views

Sum of Binomial coefficients identity

I am trying to find an exact formula for the following: $\sum\limits_{i=0}^{n}{\binom{2n}{n-i}\frac{2i^2+i}{n+i+1}}$ I don't think this should be too bad with a rearrangement of terms, but I keep ...
4
votes
3answers
408 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
2answers
224 views

Prove $3^n = \sum_{0 \leq i \leq j \leq n} $ $ n \choose i$ $ i \choose j$

How to prove $3^n = \sum_{0 \leq j \leq i \leq n} $ $ n \choose i$ $ i \choose j$ using $3^n = \sum_{0 \leq i \leq n} 2^i$ $n \choose i$
0
votes
1answer
75 views

Binomial coefficient identity

Is there an identity $\sum_{r=0}^{l-1-p} \binom {r}{p} = \binom{l}{p+1}$ ? I need a proof for this, if it holds. For $l=2$ I can see that it is true.
1
vote
2answers
50 views

Proof that $\lim_{n\rightarrow\infty}\frac{n^\alpha}{(1+p)^n}=0$ from Rudin's Principles of Mathematical Analysis, involving the binomial theorem

We are showing that when $\alpha$ and $p$ are real and $p>0$ then $$\lim_{n\rightarrow\infty}\frac{n^\alpha}{(1+p)^n}=0$$ Proof. Let $k$ be an integer such that $k>0$, $k>\alpha$. Then for ...
0
votes
2answers
50 views

Polynomial of degree 2: what happens when variable triples?

Let p(x,y,z) be a homogeneous polynomial of degree 2: if p(2,3,4) = 10, what is p(6,9,12)?
9
votes
4answers
300 views

Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i ...
1
vote
3answers
9k views

Number of subsets of a set having r elements

We have studied the standard way of ascertaining the total number of subsets of a set by using the concept of combinations ( or binomial coeffecients ). I came across an alternate derivation for this ...
7
votes
1answer
2k views

Asymptotics of binomial coefficients and the entropy function

I found a question while I was trying to practice Combinatorics and Probabilistic methods.I tried to solve it with no success.. this is the question: Use the Stirling approximation of the ...
2
votes
2answers
280 views

Binomial theorem - Positive integers solution

I'm having the following assignment: For which positive integer $n$ will the equations $$ x_1 + x_2 + x_3 + \ldots + x_{19} = n \tag{1}$$ $$ y_1 + y_2 + y_3 + \ldots + y_{64} = n \tag{2}$$ have the ...
6
votes
1answer
148 views

Product of binomial coefficient as a basis

I am stuck with the following problem. Every polynomial of degree $d$ can be expressed as $$ p(x) = p_d \binom{x}{d}+ p_{d-1}\binom{x}{d-1} + \cdots + p_0 \binom{x}{0} $$ What is the ...
2
votes
1answer
154 views

Basic Binomial Coefficient Manipulation

Could someone help me manipulate this sum? I need to be able to extract the coefficient of $x^{n-1}$ in the following: $\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{n-1}{i}\binom{n+j-1}{j}x^{i+2j}$. ...
0
votes
1answer
73 views

How did my textbook conclude this proof?

http://i.imgur.com/goUlA.png At the very last step, highlighted in red, it states that if this, then that sort of, and I'm not sure how those comparisons explain the issue of proving Pascal's ...
0
votes
1answer
105 views

Could anyone explain how my textbook did this simplification?

The book is talking about proving Pascal's triangle increases until the middle, until which point it decreases. Theorem 4.2 refers to the Multiplicative formula I just don't understand how that ...
18
votes
6answers
2k views

Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: ...
0
votes
1answer
185 views

Limit with binomial coefficients

I am trying to compute the following limit (k is a fixed constant): $$ \lim_{n\to\infty} \frac{ {n/2 - 1\choose(k-1)/2} {n/2 \choose (k-1)/2} }{n-1 \choose k-1} $$ I expanded the binomial coefficient ...
0
votes
2answers
83 views

Inequality with binomial coefficients

Let $n, l \in \mathbb{N}, l\leq n$ be fixed. Let $k\in \mathbb{N}$ with $0 \leq k \leq l$. How to show the following? $$ {2n-l\choose n-k}\leq {2n-l \choose \frac{2n-l}{2}} $$
3
votes
3answers
126 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*} ...
0
votes
3answers
121 views

Binomial sum of a sequence

I have the following sequence: $$ \sum\limits_{k=1}^n k\binom{n-1}{k-1} $$ What is the sum of this sequence.
0
votes
0answers
87 views

Finding a bound for a function involving binomial coefficients

Help me please with the following question: Let $n \in N$ be fixed. I would like to find an upper and lower bound for the following function: $$ f(x)={2n-x \choose n}+{x \choose 2}{2n-x \choose ...
12
votes
4answers
4k views

Expected Value of a Binomial distribution?

If $\mathrm P(X=k)=\binom nkp^k(1-p)^{n-k}$ for a binomial distribution, then from the definition of the expected value $$\mathrm E(X) = \sum^n_{k=0}k\mathrm P(X=k)=\sum^n_{k=0}k\binom ...
4
votes
1answer
211 views

Computing a finite binomial sum

I want to compute $$S(n,m,a)=\sum_{k=0}^{n}k^{m}\cdot\binom{n}{k}\cdot a^k.$$ With $n,m\in\mathbb N$, $a\neq0$ and $S(n,0,a)=(a+1)^n$. What I have found already: I don't see any other options then ...
4
votes
1answer
1k views

Binomial coefficient modulo prime power

I am trying to understand how to find binomial coefficients modulo a power of a prime. I am reading the paper by Andrew Granville for this. But I am unable to understand it completely. More ...
3
votes
2answers
59 views

Proving the binomial coefficient identity $\binom{~s + t~ }{s} = \prod_{i=1}^s \prod_{j=1}^t \frac{i + j}{i + j - 1}$

I tried expanding the factorial, but I do not know how to finish the proof. \begin{eqnarray*} \binom{~s + t~ }{s} & = & \frac{(s+t)!}{s! ~ t!}\\ & = & \frac{(s+t)(s+t-1) \cdots ...
0
votes
4answers
115 views

Identity in surjective functions from N to X, up to a permutation of N

I'm studying the combinatorics "twelvefold way", and found an identity that cannot explain myself. The case, $$ {x-1 \choose b-1} $$ as far as I understand is derived the following way: $$ {(x-b)+b-1 ...
2
votes
4answers
283 views

Comparing Two Sums with Binomial Coefficients

How do I use pascals identity: $${2n\choose 2k}={2n-1\choose 2k}+{2n-1\choose 2k-1}$$ to prove that $$\displaystyle\sum_{k=0}^{n}{2n\choose 2k}=\displaystyle\sum_{k=0}^{2n-1}{2n-1\choose k}$$
1
vote
1answer
340 views

permutations and the binomial coefficient

I have seen several times the use of "n choose k" in the left side of the permutations formula. However, this expression is usually referred to be used with combinations. Not that this change when or ...
5
votes
4answers
420 views

problem with proving a property of $n\choose k$

today, at college, we had the following definition of $n\choose k$: For any set $S=\{a_1,\ldots,a_n\}$ containing n elements, the number of distinct k-element subsets of it that can be formed is ...
1
vote
0answers
107 views

Recognizing binomial mixtures

I'd like to know a procedure to recognize whether a given probability distribution over outcomes $\{0, \dots, n\}$ can be expressed as a mixture of $n$-trial binomial distributions with different ...
5
votes
4answers
182 views

Proving a binomial sum with simple result

In deriving a formula I've come up with an expression that I need to prove, specifically: $$(-1)^n = \sum_{j=1}^n (-1)^j \binom{n+1}{j+1} j^n$$ This seems remarkably simple to me, and considering ...
5
votes
2answers
75 views

Combinatorial identity related to the volume of a ball in $\mathbb{R}^{2k+1}$

Calculating the volume of a ball in $\mathbb{R}^{2k+1}$ in two different ways gives us the following formula: $$\sum_{i=0}^k {k \choose i} \frac{(-1)^i}{2i+1} = \frac{(k!)^2 2^{2k}}{(2k+1)!}$$ Is ...
6
votes
1answer
428 views

Vandermonde's-like identity

The Vandermonde's identity gives $$\sum_{k=0}^r \binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.$$ Here is an example of Vandermonde's-like identity: For all $0 \le m \le n$, $$\sum_{k=0}^{2m} ...
0
votes
1answer
29 views

What type of question should we use $\binom{n + k - 1}{k - 1}$ and others

I know there are some questions with solutions of the form $\binom{n + k - 1}{k - 1}$ There are also questions with solution of the form $\binom{n + k - 1}{k}$ and there are questions with ...
1
vote
2answers
145 views

Any way to simplify $\binom{n-x}{k} / \binom{n}{k}\, $?

I tried Wolfram but it just gave me the same thing. I feel like there should be a way to process this. Any thoughts?
0
votes
2answers
67 views

Coefficent of x^8 in a bionomial theorem

How would one go about solving this? This is where i am stuck I am not even sure if I am on the right track, as you can that this is have to use nCr concept (Pascals triangle I believe) here
1
vote
4answers
53 views

Coefficent of an equation

I am suppose to find the coefficent of x^2 in this equation after doing the calculation I ended up with this but that is the wrong answer what is that I am missing?
4
votes
4answers
2k views

Proving q-binomial identities

I was wondering if anyone could show me how to prove q-binomial identities? I do not have a single example in my notes, and I can't seem to find any online. For example, consider: ${a + 1 + b \brack ...
0
votes
1answer
76 views

Binomial distribution with a given probability

Been working on this problem for quite some time, it has to do with binomial distribution but i'm lost from there. The answers to the questions were given as well but I have yet to recreate their ...
8
votes
4answers
500 views

Show that $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$

The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one ...
0
votes
2answers
1k views

Calculate reciprocal square root via binomial expansion

I have to use a binomial expansion to evaluate $1/\sqrt{4.2}$ to $5$ decimal places. The answer from a calculator is $0.48795$ but I get $0.48202$, so I'm doing something wrong. I've also checked my ...
1
vote
0answers
32 views

For $X \sim \mathrm{Binomial}(n,\frac{1}{2})$ does there exist $a,b,c,Y$ s.t. $\Pr[X=x]\Pr[X \le x] \leq a\Pr[Y=bx+c]$?

I need to upper bound some complicated expressions involving binomial distributions: Let $X \sim \mathrm{Binomial}(n,\frac{1}{2})$. I want to find $a,b,c,m$ such that for $Y \sim ...
1
vote
1answer
316 views

Asymptotic for binomial coefficient with square root

I'm looking for asymptotic estimate for the binomial coefficient: $$ \ln{\binom{n}{[\sqrt{n}]}} $$ I assume Stirling's approximation can help, but I'm not sure I will get any good estimation with this ...
5
votes
3answers
234 views

How to understand this combinatorially: $\sum^{2k}_{i=0} \binom{4k}{2i} (-1)^{i}=2^{2k}(-1)^{k}$

The TAs in my department are stuck in assisting an undergraduate with the following problem: $$\sum^{2k}_{i=0} C^{4k}_{2i}(-1)^{i}=2^{2k}(-1)^{k}.$$ We tried to solve this via induction (obviously ...
1
vote
1answer
344 views

How to find the numbers that sum up to a given number?

I have a list of numbers, finite, about 50 and I want to know which permutations with subsets of that set sum up to a given number. I found a formula for the number of ways but I don't know how to ...
0
votes
1answer
448 views

Proving Binomial Identities Using Bijections To Lattice Paths

How can I derive a bijection to show that the following equality holds? $2\displaystyle\sum\limits_{j=0}^{n-1} \binom{n-1+j}{j} = \binom{2n}{n}$ In class, we've been deriving bijections using ...
2
votes
1answer
100 views

What is the coefficient of $z^k$ in ${z+n-1 \choose n}$ for $1 \leq k \leq n$?

What is the coefficient of $z^k$ in ${z+n-1 \choose n}$ for $1 \leq k \leq n$? Thanks. I'm currently looking into Stirling numbers of the first kind, as it seems there is a connection.
2
votes
1answer
85 views

Wellner Inequality

Working on an exercise from Shorack's Probability for Statisticians, Ex 4.6 (Wellner): Suppose $T \simeq$ Binomial$(n,p)$. Then use the inequality $$\mu(|X| \ge \lambda) \le ...
4
votes
2answers
863 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
5
votes
0answers
137 views

Some rare binomial identities

Long ago , I once saw a nontrivial appealing binomial type of identity that I never saw again. It was something along the line of $\Sigma$$\binom{a(x)}{b(y)}$= where $a$ and $b$ where polynomials not ...
2
votes
2answers
188 views

Simplify $\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$

I am trying to simplify an expression involving summation as follows: $$\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$$ where $n$ is an integer, and $x$ is a positive real number. At a first ...