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
968 views

Binomial expansion, how to do them quickly?

I'm currently preparing for a test where I'm bound to do a couple of binomial expansions. Since I never encountered them in my formal education, I looked how to do them myself and found out: $ ...
4
votes
1answer
111 views

The coefficient of $x^{101}$ in the expansion of $(1-x)(1-2x)(1-2^2x)…(1-2^{101}x) =?$

The coefficient of $x^{101}$ in the expansion of $(1-x)(1-2x)(1-2^2x)...(1-2^{101}x) =?$ Can I get some help please?Thanks in advance
4
votes
1answer
102 views

On a sum related to alternating sign matrices

I'm trying to prove that $$A_{n,k} = \binom{n+k-2}{k-1}\frac{(2n-k-1)!}{(n-k)!}\prod_{j=0}^{n-2}\frac{(3j+1)!}{(n+j)!}$$ implies $$A_n = \sum_{k=1}^nA_{n,k}=\prod_{j=0}^{n-1}\frac{(3j+1)!}{(n+j)!}.$$ ...
4
votes
1answer
86 views

Binomial theorem for prime exponent

Could you explain to me why for prime $p$ we have the following? $$(x+y)^p - (x^p + y^p)= x^p + \binom{p}{1}x^{p-1}y + \binom{p}{2}x^{p-2}y^2 + \binom{p}{p-1}xy^{p-1} + y^p.$$ I found it here: ...
4
votes
2answers
537 views

Sum of product of binomial coefficients $ = (-1)^n$

Based on the binomial expansion of $(1+x)^n$, show that: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$$ This is a question from a very old high school exam paper I came across. It ...
4
votes
1answer
69 views

how compute $\gcd\Bigl(\binom{n}{1},\binom{n}{2},\binom{n}{3},…,\binom{n}{n-1}\Bigr)?$

how to prove $$\gcd\Biggl(\binom{n}{1},\binom{n}{2},\binom{n}{3},...,\binom{n}{n-1}\Biggr)=\begin{cases} p, & \text{$n=p^m$ ;$p$ is prime} \\ 1, & \text{o.w} \\ \end{cases}$$ thanks in ...
4
votes
2answers
1k views

In how many ways can 3 distinct teams of 11 players be formed with 33 men?

Problem: In how many ways can 3 distinct teams of 11 players be formed with 33 men? Note: there are 33 distinct men. The problem is similar to this one: How many distinct football teams of 11 ...
4
votes
1answer
267 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 ...
4
votes
1answer
214 views

Evaluating a limit involving binomial coefficients.

If $N_c=\lfloor \frac{1}{2}n\log n+cn\rfloor$ for some integer $n$ and real constant $c$, then how would one go about showing the following identity where $k$ is a fixed integer: $$\lim_{n\rightarrow ...
4
votes
1answer
457 views

Computing the Coefficients of a Polynomial in the Binomial Basis

Let $f(t) = \sum_{i = 0}^{n} c_i \ t^i$ be a degree $n$ polynomial. In the binomial basis, we can write $f(t) = \sum_{k = 0}^{n} h_k \ \binom{t + n - k}{n}$. Using the calculus of finite differences, ...
4
votes
3answers
58 views

Proving that $r{n \choose r}=n{n-1\choose r-1}$

For proving that: $r{n \choose r}=n{n-1\choose r-1}$ I attempted it with: $r{n\choose r}=\frac{rn!}{r!(n-r)!}=\frac{n!}{(r-1)!(n-r)!}$ $n{n-1\choose ...
4
votes
3answers
62 views

Hypergeometric 2F1 with negative c

I've got this hypergeometric series $_2F_1 \left[ \begin{array}{ll} a &-n \\ -a-n+1 & \end{array} ; 1\right]$ where $a,n>0$ and $a,n\in \mathbb{N}$ The problem is that $-a-n+1$ is ...
4
votes
1answer
41 views

Value of sum $\sum_{i=0}^n\binom{2n}{2i}(-3)^i$

What is the value of the sum $\sum_{i=0}^n\binom{2n}{2i}(-3)^i$? It looks like the binomial expansion $(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i$, but we only take every other term, and also the power is ...
4
votes
1answer
343 views

Probability of two independent random variables being equal

Assume that $X$ and $Y$ are two independent random variables that follow the binomial distribution of parameters $p$ (the probability of one success) and $n$ (the number of trials). I was wondering ...
4
votes
1answer
140 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
4
votes
1answer
92 views

Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$. This seems like it should be a simple question, but try as I might, I can't seems to find any way that does ...
4
votes
3answers
160 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
4
votes
1answer
181 views

Sum involving binomial coefficient

I want to analyse the following expression for $x \geq 0$: $$ \sum_{k = 0}^n (-1)^{k+n} \binom{n+k}{2k} x^k $$ I expect and want to prove that for $x \geq 4$, the expression tends to infinity as $n ...
4
votes
1answer
212 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 ...
4
votes
1answer
293 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
693 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
2answers
54 views

Another binomial coefficient sum

In my work I ran across the following binomial coefficient sum: $$ S=\sum_{a=0}^{n-1-l} (-1)^a \binom{n}{l+1+a} \binom{l+a}{l} $$ where $n\geq 0$ and $0\leq l \leq n-1$. I browsed the web and found ...
4
votes
4answers
205 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
120 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
138 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
1answer
150 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
2answers
181 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
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
210 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
196 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
89 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
247 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
158 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
291 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
75 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
4
votes
1answer
174 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
187 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
156 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
102 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
39 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
89 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
4
votes
0answers
140 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
82 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
124 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
2answers
406 views

This question involves Pascal's Triangle & Binomial Theorem. Full Question

Could anyone please help me on the following problem: Factorize the expression $P(n)=n^x-n$ for $x=2,3,4,5$ Determine if the expression is always divisible by the corresponding $x$. If divisible use ...
4
votes
1answer
567 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) ...