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

Sums of binomial coefficients

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
4
votes
4answers
279 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...
4
votes
5answers
451 views

Spivak's Calculus - Exercise 4.a of 2nd chapter

4 . (a) Prove that $$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$ Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$. I'm having a hard time trying to solve the problem ...
12
votes
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
10
votes
1answer
740 views

Sum of product of binomial coefficient

Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$ I tried to use the multinomial theorem, but it doesn't seem applicable.
9
votes
3answers
443 views

Obtaining binomial coefficients without “counting subsets” argument

I want to obtain the formula for binomial coefficients in the following way: Elementary ring theory shows that $(X+1)^n\in\mathbb Z[X]$ is a degree $n$ polynomial, for all $n\geq0$, so we can write ...
8
votes
3answers
217 views

A peculiar binomial coefficient identity

While inventing exercises for a discrete math text I'm writing I came up with this $$ \binom{\binom{n}{2}}{2}=3\binom{n+1}{4} $$ It's an easy result to prove, but it got me wondering Is this pure ...
7
votes
2answers
170 views

Does this really converge to 1/e? (Massaging a sum)

Short version: can we prove that $$\sum_{k=0}^n (-1)^k \binom{n}{k}^2 \frac{k!}{n^{2k}} \to \frac1e$$ as $n \to \infty$? Long version: First, consider $$a_n = \sum_{k=0}^n \frac{(-1)^k}{k!}$$ It is ...
7
votes
2answers
344 views

Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$

I need to estimate the asymptotics of $$\sum_{k=0}^{n} {\binom n k}^a, \quad a>2, \quad a \in \mathbb{N}$$ In particular, I'm pretty much interested in $a=4$ case, but if the general solution ...
7
votes
2answers
683 views

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
6
votes
1answer
157 views

How to transform the product to sum?

I just wonder that how to prove that $$ \prod_{m=1}^{n}\Big(x-2\cos\frac{m\pi}{n+1}\Big)=\sum_{k=0}^{[n/2]}(-1)^{k}\binom{n-k}{k}x^{n-2k}. $$ Similarly, how to transform the product $$ ...
6
votes
2answers
213 views

Wanted: Insight into formula involving binomial coefficients

There is the formula $$\sum_i (-1)^i\binom{a}{k+i}\binom{l+i}{b} = (-1)^{a+k} \binom{l-k}{b-a}.$$ Only finitely many summands are non-zero (those for $i\in\{b-l,\ldots,a-k\}$), so the sum is finite. ...
6
votes
2answers
13k views

Negative Exponents in Binomial Theorem

I'm looking at extensions of the binomial formula to negative powers. I've figured out how to do $n \choose k$ when $n < 0 $ and $k \geq 0$: $${n \choose k} = (-1)^k {-n + k - 1 \choose k}$$ So ...
6
votes
1answer
828 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
5
votes
2answers
241 views

How prove this $\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $

I think the following equality is true ($p\in \mathbb{N},p\ge 2$): $$\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $$ when $p=2$, then ...
5
votes
2answers
305 views

Proof of inequality $\sum\limits_{k=0}^{n}\binom n k\frac{5^k}{5^k+1}\ge\frac{2^n\cdot 5^n}{3^n+5^n}$

Show that $$\sum_{k=0}^{n}\binom n k\frac{5^k}{5^k+1}\ge\frac{2^n\cdot 5^n}{3^n+5^n}$$ where $$\binom n k=\frac{n!}{k!(n-k)!}$$
5
votes
3answers
374 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
5
votes
3answers
553 views

A Binomial Coefficient Sum

In my work on $f$-vectors in polytopes, I ran across an interesting sum which has resisted all attempts of algebraic simplification. Does the following binomial coefficient sum simplify? \begin{align} ...
4
votes
2answers
296 views

maybe this sum have approximation $\sum_{k=0}^{n}\binom{n}{k}^3\approx\frac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty$

prove or disprove this $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$ this problem is from when Find this limit ...
4
votes
3answers
303 views

Number of binary strings with $n$ ones and $m$ zeros

$f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros. Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$ I got to the point that: $$\sum_{a=0}^n ...
3
votes
2answers
54 views

Sums with squares of binomial coefficients multiplied by a polynomial

It has long been known that \begin{align} \sum_{n=0}^{m} \binom{m}{n}^{2} = \binom{2m}{m}. \end{align} What is being asked here are the closed forms for the binomial series \begin{align} S_{1} &= ...
3
votes
2answers
93 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
3
votes
1answer
113 views

Combinatorial proof of $k\binom{n}{k} = n\binom{n-1}{k-1}$ [duplicate]

I'm trying to prove this combinatorially. $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ I know the first step is to relate a question to the equation. My question was if you have $n$ friends how many ways can ...
3
votes
2answers
130 views

how to prove $\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$ without induction?

$$\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$$ how to prove it without induction? I tried with several way but I failed anybody help me ?
3
votes
0answers
168 views

proof of formula and calculation sum

Show that following formula is true: $$ \sum_{i=0}^{[n/2]}(-1)^i (n-2i)^n{n \choose i}=2^{n-1}n! $$ Using formula calculate $$ \sum_{i=0}^n(2i-n)^p{p \choose i} $$
2
votes
2answers
100 views

Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction

I have a problem with following equality: $$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$ And I would like to use induction in following way: Base: $$ m = n $$ And: $$ ...
2
votes
3answers
121 views

To prove $\sum_{i=0}^k\binom{n}{3i}\leq \frac{1}{3}(2^n+2)$

If $n\in \mathbb{Z^+}$ and $k$ is the largest integer for which $3k\leq n$, then is it true that $\sum_{i=0}^k\binom{n}{3i}\leq \frac{1}{3}(2^n+2)$? My work: We can break this into two cases: ...
1
vote
1answer
156 views

What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
1
vote
3answers
205 views

Show that ${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$

Show that $${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$$ Please help me showing the above identity. I tried to solve it in algebraic way and in combinatoric way, but ...
1
vote
2answers
115 views

Help proving ${n \choose k} \equiv 0 \pmod n$ for all $k$ such that $0<k<n$ iff $n$ is prime.

I can prove the $n$ is prime case: If $n$ is prime, then since $k < n$ and $n$ is prime, the factor of $n$ in the numerator won't be cancelled out. So the question boils down to Let an integer ...
1
vote
2answers
70 views

${{p^k}\choose{j}}\equiv 0\pmod{p}$ for $0 < j < p^k$

$${{p^k}\choose{j}}\equiv 0\pmod{p}.\ \ \ \text{for $0 < j < p^k$ and p is prime}$$ I can show this for $k=1$ using the fact that in denominator all numbers are less than $p$. I need hint ...
12
votes
3answers
621 views

How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer ...
11
votes
4answers
294 views

Determine $\displaystyle \lim_{n \to \infty}{{n} \choose {\frac{n}{2}}}\frac{1}{2^n}$, where each $n$ is even

For each positive even integer $n$, set $$P_n = \displaystyle {{n} \choose {\frac{n}{2}}}\frac{1}{2^n}.$$ Show that $\displaystyle \lim_{n \to \infty} P_n$ exists and determine its value. Here's ...
10
votes
1answer
144 views

Can this product be written so that symmetry is manifest?

Let $i,$ $j,$ $k$ be nonnegative integers such that $i+j+k$ is even. The expression $$(-1)^{j+k}\binom{i+j+k}{i,j,k}\prod_{\ell=0}^{k-1} \frac{i-j+k-2\ell-1}{i+j+k-2\ell-1}$$ apparently computes the ...
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
8
votes
3answers
100 views

Show that ${-n \choose i} = (-1)^i{n+i-1 \choose i} $

Show that ${-n \choose i} = (-1)^i{n+i-1 \choose i} $. This is a homework exercise I have to make and I just cant get started on it. The problem lies with the $-n$. Using the definition I get: $${-n ...
8
votes
3answers
406 views

Non-probabilistic proofs of a binomial coefficient identity from a probability question

Combining the answers given by me and Ralth to the probability question at Probability Question, we get the following identity: $$ \sum\limits_{k = m}^n {{n \choose k}p^k (1 - p)^{n - k} {k \choose ...
7
votes
2answers
331 views

Simplify $\sum_{k=1}^{n} {k\choose m} {k}$

$\sum_{k=1}^{n} {k\choose m} {k}$ I have tried to expand it, but the m is pretty annoying. Any ideas to get rid of the summation and give a simple formula? There is a part before $\sum_{k=1}^{n} ...
7
votes
1answer
171 views

Determining when a certain binomial sum vanishes

Consider the following sum of signed binomial coefficients: $$S_{n,a,p} = \sum_{i \equiv a \mod p} \binom{n}{i}(-1)^i$$ ($n$ is a positive integer, $p$ is an odd prime, $a$ is between $0$ and ...
7
votes
5answers
208 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
7
votes
4answers
794 views

partial sum involving factorials

Here is an interesting series I ran across. It is a binomial-type identity. $\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}}{(n-k)!}=4^{n}\cdot n!$ I tried all sorts of playing around, ...
7
votes
2answers
359 views

A Curious Binomial Sum Identity without Calculus of Finite Differences

Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$, \begin{align} \binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} ...
7
votes
3answers
274 views

Asymptotic difference between a function and its binomial average

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number. Dividing by $2^n$, we ...
6
votes
1answer
86 views

Combinatorial Interpretation of a Binomial Identity

The original post due to David Peterson is here. How to establish the following Binomal identity combinatorially: $$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = ...
6
votes
3answers
287 views

How many solutions are possible to this equation?

Given $$A+2B+3C=N $$ where $N$ is a given positive integer. $A ,B,C\in\mathbb{N}$ vary from $0$ to $\infty$. How many solutions will be there to this equation?
6
votes
3answers
258 views

Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is $${n \choose k} {n-1 \choose k} k!.$$ Is there a ...
6
votes
1answer
393 views

Vandermonde's-like identity

The Vandermonde's identity gives $$\sum_{k=0}^r \binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.$$ Here is an example of Vandermonde's-like identity: For all $0 \le m \le n$, $$\sum_{k=0}^{2m} ...
5
votes
2answers
198 views

Show that the $k$th forward difference of $x^n$ is divisible by $k!$

Define the forward difference operator $$\Delta f(x) = f(x+1) - f(x)$$ I believe that if $f(x)$ is a polynomial with integer coefficients, $\Delta^k f(x)$ is divisible by k!. By linearity it suffices ...
5
votes
1answer
601 views

Prove that Pascals triangle contains only natural numbers, using induction.

I'm currently working my way through Spivak, and I'm stuck on the following. Prove that Pascals triangle only contains natural numbers using induction and the following relation: $\left( ...
4
votes
2answers
97 views

Show that $\sum\limits_{i=0}^{n/2} {n-i\choose i}2^i = \frac13(2^{n+1}+(-1)^n)$

While doing a combinatorial problem, with $n$ being even, I came up with the expression $$\sum_{i=0}^{n/2} {n-i\choose i}2^i$$ for which I used wolfram to get a closed form expression of ...