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)

8
votes
4answers
375 views

Why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k} = 0$?

I know that the expansion of $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k}$ equals to zero. But why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$ also equal to zero for $n \geq 2$? I've been ...
8
votes
4answers
258 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
8
votes
7answers
886 views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
8
votes
4answers
198 views

Proving this binomial identity $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$

A teacher gave this as a homework question, and I have tried but haven't been able to arrive at a solution. $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$ Could someone prove it, or at least ...
8
votes
3answers
324 views

Intuitive explanation for a polynomial expansion?

Is there an ituitive explanation for the formula: $$ \frac{1}{\left(1-x\right)^{k+1}}=\sum_{n=0}^{\infty}\left(\begin{array}{c} n+k\\ n \end{array}\right)x^{n} $$ ? Taylor expansion around x=0 ...
8
votes
3answers
338 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
8
votes
2answers
89 views

Rough bound for sum $\binom{3n}{0}+\binom{3n}{1}+\cdots+\binom{3n}{n-1}$

Is it true that $$\frac{\dbinom{3n}{0}+\dbinom{3n}{1}+\cdots+\dbinom{3n}{n-1}}{2^{3n}}<\frac13$$ for all positive integers $n$? I've plotted the first few values of $n$ and noticed that the ...
8
votes
4answers
506 views

Show that $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$

The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one ...
8
votes
3answers
889 views

Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
8
votes
3answers
229 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 ...
8
votes
2answers
482 views

Is there a combinatorial way to see the link between the beta and gamma functions?

The Wikipedia page on the beta function gives a simple formula for it in terms of the gamma function. Using that and the fact that $\Gamma(n+1)=n!$, I can prove the following formula: $$ ...
8
votes
2answers
1k views

prime numbers in Pascal's triangle

Just wondering about this: Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$? From the first 18 lines it appears that this is ...
8
votes
3answers
234 views

Putting ${n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ in a closed form

As the title says, I'm trying to transform $\displaystyle{n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ into a closed form. My work: $\displaystyle\left(1 + ...
8
votes
3answers
371 views

Polynomial in $\mathbb{Q}[x]$ sending integers to integers?

We can view the binomial coefficient $\binom{x}{k}$ has a polynomial in $x$ with degree $k$. So taking some $f\in\mathbb{Q}[x]$, why is $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$, precisely when the ...
8
votes
4answers
472 views

Inequality with central binomial coefficients

For every even positive number $N$ we have: $$ {2N \choose N } < 2^N {N \choose N/2 } < 2 {2N \choose N } $$ (Furthermore, $\frac{2^N {N \choose N/2 }}{{2N \choose N }} \to \sqrt{2} $ for ...
8
votes
5answers
836 views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
8
votes
3answers
410 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 ...
8
votes
4answers
312 views

Orthogonality for Binomial Coefficients

Could somebody explain to me where these two formulas come from as applications of the binomial theorem? $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$ for non-negative integers $r\lt n$. And ...
8
votes
3answers
102 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
1answer
482 views

How to compute the asymptotic growth of $\binom{n}{\log n}$?

I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$ It sounds like it's something simple, but I can't get a nice expression I can use. Any ideas on how to do this?
8
votes
2answers
729 views

Binomial coefficients: how to prove an inequality on the $p$-adic valuation?

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used: $$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln ...
8
votes
3answers
390 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} ...
8
votes
3answers
389 views

Proving the sum of squares of sine and cosine using the Cauchy product formula

Here are the power series of sine and cosine: $$\sin(x) = \sum_{n=0}^{\infty} (-1)^n \frac {x^{2n+1}} {(2n+1)!}$$ and $$\cos(x) = \sum_{n=0}^{\infty} (-1)^n \frac {x^{2n}} {(2n)!}$$ How can it be ...
8
votes
2answers
211 views

Ordinary generating function for $\binom{3n}{n}$

The ordinary generating function for the central binomial coefficients, that is, $$\displaystyle \sum_{n=0}^{\infty} \binom{2n}{n} x^{n} = \frac{1}{\sqrt{1-4x}}$$ follows from the generalized ...
8
votes
4answers
266 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 ...
8
votes
1answer
303 views

Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$. LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset. RHS: We are ...
8
votes
1answer
424 views

Summation of an Infinite Series: $\sum_{n=1}^\infty \frac{4^{2n}}{n^3 \binom{2n}{n}^2} = 8\pi G-14\zeta(3)$

I am having trouble proving that $$\sum_{n=1}^\infty \frac{4^{2n}}{n^3 \binom{2n}{n}^2} = 8\pi G-14\zeta(3)$$ I know that $$\frac{2x \ \arcsin(x)}{\sqrt{1-x^2}} = \sum_{n=1}^\infty ...
8
votes
1answer
285 views

Smallest constant in exponent so that limit of sum is $0$

I am trying to work out the smallest constant $c>0$ so that $$\lim_{n \to \infty} \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}} =0 .$$ ...
8
votes
3answers
181 views

How can we find the gcd for elements (binomial coefficient)?

$\gcd\left(\binom{2n}1,\binom{2n}3,\binom{2n}5,\ldots,\binom{2n}{2n-1}\right)$ i want to know what is specialty of such a series.I am not able to generalize the problem solution.Is there any rule for ...
8
votes
2answers
283 views

Binomial identity

I'd like to get a hint to prove the following identity: $$\tag{1}\sum_{\nu}(-1)^{\nu}\displaystyle \binom{a}{\nu}\binom{n-\nu}{r}=\binom{n-a}{n-r} .$$ The original statement reads "By specialization ...
8
votes
3answers
989 views

Proving $\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$ [duplicate]

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
8
votes
2answers
292 views

Computing the last non-zero digit of ${1027 \choose 41}$?

I am working on the following problem: Let $x_n$ be a sequence of positive odd numbers. If $N$ is the number of ordered pairs $(x_1, x_2, x_3, \dots, x_{42})$ such that $$x_1 + x_2 + x_3 + \dots + ...
8
votes
4answers
142 views

A binomial identity from Mathematical Reflections

Here is the problem: Let $m,n$ be positive integers with $n>m$. Prove that $\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$ This ...
8
votes
1answer
194 views

Evaluate $\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$

Evaluate $$\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$$ I don't understand where to start. Please help.
8
votes
2answers
212 views

How prove binomial cofficients $\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$

How prove this $$\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$$ This equation How prove it? Thank you I want take this ...
8
votes
1answer
296 views

Vandermonde identity in a ring

Let $R$ be a commutative $\mathbb{Q}$-algebra. For $r \in R$ and $n \in \mathbb{N}$ we can define the binomial coefficient $\binom{r}{n}$ as usual by $\binom{r}{0}=1$ and ...
8
votes
2answers
3k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
8
votes
2answers
182 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
8
votes
1answer
358 views

Derivation of bound on expression involving binomial coefficient from Erdős and Rényi 1959

I'm in the process of working through Erdős and Rényi's 1959 article "On Random Graphs I". In the proof of the first Lemma, equation 14 gives a bound on an expression involving several binomial ...
8
votes
1answer
429 views

$\binom{n}{k} : \binom{n}{k+1} : \binom{n}{k+2} = a : b : c$

It is a rather surprising fact (to me, at least) that $\displaystyle \binom{14}{4} = 1001$; $\displaystyle \binom{14}{5} = 2002$; $\displaystyle \binom{14}{6} = 3003$. Actually, this is the only ...
8
votes
0answers
154 views

Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$

I found this question in an old problem set. There's no hint or solution mentioned. For $n \geq 3$, prove or disprove the existence of $(x,y,z) \in \mathbb N^3, ...
7
votes
6answers
457 views

Closed-form expression for $\sum_{k=0}^n\binom{n}kk^p$ for integers $n,\,p$

Is there a closed-form expression for the sum $\sum_{k=0}^n\binom{n}kk^p$ given positive integers $n,\,p$? Earlier I thought of this series but failed to figure out a closed-form expression in $n,\,p$ ...
7
votes
2answers
727 views

Finding $\lim\limits_{n \to \infty} \sum\limits_{k=0}^n { n \choose k}^{-1}$

We know that $$ 2^n= (1+1)^n = \sum_{k=0}^n {n \choose k}$$ I was asked to solve this limit, $$\lim_{n \to \infty} \ \sum_{k=0}^n {n \choose k}^{-1}=? \quad \text{for} \ n \geq 1$$
7
votes
5answers
301 views

The $n^{th}$ root of the geometric mean of binomial coefficients.

$\{{C_k^n}\}_{k=0}^n$ are binomial coefficients. $G_n$ is their geometrical mean. Prove $$\lim\limits_{n\to\infty}{G_n}^{1/n}=\sqrt{e}$$
7
votes
6answers
367 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
7
votes
3answers
2k views

Proof of a combinatorial identity: $\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? ...
7
votes
3answers
511 views

Hard elementary combinatorics problem

How does one compute (without brute force) the smallest integer $n$ such that $\binom{2n}{1}(-3)^0 + \binom{2n}{3}(-3)^1 + \binom{2n}{5}(-3)^2 + \cdots + \binom{2n}{2n-1}(-3)^{(n-1)} = 0$?
7
votes
5answers
370 views

Are there surprisingly identical binomial coefficients?

Suppose $\binom{n}{k}=\binom{n'}{k'}$ with $k \geq 2$, $k' \geq 2$, $n \geq 2k$ and $n' \geq 2k'$. Does it follow that $n=n'$ and $k=k'$? EDIT: Yup, ...
7
votes
2answers
223 views

Find the sum of this series :$ \frac{1}{{1!2009!}} + \frac{1}{{3!2007!}} + \cdots + \frac{1}{{1!2009!}}$

Find the sum of this series : $$\sum\limits_{\scriptstyle 1 \leqslant x \leqslant 2009 \atop {\scriptstyle x+y=2010 \atop \scriptstyle {\text{ }}x,y{\text{ odd}} }} {\frac{1}{{x!y!}}} = ...
7
votes
3answers
749 views

Summation Identity: $\sum_{i=1}^ni^3 = \left( \frac{n(n+1)}{2} \right)^2$

I have to prove: $$\sum\limits_{i = 1}^n i^3 = \Bigg( \frac{n(n+1)}{2}\Bigg)^2$$ Using the following: $$n^3 = 6 {n \choose 3} + 6 {n \choose 2} + n \quad \forall n \in \mathbb{N}$$ My work is that ...