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
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 ...
4
votes
1answer
282 views

Algebraic Proof that $\sum\limits_{k=0}^m \binom{r}{k} \binom{m+n-r}{m-k} = \binom{m+n}{m}$

How do I prove that: $$\sum\limits_{k=0}^m \binom{r}{k} \binom{m+n-r}{m-k} = \binom{m+n}{m} ~~~~~~~~~ (r <= m + n) $$ by using an algebraic identity? My Attempt: I know of the generating ...
4
votes
1answer
129 views

Convergence of a sequence of partial binomial sums

I have a sequence $$a_n = (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k.$$ I want to show that $a_n\to 0$ when $n\to\infty$ if $0\le p < \frac{1}{2}$. Here's a ...
4
votes
1answer
684 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
4
votes
3answers
193 views

Convolution of binomial coefficients

As part of a (SE) problem I've been working on, I came up with this expression: $$ \sum_{i=0}^M\binom{M-1+i}{i}\binom{M+i}{i} $$ I'd like to get a closed form for this, but after a considerable amount ...
4
votes
1answer
119 views

A convolution involving binomials

Given $$f(i)\gt0,\:g(i)>0,\:i =0,1,2,3,...\:$$and$$\sum_{i=0}^{\infty}f(i) = 1,\sum_{i=0}^{\infty}g(i) = 1$$Prove that, if$$\frac{g(l-k)f(k)}{\sum_{i=0}^{l}f(i)g(l-i)}=\binom{l}{k}p^k(1-p)^{l-k}\: ...
4
votes
1answer
131 views

Complex Analysis proof of multinomial expression

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$ A nice complex analysis proof (by Felix Marin, here) follows as: ...
4
votes
2answers
183 views

Unusual binomial sum: $\sum_{d=k}^{n} {d \choose k} p^{d}(1-p)^{n-d}$

Does anyone know how to simplify the following sum? It's been giving me and everyone else I've showed it to quite a bit of trouble. I'm quite confident that this should simplify, but I just can't seem ...
4
votes
1answer
147 views

Closed form of $\sum_{k=1}^{n}\binom{n}{k} h^{(n-k)}(0)f^{(k-1)}(0)$

Is there a closed form for: $$\sum_{k=1}^{n}\binom{n}{k} h^{(n-k)}(0)f^{(k-1)}(0)$$ where: $$h(x)=(1-x)^{\alpha}(A-Bx)^{\frac{1}{\gamma}-\alpha}$$ and ...
4
votes
1answer
74 views

Verification of a Combinatorial Identity

I have a challenge for you combinatorial mathematicians. Is anyone willing to verify the following combinatorial identity? ...
4
votes
2answers
208 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
4
votes
1answer
182 views

Combinatorial Identity

I have to validate the following identity which is defined: $$ \sum_{k=1}^n (-1)^{k-1}*q^{\frac{k(k-1)}{2}} *\frac{\prod_{i=n-k+1}^n(1-q^i)}{\prod_{i=1}^k(1-q^i)} = 1 $$ where $0<q<1$. I ...
4
votes
1answer
192 views

Solve the recurrence: $f(n, k) = f(n-1, k-1) + f(n-1, k) + 2^n$

This is somewhat like Pascal's triangle but with an additional $2^n$: $$\left\{\begin{align*} &f(n,0)=f(n,n)=2^n-1\\ &f(n,k)=f(n-1,k-1)+f(n-1,k)+2^n \end{align*}\right.$$ Is there a direct ...
4
votes
1answer
246 views

Probability of a certain dice roll sum disregarding lowest rolls

The number of ways to obtain a total of $p$ in $n$ rolls of $s$-sided dice is: $$c=\sum_{k=0}^{\lfloor(p-n)/s\rfloor}(-1)^k\binom{n}k\binom{p-sk-1}{n-1}\;.$$ What I'm interested in is making the $n$ ...
4
votes
1answer
156 views

Calculate $\sum_{i=1}^{[\frac{\sqrt n}{2}]}{n\choose i}$

It is known that $\sum_{i=1}^n {n \choose i}=2^n$. I am wondering what would be the sum if we change the upper limit to $\sqrt n/2$, i. e. How to calculate$$\sum_{i=1}^{[\frac{\sqrt n}{2}]}{n \choose ...
4
votes
1answer
290 views

Partial sum of ${A \choose i} {B\choose n-i}$, when $B=-1$?

It's easy to see that $$ \sum_i {A\choose i} {B\choose n-i} = {A+B\choose n} $$ since when we choose $n$ things out of $A+B$, some ($i$ of them) are in the $A$ and the rest are in the $B$. Is there ...
4
votes
1answer
206 views

Limit involving the totient function and combination

Do you think the following limits are correct? $\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\varphi(N) \choose k} {d-1 \choose k-1}}{\varphi(N)^d}=0$ ...
4
votes
0answers
23 views

Show that $p \in \left[\frac{4^m}{\sqrt{2m}},\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
0answers
144 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
4
votes
0answers
181 views

How to prove that $\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$?

How to prove this: $$\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$$ For all $x\in\mathbb R_{\ge0}$ and with $\binom{x}{r}=\frac{\Gamma(x+1)}{\Gamma(r+1)\cdot\Gamma(x-r+1)}$ It is obviously ...
4
votes
0answers
153 views

Proving an equation involving binomial coefficients

Prove that $$\sum_{q=0}^v \binom{v}{q}\frac{q!}{v^{q+1}} = \sum_{q=0}^{v-1} \binom{v-1}{q} \frac{(q+2)!}{v^{q+2}}$$ Thanks. Below are what I have tried: Approach 1: $$\sum_{q=0}^{v-1} ...
4
votes
0answers
95 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) ...
4
votes
1answer
38 views

Properties of cumulative binomial distribution

Let $F\left(k, n, p\right) = \sum_{i=1}^k\binom{n}{i}p^i\left(1-p\right)^{n-i}$ denote the cumulative binomial distribution function. If $F\left(k, n, p\right)-F\left(k, n, p'\right) \geq ...
4
votes
0answers
139 views

Binomial-like sum involving falling factorials

We know that $\sum_{k=0}^n a^k \frac{n^{\underline k}}{k!} = (1+a)^n$. Is there a known (preferably closed) form for $\sum_{k=0}^n a^k n^{\underline k}$?
4
votes
0answers
80 views

Binomial coefficient sum over top index

I am trying to evaluate a sum over binomial coefficients which is giving me some problems. Specifically I want to calculate: $$\sum_{r=0}^{c-1}\binom{r+n}{n}\frac{1}{c-r}$$ My main thought was to ...
4
votes
1answer
87 views

In Pursuit of a Broader Understanding of Complicated Binomial Coefficient Sums

$$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$ The above identity was posted once before by me, however, all results were obtained numerically exploring the identity rather than understanding ...
4
votes
1answer
112 views

How to calculate (or approximate) “trimmed” (a+b)^n?

$a^n + C_n^{1}a^{n-1}b + ... C_n^{n-1}a^{1}b^{n-1}+b^n = (a+b)^n$ But how to calculate (maybe approximately) $a^n + C_n^{1}a^{n-1}b + ... C_n^{i}a^{n-i}b^{i} = ?$ For info, the underlying problem ...
4
votes
1answer
545 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 ...
4
votes
0answers
163 views

How to transform series of series into series

I need to prove this equation. $$ \sum_{k=0}^{i-2} \left( e \space α(k+1)\space\frac{(-1)^{i+k+2}}{(i-k-2)!} \right) = \sum_{k=0}^{i-2} \frac{(i-k)^k}{k!} \space e^{i-k} (-1)^k\space where,\space α(i) ...
4
votes
2answers
382 views

computation of the sum

I am having trouble to compute the following sum: $$ \sum_{k=0}^n(n-2k)^p \frac{{n \choose k}{2m-n \choose m-k}}{{2m \choose m}} $$ Here $p\geq 2$. To simplify the question, we can even assume that ...
4
votes
0answers
201 views

Simplifying an expression involving binomial coefficients

Consider $$ \prod_{j=0}^{i-1}\binom{n-2j}{2}\left[1+\sum_{k=0}^{N-1}{\left( \prod_{l=0}^{k} \dfrac{N-l}{M-l}\right)\left(1 + \sum_{m=k+1}^{N-1} \prod_{p=k+1}^m \dfrac{N-p}{M-p}\right)+1}\right] $$ ...
4
votes
0answers
240 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
418 views

p-adic numbers and binomial coefficients

Let $\alpha\in \mathbb{Z}_p$ be an $p$-adic integer and define for $n\in \mathbb{Z}_{\geq 0}$ $${\alpha\choose n} := \frac{\alpha(\alpha-1)\cdot\ldots\cdot(\alpha-n+1)}{n!}.$$ This is again a ...
3
votes
6answers
1k views

How do I begin proving this binomial coefficient identity: ${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
3
votes
3answers
214 views

Prove $\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$

Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
3
votes
4answers
234 views

Why does $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$?

I don't understand the identity $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$, where $k$ is fixed. I first approached it by considering the identity $$ \sum_{n,k\geq 0} \binom{n}{k} x^n y^k = ...
3
votes
3answers
333 views

Is there a closed-form formula for sum of “odd combinations”? [closed]

So, I was trying to come with a formula for the sum of below series: ${2^n \choose 1}+{2^n \choose 3}+...+{2^n \choose 2^n - 1}$ Thank you.
3
votes
5answers
138 views

Calculate $\lim_{n\rightarrow +\infty}\binom{2n} n$

Calculate $$\lim_{n\rightarrow +\infty}\binom{2n} n$$ without use Stirling's Formula. Any suggestions please?
3
votes
4answers
2k views

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$ I have expanded it this far: $$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$ but then I am ...
3
votes
4answers
110 views

Algebric proof for the identity $n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$

Prove the identity: $$n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$$ I tried using the binomial coefficients identity $2^n = \sum_{k=1}^n {n \choose k}$ but got stuck along the way.
3
votes
2answers
185 views

Is it possible to prove $\sum_{k=0}^n \binom{n\vphantom{k}}{k} \binom{k}{m} = \binom{n\vphantom{k}}{m} 2^{n-m}$ combinatorially?

$$\sum_{k=0}^n \binom{n}{k} \binom{k}{m} = \binom{n}{m} 2^{n-m}$$ So for the proof, I have to use a real example, such as choosing committees, binary sequences, giving fruit to kids, etc. I have been ...
3
votes
5answers
599 views

Binomial theorem application

I have a question about the bonomial theorem, and in specifically, a question that I want help on. I have worked out the answer, but by manually expanding each and every alternative. However, I ...
3
votes
3answers
562 views

Water and wine mixing problem

This is a well-known problem involving a water barrel and a wine barrel, described here. The trick to solving the puzzle is that one need not make the calculations for each stage of the liquid ...
3
votes
3answers
181 views

matrix representations and polynomials

I just investigated the following matrix and some of its lower powers: $$M = \left[\begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&1&1&0\\ 1&1&1&1 ...
3
votes
2answers
234 views

Calculating a binomial sum

I came across this excercise in an old exam (in discrete math), and I don't know how to approach it: $$\sum_{k=0}^{10}\left(\frac{1}{2}\right)^k\left(-1\right)^k\binom{10}{k}$$ I know the answer is ...
3
votes
3answers
1k views

How can I prove that the binomial coefficient ${n \choose k}$ is monotonically nondecreasing for $n \ge k$?

I want to prove that the binomial coefficient ${n \choose k}$ for $n \ge k$ is a monotonically nondecreasing sequence for a fixed $k$. How do I do this?
3
votes
3answers
350 views

Closed form for a sum involving binomial coefficient [duplicate]

Possible Duplicate: How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $? How to derive the following equality? $$\sum_{j=0}^n \binom{n}{j} \frac1{j+1} = ...
3
votes
4answers
686 views

Understanding $n\choose k$ in terms of sum and product rules

This is a follow up on my earlier question. To put some values and context, let me say I am trying to justify the number of possibilities of choosing 2 chapters out of 10 in a book i,e $10 \choose 2$. ...
3
votes
4answers
128 views

Show that $\binom{2n}{n}$ is an even number, for positive integers $n$.

I would appreciate if somebody could help me with the following problem Show by a combinatorial proof that $$\dbinom{2n}{n}$$ is an even number, where $n$ is a positive integer. I ...
3
votes
2answers
262 views

proving a sum of binomial coefficients

How can i prove that $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}=2^{2n-1}$ I tried using induction and pascal's identity but it didn't help me.