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)

0
votes
0answers
14 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 ...
4
votes
2answers
437 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
2
votes
4answers
2k views

Fermat's Combinatorial Identity: How to prove combinatorially? [duplicate]

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$ I don't have much experience with combinatorial proofs, so I'm grateful for all the hints. (Presumptive) ...
0
votes
2answers
43 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
2answers
30 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 ...
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 ...
-2
votes
2answers
54 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 ...
1
vote
0answers
25 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 ...
6
votes
4answers
255 views

How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

How to closed the sum $\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$ I'm trying divide two cases $n$ odd and $n$ even. I predict that ...
0
votes
0answers
46 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
2answers
47 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 ...
5
votes
2answers
387 views

Alternative combinatorial proof for a combinatorial identity

I have a question with regards to combinatorics. I am supposed to show the following combinatorial identity: $\sum_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$. The ...
8
votes
4answers
275 views

Prove that $\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$ [duplicate]

Prove that $$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ What should I do for this equation? Should I focus on proving ...
-1
votes
2answers
42 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 ...
13
votes
3answers
226 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
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 ...
3
votes
2answers
97 views

Sum of series ${n\choose 2a}{a\choose 0}+ {n\choose {2a+2}}{{a+1}\choose 1} + {n\choose {2a+4}}{{a+2}\choose 2} + \ldots$

I wanted to check the rationality of the cosine function for some rational multiples of $\pi$. And I found out that, $\cos(n \cdot\arccos x)$ generates a polynomial in $x$ whose co-efficients have the ...
13
votes
6answers
494 views

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
6
votes
2answers
166 views

Binomial transform of a scaled version of the catalan numbers.

I was looking at the mathworld entry for Catalan Numbers http://mathworld.wolfram.com/CatalanNumber.html and was surprised to find formula (11) there: (1) $C_n= \sum_{k=0}^n (-1)^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
70 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)$$ ...
3
votes
1answer
165 views

Proving an equality involving binomial coefficients and summations

Question: $$\sum_{k=0}^{n}\left ( -1 \right )^{k}\binom{2n}{k}\binom{2n-k}{2n-2k}=\sum_{2n}^{k=0}\binom{2n}{k}^{2}\left ( \frac{1+\sqrt{5}}{2} \right )^{2n-k}\left ( \frac{1-\sqrt{5}}{2} \right ...
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
52 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 ...
11
votes
1answer
120 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 ...
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 ...
3
votes
2answers
50 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} $ ...
27
votes
7answers
2k views

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Let $m,n\ge 0$ be two integers. Prove that $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$ where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = ...
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 ...
1
vote
1answer
51 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, ...
0
votes
2answers
69 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 ...
15
votes
1answer
171 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
0
votes
4answers
39 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
65 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 ...
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 ...
10
votes
1answer
174 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 ...
7
votes
2answers
107 views

Roots of a polynomial whose coefficients are ratios of binomial coefficients

Prove that $\left\{\cot^2\left(\dfrac{k\pi}{2n+1}\right)\right\}_{k=1}^{n}$ are the roots of the equation $$x^n-\dfrac{\dbinom{2n+1}{3}}{\dbinom{2n+1}{1}}x^{n-1} + ...
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 ...
1
vote
1answer
49 views

Is it possible to evaluate this binomial sum?

Would it be possible to evaluate this sum? $$\sum_{k=0}^{N/2}k\binom{N+1}{k},$$ where $N$ is even? I know that the sum $$\sum_{k=0}^{N+1}k\binom{N+1}{k}=2^N(N+1)$$ (by ...
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
46 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 ...
0
votes
1answer
905 views

binomial calculation method

I want solve this probability: For $p= 0.4$ $q=0.8$ $n= 20$ $1-P(5<x<11)$ = $1-\sum_{k=6}^{10} \binom{20}{k}(0.4)^k(0.6)^{20-k}. Wolfram Alpha -> = 0,2531$ Is calculation method ...
1
vote
1answer
56 views

Multinomial identity - guidance needed

I need hints on a direction to prove that $$\displaystyle\prod_{k=1}^{n} {{k+1\choose2}\choose k} ={{n+1\choose2}\choose1,2,3.....,n}$$ Any ideas?
2
votes
1answer
430 views

Proving an identity with a combinatorial proof

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity: $$\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$ The problem is that I ...
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 ...
15
votes
4answers
479 views

Sum of binomial coefficients $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$

How do I prove the following identity: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$ I am trying to use inclusion-exclusion, and this will boil down to a sum like ...