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)

3
votes
3answers
143 views

When are products of binomial coefficients equal?

It's known that $\binom{n}{r} = \binom{n}{s}$ if and only if $r = s$ or $r = n - s$. If $n \neq m$, is it true that $\binom{n}{s} \binom{m}{r} = \binom{n}{k} \binom{m}{\ell}$ if and only if ($s = k$ ...
5
votes
1answer
48 views

How to prove$\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$

I saw a combinatorial identity when i study linear-algebra, But the author didn't explain how to get it. $\displaystyle \sum_{i=0}^{k}(-1)^i\binom{n}{k-i}\binom{n+i-1}{i}=0$ I tried $n=10$ or ...
7
votes
2answers
62 views

Summation of the reciprocals of the product of consecutive integers

It is well known that there is a closed formula for: $$\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{(n)(n + 1)}$$ And likewise for: $$\frac{1}{1 \cdot 2 \cdot 3} + \frac{1}{2 \cdot ...
0
votes
1answer
7 views

Walking through the reduction of a cumulative probability function to a polynomial

Setup Define $P(p)$ as follows: $$ P(p) = \sum_{N_1-\phi \cdot N_2 \geq \theta} {n_1 \choose N_1} {n_2 \choose N_2} p^{N_1 + N_2}q^{n_1 + n_2 - N_1 - N_2}. $$ Here, $$ q = 1 - p. $$ The sum is ...
0
votes
1answer
31 views

Factorial and Multiplication

KISS: Is there anything I could do with $$ {xN\choose yN}$$ Given any size $N$, I would like to see how many ways there are to choose a fraction $yN$ out of $xN$. In factorials, that is ...
0
votes
0answers
19 views

Sums of powers of binomial co-efficients

Let $0<p<1.$ I am looking for sharp estimates on the following two quantities, for values of $t>1.$ $$\sum_{r=0}^n \left({n\choose r} p^r(1-p)^{n-r}\right)^t$$ $$\sum_{r=0}^n ...
0
votes
2answers
48 views

pascal's triangle sum of nth diagonal row

today i was reading about pascal's triangle. the website pointed out that the 3th diagonal row were the triangular numbers. which can be easily expressed by the following formula. $$\sum_{i=0}^n i = ...
1
vote
1answer
13 views

Are binomial coefficients with fixed “denominator” log-concave?

I'm working on a problem and began suspecting that the following inequality holds. Let $k\in\mathbb{N}$ be fixed, and define $f(n)={n\choose k}$. Then $f(n)$ is log-concave in $n$, in particular if ...
1
vote
2answers
55 views

Can you verify this inequality $\binom {m^2} {m-1} \geq m^{m-1} \geq 2^{n/2}/n$

$N \geq \binom {m^2} {m-1} \geq m^{m-1} \geq 2^{n/2}/n$, given $n = 2 m\log m$. Can you prove it? Where N is the number of subfunction. This question is part of proof on finding lower bound on the ...
-2
votes
2answers
57 views

Closed-form expression for $\binom{n}{1}+3\binom{n}{3}+5\binom{n}{5}+\cdots$

Find a closed-form expression for $$\binom{n}{1}+3\binom{n}{3}+5\binom{n}{5}+\cdots ,$$ where $n > 1$. You may find the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$ helpful. I really can't ...
0
votes
1answer
51 views

Binomial theorem proof

I'm working through Richard Hamming's "Methods of Mathematics Applied to Calculus, Probability, and Statistics" on my own. I'm struggling with his proof of the binomial theorem, as summarized below. ...
1
vote
0answers
28 views

A model to describe probability to win at certain skill ranges?

Let's say we have a list of all the chess players in the world, and we want to predict the likelihood of success if any player goes up against any other player. (Hypothetical example) I'm assuming ...
1
vote
2answers
51 views

Solve $\frac{1}{2^\theta}\sum_{k=0}^{\theta} {\theta\choose k} \delta(k)=\theta$ for $\delta$

The following arises in unbiased estimation of a parameter for the binomial distribution, but that information is not needed for solving the question. I tried solving this by manipulating the sum to ...
-1
votes
2answers
45 views

Finding coefficients of $x^n$ and $x^{n+r}$ in an expansion

I have to find the coefficients of $x^n$ and $x^{n+r}$ $(1 < r < n)$ in the expansion of: $$(1 + x)^{2n} + x(1 + x)^{2n - 1} + x^2(1 + x)^{2n - 2} + ... + x^n(1 + x)^n$$ How do I solve it?
0
votes
0answers
46 views

Binomial Sum Formula

I can't find a good closed form expression for this, $\sum_{k=0}^n\left[\binom{n}{k}\binom{m}{k}\right]$, where n is the variable, and m is a fixed constant, to be included in the formula. :( Can ...
3
votes
0answers
42 views

Summing the binomial pmf over $n$, part 2

After the great answers I got to this question, I tried summing a similar-looking series using the same strategies ($k \geq 0, \alpha > 1, p \in (0,1)$): $$ \sum_{n=k}^{\infty} {n \choose k} p^k ...
0
votes
1answer
39 views

Proof for the coefficient of $x^n$ in $(x^0 + x^1 + \dots + x^n)^n$

Theorem: The coefficient of $x^n$ in $(x^0 + x^1 + \dots + x^n)^n$ is $\binom{2n-1}{n-1}$. How to prove this? Multinomial theorem produces the following $$ \left(\sum_{k=0}^{n} x^k \right)^n = ...
2
votes
3answers
71 views

Summing the binomial pmf over $n$

I was trying to work out some bounds for a research problem when I came across the innocuous-looking sum: $$ \sum_{n=k}^{\infty} {n \choose k} p^k (1-p)^{n-k}, \quad k \in \mathbb{N}, \; p \in (0,1)$$ ...
0
votes
1answer
35 views

What does this point about triangular number mean

I was reading about triangular numbers from Wikipedia. I makes following point on the above web page: The number of line segments between closest pairs of dots in the triangle can be represented ...
3
votes
2answers
53 views

Sum over two binomials identity

So while trying to count the number of configurations in a statistical mechanics research problem I come across this lovely sum: $$\sum_{i=0}^k \binom{i+r}{r} \binom{k-i+r}{r}$$ I scoured the ...
2
votes
2answers
40 views

Binomial sum with two parameters

Let $m$ and $n$ be two integers. Evaluate $$S_{m,n}=\sum_{j=0}^{m} (-1)^j \binom{m}{j}\binom{mn-jn}{m+1}$$ At first, for $n=2$ I got $S_{m,2}=2^{m-1}m$, for $n=3$ I obtained $S_{m,3}=3^m m$, then I ...
13
votes
3answers
228 views

What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?

Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$ where $n$ is an even positive integer. I tried using binomial identities, but since the binomial ...
3
votes
2answers
51 views

Squares of a number yields a palindrome?

I was doing my statistics homework when I observed an interesting pattern: $ 11^2 = 121 $ $ 111^2 = 12321$ $ 1111^2 = 1234321 $ $ 11111^2 = 123454321 $ $ 111111^2 = 1.234565432 \times 10^{10} $ ...
7
votes
2answers
44 views

Evaluate $\sum_{r=0}^n \binom{n}{r}\sin rx \cos (n-r)x$

Evaluate $$ \sum_{r=0}^n \left[\binom{n}{r}\cdot\sin rx \cdot \cos (n-r)x\right] $$ I tried to use binomial identities, but since there are trigonometric terms, I don't have the idea ...
1
vote
2answers
45 views

Binomial coefficient as a summation series proof?

Alright, so I was wondering if the following is a well known identity or if its existence provides any real benefits other than serving as a time-saver when dealing with higher values for ...
0
votes
2answers
71 views

Can this binomial polynomial sum be simplified?

$$\sum_{k=0}^{n} \binom{n}{k} k^d$$ where $d$ is some fixed positive integer. Is this a well known sum that has a faster-than-$O(n)$ evaluation? It looks similar to Faulhaber's formula, except with ...
0
votes
4answers
40 views

Proving binomial coefficient formula based on Pascal's triangle

I am trying to practice proving things, and I came across one I wasn't sure about. We already know that $\binom{n}{k}$ is the sum of the two corresponding "parent" entities in Pascal's triangle, ...
2
votes
1answer
66 views

Upper bounding a tricky sum

For a problem in probability, I'm trying to find an upper bound for $$ \sum_{d=0}^k\binom{k}{d}\gamma^d(1-\gamma)^{k-d}\left(1-p^d(1-p)^{k-d}\right)^m$$ which will help me analyze what values of ...
3
votes
1answer
37 views

$\binom{n}{k}$ modulo prime power for large $n$ and small $k$

I have to compute several value of $\binom{n}{k}$ mod $p^a$ for prime $p$ over a range of $k$, where $n$ is large and fixed, and $k$ is small and dynamic. Is there a way to speed the process up? If I ...
1
vote
1answer
52 views

On an estimation of binomial coefficient

On page 14 of the book 'Proofs from THE BOOK', there is an estimation presented as: $$\binom{2n}{n}\le \prod_{p\le \sqrt{2n}}\ 2n. \prod_{\sqrt{2n}<p\le \frac{2}{3}n}\ p. \prod_{n<p\le 2n}\ p, ...
3
votes
2answers
41 views

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$, $1 \le n < pq$, are divisible by $pq$? In particular, if $p$ and $q$ are distinct odd primes, and $n$ is even, does $pq ...
2
votes
2answers
46 views

Probability calculation with large numbers

I do have a probability measure: $P = 1 - \dfrac{k!\, \binom{2^{32}} {k}}{(2^{32})^k}$, where $k$ is an positive integer. Yet, I do have trouble evaluating it in terms of a numerical plot, as the ...
10
votes
1answer
177 views

Prove $\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$ for-

Let $n$ be a positve integer. Prove that$$\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$$ for each non-negative ...
0
votes
2answers
32 views

Binomial Coefficient Probability Question

completely stuck in this probability question. I know to use Hypergeometric probability but im not sure about what numbers i should be using. Any help would be great. A regular deck of 52 playing ...
1
vote
0answers
49 views

Inequality with power function and binomial coefficients

Any suggestion on how to proceed to show: $$\frac{2(m+1)^m -1 }{(m+1)m} - \sum_{k=0}^{m} {{m}\choose{k}} \frac{m^k}{(k+1)^2} >0 $$ where $m\geq 2$ is of course an integer. Numerical results ...
1
vote
2answers
40 views

How do I show $(a+b)^K=\sum _{n=0}^K \binom{K}{n} b^n a^{K-n} $ without using recurrence?

We already know that we can represent this binomial as the following: $$(a+b)^K=\sum _{n=0}^K \binom{K}{n} b^n a^{K-n};$$ where $\binom{K}{n} = \frac{K!}{n! (K-n)!}$ My question here is :How do I ...
2
votes
3answers
110 views

Another identity with binomial coefficients

I'm looking for an easy way to prove this identity $$\sum_{j=0}^{n}{(-1)^j j (n-j) {n \choose j}} = 0$$ for $n > 2$. I know this can be proven by differentiating $(1+x)^n = \sum x^j{n \choose j}$ ...
1
vote
2answers
57 views

Evaluate $\binom{n}{1}\alpha_1+\binom{n}{2}\alpha_2+\binom{n}{3}\alpha_3+…+\binom{n}{n}\alpha_n$

If $\alpha_1,\alpha_2,.....,\alpha_n$ are the n;$n^{th}$ roots of unity then$\binom{n}{1}\alpha_1+\binom{n}{2}\alpha_2+\binom{n}{3}\alpha_3+......+\binom{n}{n}\alpha_n$ ...
0
votes
1answer
23 views

Find when the population doubles?

For a given rate of population increse g (that is, g% increase), in order to find out the time t that the population doubles, I have worked out that I need to find t in terms of g in the following ...
3
votes
3answers
358 views

Binomial coefficients based question

$\binom {m}{0}+\binom {m}{1}-\binom {m}{2}-\binom {m}{3}+\binom {m}{4}+\binom {m}{5}-\binom {m}{6}-\binom {m}{7}+........=0$ if and only if for some positive integer k,then $m=$ $(A)4k\hspace{1cm} ...
6
votes
2answers
80 views

Derivative of sum of powers

For fixed $n \geq 1$ and $p \in [0,1]$, is there a nice expression for the derivative of $\sum_{k=0}^n p^k (1-p)^{n-k}$ with respect to p?
3
votes
3answers
91 views

Prof Gould combinatorial identity 3.27 and its “cousin” formula

In the book on Combinatorial Identities of Prof Gould I found the identity 3.27 $$\sum_{k=0}^{\rho}\binom{2x+1}{2k+1}\binom{x-k}{\rho-k}=\frac{2x+1}{2\rho+1}\binom{x+\rho}{2\rho}2^{2\rho}$$ I now ...
4
votes
1answer
60 views

How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

Sloane's A053614 implies that $2, 5, 8, 12, 23$, and $33$ are the only natural numbers $n \geq 1$ which cannot be written as the sum of distinct triangular numbers (i.e., numbers of the form ...
0
votes
1answer
29 views

Help evaluating a partial sum with factorials and binomial coefficients

I come from a CS background and had to contend with a problem similar to this one. Essentially, I want a general-case estimate on how many rolls I'd have to make to land on the same number twice with ...
2
votes
4answers
146 views

Coefficient of binomial expansion

The coefficient of $x^3$ is $4$ times the coefficient of $x^2$ in the new expansion of $(1+x)^n$. Find the value of $n$.
0
votes
4answers
114 views

calculate-binomio-newton

i am help Calculate: $$(C^{16}_0)-(C^{16}_2)+(C^{16}_4)-(C^{16}_6)+(C^{16}_8)-(C^{16}_{10})+(C^{16}_{12})-(C^{16}_{14})+(C^{16}_{16})$$ PD : use $(1+x)^{16}$ and binomio newton
8
votes
2answers
151 views

An interesting property of binomial coefficients that I couldn't prove

So when I was trying to prove the argument in this link I've come up with something. When you extract the left term from the right term, you get the term under them. What is interesting is that as ...
1
vote
2answers
71 views

How to derive the Taylor expansion form of a polynomial expression?

I want to change this polynomial into the form $\sum_{k=0}^m a_k x^k$ $$q_m(x)=\sum_{k=0}^m(-1)^k\binom{2m+1}{2k+1}x^k(1-x)^{m-k}$$ I see no way to do this as I fear one might need intricate binomial ...
11
votes
1answer
121 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
3
votes
2answers
110 views

Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$

I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$: $$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$ So far, I've turned the left hand side of the equality into ...