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)

5
votes
2answers
285 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
2answers
12k 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 ...
5
votes
3answers
368 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
534 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
293 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
295 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
91 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
108 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
127 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
98 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
117 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
151 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
193 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
114 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
66 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 ...
11
votes
4answers
293 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
141 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
99 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
402 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
326 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
169 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
204 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
775 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
354 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
271 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
77 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
284 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
249 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
385 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
195 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
580 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
82 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 ...
4
votes
1answer
137 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
1answer
120 views

Squarefree binomial coefficients.

At $n=23$, all binomial coefficients are squarefree. Is this the largest value for $n$ where this is the case? Edit A plot up to $n=50$: A plot up to $n=500$: plotted against $n+1$ and ...
4
votes
1answer
102 views

Simplest proof that $\binom{n}{k} \leq \left(\frac{en}{k}\right)^k$

The inequality $\binom{n}{k} \leq \left(\frac{en}{k}\right)^k$ is very useful in the analysis of algorithms. There are a number of proofs online but is there a particularly elegant and/or simple proof ...
4
votes
4answers
147 views

Evaluating Sums Algebraically or Combinatorially

Consider (1) $$\sum_{k=0}^{n}\binom{n}{k}2^{k-n}$$ (2) $$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$ These sums appear too difficult (in my mind) to evaluate combinatorially. What are some ...
4
votes
2answers
816 views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
4
votes
2answers
781 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
4
votes
1answer
244 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
205 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
2answers
491 views

Limit of alternating sum with binomial coefficient

I need to find a limit, or approximation for $\sum\limits_{k=1}^{n} (-1)^k {n \choose k} \log(a+bk)$ for, say, an $a,b\in (0,10)$. It is not so important what values $a$ and $b$ have. It would be ...
3
votes
4answers
53 views

Explanation about an identity involving inverse binomial coefficients.

Now, I was solving a this problem. It asks for summation of $$\sum\limits_{k =0}^\infty\dfrac{1}{{n+k \choose n}}$$ I solved it using this answer, the answer turns out to be $$\dfrac{n}{n-1}$$ ...
3
votes
2answers
136 views

$\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$?

Is it true that $\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$ ? I feel that it is true because if we define $H_1 (x,r)=rx(1+x)^{r-1}$ , and $H_{m+1}(x,r)=x \dfrac d ...
3
votes
1answer
113 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
3
votes
2answers
80 views

$2^n=C_0+C_1+\dots+C_n$

Could anyone give me hints for this one? $2^n=C_0+C_1+\dots+C_n$ Thats all I can say and I know tricks like integrating or differentiating both side and then put $x=1$ or what ever we need. but ...
3
votes
1answer
132 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
3
votes
2answers
91 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
2answers
250 views

proving a sum of binomial coefficients

How can i prove that $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}=2^{2n-1}$ I tried using induction and pascal's identity but it didn't help me.