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)

2
votes
5answers
390 views

How to simplify this triple summation containing binomial coefficients?

$$ \large\sum_{i=0}^{n} \sum_{j=i}^{n} \sum_{k=j}^{n} \binom{i+m-1}{m-1}\binom{j+m-1}{m-1}\binom{k+m-1}{m-1} $$ How to solve it when this involve more than thousand summation ?
6
votes
1answer
130 views

ordered pairs in binomial coefficients

Find the number of ordered pairs $(n,r)$ which satisfy $\binom{n}{r} = 2013$. Find the number of ordered pairs $(n,r)$ which satisfy $\binom{n}{r} = 2014$. My Attempt for $(1)$: By ...
16
votes
3answers
669 views

How to calculate the limit that seems very complex..

Someone gives me a limit about trigonometric function and combinatorial numbers. $I=\displaystyle ...
4
votes
1answer
68 views

Binomial coefficients identity [duplicate]

Prove algebraically or otherwise: $$\sum \limits_{r=0}^n {2r \choose r} {2n-2r \choose n-r} = 4^n $$ where ${n \choose r}$ denotes the usual binomial coefficient. I think there is a combinatorial ...
0
votes
0answers
19 views

Relations between binomial polynomials (umbral calculus)

In the field of umbral calculus binomial polynomials are called such $p_n(x) : \text{deg} \> p_n = n$ that satisfy the binomial identity: $$p_{n}(x+y) = \sum_{k=0}^n \binom{n}{k} p_{k}(x) ...
4
votes
1answer
104 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
4
votes
2answers
410 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 ...
7
votes
3answers
151 views

How prove this sum $\sum_{k=0}^{n-1}a_{k}b_{k}=\frac{n}{2}\binom{2n}{n}$

Question: show that $$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\cdots+\binom{n}{n}\right)=\dfrac{n}{2}\binom{2n}{n}$$ My idea: let ...
3
votes
3answers
280 views

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

Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
-2
votes
2answers
66 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 ...
7
votes
3answers
268 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
58 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
69 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
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
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 ...
4
votes
3answers
99 views

Show that $ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $?

I can't resolve this exercise and I need a tip. $$ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $$ where $ n \geq s $.
2
votes
1answer
79 views

When are the binomial coefficients equal to a generalization involving the Gamma function?

Let $\Gamma$ be the Gamma function and abbreviate $x!:=\Gamma(x+1)$, $x>-1$. For $\alpha>0$ let us generalize the binomial coefficients in the following way: ...
3
votes
1answer
165 views

Derivative of Binomial Coefficient $\binom{2N}{N-x}$ with respect to $x$

I've got $\binom{2N}{N-x}$ and I'd like to take the derivative with respect to $x$. I know that I can take the derivative of $\binom{n}{k}$ w.r.t. n using logarithmic differentiation, but that's not ...
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 ...
4
votes
2answers
439 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
49 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
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 ...
6
votes
4answers
258 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 ...
1
vote
2answers
52 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
389 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 ...
9
votes
4answers
276 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
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
47 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
229 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
41 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)$$ ...
3
votes
1answer
166 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
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
41 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
122 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
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} $ ...
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
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, ...
0
votes
2answers
72 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 ...