Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
6
votes
3answers
149 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
136 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
113 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
87 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
76 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 ...
3
votes
2answers
475 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 ...
4
votes
0answers
70 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 ...
4
votes
0answers
93 views
Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?
Remark: I recently rewrote this post, hoping to get answers!
I am analyzing the following experiment:
Pick an $x \in \{0,\ldots,2k\}$ uniformly at random
Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
15
votes
4answers
322 views
Prove that $n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $
Basically I had some fun doing this:
0
1
1 6
7 6
8 12
19 6
27 18
37 6
64 24
61
125
etc.
starting with ...
2
votes
2answers
462 views
Find the coefficient of $x^3y^2z^3$ in the expansion $(2x+3y-4z+w)^9$
The exercise says:
In the expansion $(2x+3y-4z+w)^9$, find the coefficient of
$x^3y^2z^3$.
The formula to find the coefficient of $x_1^{r_1}x_2^{r^2}\dots x_k^{r_k}$ in $(x_1+x_2+\dots+x_k)^n$ ...
1
vote
2answers
333 views
Combinatorial proof of an identity [duplicate]
Possible Duplicate:
Combinatorially prove something
I have to give a combinatorial proof of the identity:
$$\sum_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$$
I can use prove it using the binomial ...
6
votes
6answers
286 views
Find the coefficient of $\sqrt{3}$ in $(1+\sqrt{3})^7$?
I just want to ask you if my solution is correct.
Here's the problem,
Using the Binomial Theorem, find the coefficient of $\sqrt{3}$ in $(1+\sqrt{3})^7$.
Solution: The binomial theorem is,
...
6
votes
3answers
159 views
What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$?
What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$ in terms of $d$? Does the limit exist? Is there a simple upper bound interms of $d$?
3
votes
0answers
178 views
Calculating the Shapley value in a weighted voting game.
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
0
votes
1answer
78 views
Discriminating between model error and random error. [closed]
I am trying to discriminate between a type of systematic error and random error in fitting data to a model.
I have various functions (let's call them 'models') to which I would like to compare a ...
1
vote
2answers
66 views
binomial theorem: find coef. xy
Given:
$$
\left(x-\dfrac{1}{2y}\right)^8\left(x+\dfrac{1}{2y}\right)^4
$$
Using binomial theorem, what is the coefficient of xy in the expansion?
I've tried to do it but I couldn't. Could you ...
4
votes
2answers
991 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 ...
1
vote
0answers
102 views
Binomial coefficient intervals (inequality)
For given $N$, $x$ and $k$ such that $0\leq x<N$ and $2\leq k\leq
\left\lfloor \frac{N+1-2x}{2}\right\rfloor $, does it exist $p,$ $2\leq
p\leq \left\lfloor \frac{N+1}{2}\right\rfloor $ such that
...
2
votes
3answers
418 views
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$.
...
0
votes
1answer
412 views
Distribute distinct objects in identical boxes
Number of ways to distribute 6 Distinct objects to 3 Identical Boxes such that each should have atleast one?
Is there any standard formula for these sums,
as we have for identical - different pair ...
2
votes
2answers
286 views
Number of triangles inside given n-gon?
How many triangles can be drawn all of whose vertices are vertices of a given n-gon and all of whose sides are diagonals ( not sides ) of the n-gon ?
How many k-gons can be drawn in such a way ?
2
votes
1answer
159 views
Given $y$ and $x \choose y$, how to find $x$? [duplicate]
Possible Duplicate:
How to reverse the $n$ choose $k$ formula?
Given integers $y\geq 0$ and $z>0$, is there a good way to find an integer $x\geq y$ such that $z=\binom x y$?
I could ...
8
votes
2answers
195 views
Techniques for summing ratio of binomial coefficients
There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. ...
3
votes
2answers
95 views
What is the exponent of the last term of $(2x^2+3y^3)^{10}$?
What is the exponent of the last term of: $$(2x^2+3y^3)^{10}$$
Hi! I'm sorry if this question seems a bit amateurish. I'm quite confused with this question that was asked in a quiz about binomial ...
3
votes
5answers
218 views
Spivak's Calculus - Exercise 4.a of 2nd chapter
4 . (a) Prove that
$$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$
Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$.
I'm having a hard time trying to solve the problem ...
0
votes
2answers
110 views
generating function of multinomial coefficient
How to express this series in closed form?
$$\sum_{i=1}^{\infty}\frac{(3i)!}{(i!)^3}x^{i}$$
Motive of the generating function is to evaluate the number of the paths from the $(0,0,0)$ to $(n,n,n)$ ...
4
votes
1answer
153 views
Inequality involving sums of fractions of products of binomial coefficients
Let $n\in\mathbb{N}$.
For $0\le l\le n$ consider
\begin{equation}
b_l:=4^{-l} \sum_{j=0}^l \frac{\binom{2 l}{2 j} \binom{n}{j}^2}{\binom{2 n}{2 j}}\text{.}
\end{equation}
Do you know a technique how ...
3
votes
0answers
72 views
Simplifying the sum with binomial coefficients [duplicate]
Possible Duplicate:
Identity involving binomial coefficients
Simplify the sum: $$\sum_{k=0}^n {2k\choose k}{2n-2k\choose n-k}$$
So we can denote $a_n=\sum_{k=0}^n {2k\choose ...
2
votes
1answer
56 views
Criterion for Wolstenholme Primes
Wolstenholme Theorem is a nice theorem that states that every prime $p >3$ satisfies:
$$\binom{2p}{p} \equiv 2 \pmod {p^3}$$
A Wolstenholme prime is a prime $p$ such that $\binom{2p}{p} \equiv 2 ...
5
votes
1answer
125 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 ...
1
vote
1answer
184 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 ...
3
votes
2answers
164 views
what is the easiest way to represent $ \sqrt{1 + x} $ in series
How to expand $ \sqrt{1 + x}$.
$$ \sum_{n = 0}^\infty {{\left ( 1 \over 2\right )!}x^n \over n! \left({1 \over 2 }- n\right )!} = 1 + \sum_{n = 1}^\infty {{\left ( 1 \over 2\right )!}x^n \over n! ...
15
votes
3answers
562 views
Alternating sum of squares of binomial coefficients
I know that the sum of squares of binomial coefficients is just ${2n}\choose{n}$ but what is the closed expression for the sum ${n}\choose{0}$$^2$ - ${n}\choose{1}$$^2$ + ${n}\choose{2}$$^2$ + ... + ...
1
vote
0answers
180 views
The Lucas Theorem and facts
I have studied the Lucas theorem and I encountered the following facts.
How to deduce the following facts from The Lucas theorem?
(1) If d, q > 1 are integers such that , $$\binom{nd}{md}$$ ...
2
votes
1answer
207 views
proof of a finite sum involving a binomial coefficient and a variable.
I found that the following equation holds for integers $l$, $k$, and any $x \neq 0,1$,
$$\tag{1}
\sum\limits_{l = 0}^k {\left( { - 1} \right)^l } \left( {\begin{array}{*{20}c}
k \\
l \\
...
2
votes
3answers
208 views
Two inequalities with binomial coefficients
I have two inequalities that I can't prove:
$\displaystyle{n\choose i+k}\le {n\choose i}{n-i\choose k}$
$\displaystyle{n\choose k} \le \frac{n^n}{k^k(n-k)^{n-k}}$
What is the best way to prove ...
1
vote
0answers
123 views
Lucas' theorem Consequence
Lucas' theorem consequence
$$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$
$$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$
$$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$
...
0
votes
2answers
256 views
Prove $\sum_{k=0}^{n}\binom{n}{k} = 2^{n}$ combinatorially [duplicate]
Possible Duplicate:
Proving a special case of the binomial theorem
Prove the identity using a combinatorial argument:
$$\sum_{k=0}^{n}\binom{n}{k} = 2^{n}$$
I'm not sure how to do a ...
0
votes
5answers
105 views
Prove by induction: $2^n = C(n,0) + C(n,1) + \cdots + C(n,n)$
This is a question I came across in an old midterm and I'm not sure how to do it. Any help is appreciated.
$$2^n = C(n,0) + C(n,1) + \cdots + C(n,n).$$
Prove this statement is true for all $n ...
1
vote
2answers
289 views
modified $\sum{k{n \choose k}}$ closed form expression
There is probably something stupidly simple I'm missing, but I'm trying to find a closed form for:
$$
2\sum_{k=1}^{(n-1)/2} k \, {n \choose k} \hspace{1cm} (n\textrm{ is odd})
$$
Anyone know how to ...
8
votes
1answer
115 views
A three variable binomial coefficient identity
I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following:
$$ \sum_{i+j+k=n} ...
1
vote
2answers
195 views
Limit of binomial coefficient
I would like to find the limit
$$
\lim_{n \to \infty} \binom{s}{n+1} = \lim_{n \to \infty} \frac{s (s-1) \cdots (s-n)}{(n+1)!} ,
$$
where $s \in \mathbb C$.
Actually, it would be enough to show that ...
1
vote
1answer
130 views
Binomial expansion with only odd coefficients?
In William Feller's 1st book p.272
It said the generating function $\Phi$ satisfies
\begin{equation*}
qs\Phi^2(s) - \Phi(s) + ps = 0
\end{equation*}
so it has two roots. The first root is unbounded ...
1
vote
2answers
155 views
Generating function with binomial coefficients
I want to derive formula for generating function $$\sum_{n=0}^{+\infty}{m+n\choose m}z^n$$ because it is very often very useful for me. Unfortunately I'm stuck:
$$ f(z)=\sum_{n\ge 0}{m+n\choose ...
3
votes
1answer
200 views
Three problems with binomial coefficients
I found three difficult problems for me, involving binomial coefficients. They are extremely interesting I think, but I don't know if I have enough knowledge to manage. Seem really hard, can you help ...
1
vote
4answers
221 views
Alternating sum of binomial coefficients
Calculate the sum:
$$ \sum_{k=0}^n (-1)^k {n+1\choose k+1} $$
I don't know if I'm so tired or what, but I can't calculate this sum. The result is supposed to be $1$ but I always get ...
3
votes
0answers
95 views
Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$
How can I prove the following, where $p$ is a prime and $x$ a positive integer?
$$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$
I'm not sure if it is actually true, but I tested ...
2
votes
2answers
249 views
Does this qualify as a proof? (Spivak's 'Calculus')
I'm working through Spivak's 'Calculus' at the moment, and a question about series confused me a bit. I think I have the solution, but I'm not sure if my "proof" holds.
The question is:
Prove ...
2
votes
1answer
115 views
Going from binomial distribution to Poisson distribution
Why does the Poisson distribution
$$\!f(k; \lambda)= \Pr(X=k)= \frac{\lambda^k \exp{(-\lambda})}{k!}$$
contain the exponential function $\exp$, while its relation to the binomial distribution would ...
0
votes
1answer
167 views
Multi binomial theorem application
If i have the polynomial expression
$(a_1x+b_1y+c_1)^p. (a_2x+a_2y+c_2)^d$, and with assumptions $a_1+b_1<<c_1$ , $a_2+b_2<<c_2$, can i expand this as a product of binomials using the ...
