# Tagged Questions

Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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)$ ...
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 ...
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$ ...
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 ...
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, ...
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$?
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 ...
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 ...
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 ...
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 ...
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 ...
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$. ...
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 ...
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 ?
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 ...
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. ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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! ...
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$ + ... + ...
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}$$ ...
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 \\ ...
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 ...
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$$ ...
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 ...
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 ...
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 ...
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} ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 109, "mathjax_display_tex": 24, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9143093824386597, "perplexity_flag": "middle"}