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
0answers
235 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
407 views

p-adic numbers and binomial coefficients

Let $\alpha\in \mathbb{Z}_p$ be an $p$-adic integer and define for $n\in \mathbb{Z}_{\geq 0}$ $${\alpha\choose n} := \frac{\alpha(\alpha-1)\cdot\ldots\cdot(\alpha-n+1)}{n!}.$$ This is again a ...
3
votes
6answers
1k views

How do I begin proving this binomial coefficient identity: ${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
3
votes
4answers
234 views

Why does $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$?

I don't understand the identity $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$, where $k$ is fixed. I first approached it by considering the identity $$ \sum_{n,k\geq 0} \binom{n}{k} x^n y^k = ...
3
votes
3answers
301 views

Is there a closed-form formula for sum of “odd combinations”? [closed]

So, I was trying to come with a formula for the sum of below series: ${2^n \choose 1}+{2^n \choose 3}+...+{2^n \choose 2^n - 1}$ Thank you.
3
votes
3answers
167 views

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

Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
3
votes
5answers
137 views

Calculate $\lim_{n\rightarrow +\infty}\binom{2n} n$

Calculate $$\lim_{n\rightarrow +\infty}\binom{2n} n$$ without use Stirling's Formula. Any suggestions please?
3
votes
4answers
2k views

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$

Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$ I have expanded it this far: $$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$ but then I am ...
3
votes
4answers
97 views

Algebric proof for the identity $n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$

Prove the identity: $$n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$$ I tried using the binomial coefficients identity $2^n = \sum_{k=1}^n {n \choose k}$ but got stuck along the way.
3
votes
2answers
180 views

Is it possible to prove $\sum_{k=0}^n \binom{n\vphantom{k}}{k} \binom{k}{m} = \binom{n\vphantom{k}}{m} 2^{n-m}$ combinatorially?

$$\sum_{k=0}^n \binom{n}{k} \binom{k}{m} = \binom{n}{m} 2^{n-m}$$ So for the proof, I have to use a real example, such as choosing committees, binary sequences, giving fruit to kids, etc. I have been ...
3
votes
5answers
582 views

Binomial theorem application

I have a question about the bonomial theorem, and in specifically, a question that I want help on. I have worked out the answer, but by manually expanding each and every alternative. However, I ...
3
votes
3answers
544 views

Water and wine mixing problem

This is a well-known problem involving a water barrel and a wine barrel, described here. The trick to solving the puzzle is that one need not make the calculations for each stage of the liquid ...
3
votes
2answers
230 views

Calculating a binomial sum

I came across this excercise in an old exam (in discrete math), and I don't know how to approach it: $$\sum_{k=0}^{10}\left(\frac{1}{2}\right)^k\left(-1\right)^k\binom{10}{k}$$ I know the answer is ...
3
votes
3answers
1k views

How can I prove that the binomial coefficient ${n \choose k}$ is monotonically nondecreasing for $n \ge k$?

I want to prove that the binomial coefficient ${n \choose k}$ for $n \ge k$ is a monotonically nondecreasing sequence for a fixed $k$. How do I do this?
3
votes
3answers
342 views

Closed form for a sum involving binomial coefficient [duplicate]

Possible Duplicate: How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $? How to derive the following equality? $$\sum_{j=0}^n \binom{n}{j} \frac1{j+1} = ...
3
votes
4answers
681 views

Understanding $n\choose k$ in terms of sum and product rules

This is a follow up on my earlier question. To put some values and context, let me say I am trying to justify the number of possibilities of choosing 2 chapters out of 10 in a book i,e $10 \choose 2$. ...
3
votes
4answers
125 views

Show that $\binom{2n}{n}$ is an even number, for positive integers $n$.

I would appreciate if somebody could help me with the following problem Show by a combinatorial proof that $$\dbinom{2n}{n}$$ is an even number, where $n$ is a positive integer. I ...
3
votes
2answers
259 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.
3
votes
2answers
2k views

Sum of square binomial coefficients [duplicate]

Please feel free to close this is necessary as I didn't see exactly this question (some variations that I tried but didn't seem to apply. Prove: $$\sum_{k=0}^{n}{\binom{n}{k}^2}=\binom{2n}{n}$$ I ...
3
votes
2answers
818 views

Why does the $n$-th power of a Jordan matrix involve the binomial coefficient?

I've searched a lot for a simple explanation of this. Given a Jordan block $J_k(\lambda)$, its $n$-th power is: $$ J_k(\lambda)^n = \begin{bmatrix} \lambda^n & \binom{n}{1}\lambda^{n-1} & ...
3
votes
5answers
436 views

Evaluating even binomial coefficients

Can someone give me a hint how to evaluate $$ \binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)},$$ where $o(n)$ is $n$ if $n$ is even and $n-1$ otherwise ?
3
votes
2answers
138 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
4answers
140 views

What is the meaning of $(2n)!$

I came across something that confused me $$(2n)!=?$$ What does this mean: $$2!n!, \quad 2(n!)$$ or $$(2n)!=(2n)(2n-1)(2n-2)...n...(n-1)(n-2)...1$$ Which one is right? The exercise is to show that ...
3
votes
4answers
161 views

Find the Sum $1\cdot2+2\cdot3+\cdots + (n-1)\cdot n$

Find the sum $$1\cdot2 + 2\cdot3 + \cdot \cdot \cdot + (n-1)\cdot n.$$ This is related to the binomial theorem. My guess is we use the combination formula . . . $C(n, k) = n!/k!\cdot(n-k)!$ so . . ...
3
votes
2answers
105 views

How can I solve $\sum\limits_{i = 1}^k i \binom{k}{i-1}$

If anyone could help with the steps in solving this summation. I've been playing with it most of the day. It started from me trying to prove $\sum\limits_{i=0}^{k+1} \left(i\binom{k+1}{i}\right) = ...
3
votes
5answers
383 views

Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$. I realized that the total number of ...
3
votes
3answers
138 views

${n \choose k} \le ({en \over k})^k$ proof

$${n \choose k} \le \left({en \over k}\right)^k$$ Could anyone give me a hint how to prove this by induction on $k$? (I can prove it without induction)
3
votes
4answers
715 views

Trying to find $\sum\limits_{k=0}^n k \binom{n}{k}$ [duplicate]

Possible Duplicate: How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$? $$\begin{align} &\sum_{k=0}^n k \binom{n}{k} =\\ &\sum_{k=0}^n k ...
3
votes
4answers
881 views

Alternating sum of binomial coefficients

Calculate the sum: $$ \sum_{k=0}^n (-1)^k {n+1\choose k+1} $$ I don't know if I'm so tired or what, but I can't calculate this sum. The result is supposed to be $1$ but I always get ...
3
votes
4answers
14k views

Probability of winning a prize in a raffle

My work is having it's annual Christmas raffle today. 1600 tickets have been sold, and there are 40 prizes to win. I have bought ten tickets. What are the odds I will win a prize? While an initial ...
3
votes
3answers
86 views

A combinatorial identity: $\sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $

I proved this combinatorial identity while doing some linear algebra. For any positive integer $k$, $$ \sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $$ I was wondering what ...
3
votes
4answers
182 views

proving an invloved combinatorial identity

How to prove following Identity? $$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$ This seems very hard to me. Any idea about how to prove it combinatorialy? ...
3
votes
2answers
242 views

How find this sum closed form?

Have this sum have close form $$f(n)=\sum_{k=0}^{n-1}\left(\left(\sum_{i=0}^{k}(-1)^i\binom{n}{i}\right)\cdot\left(‌​\sum_{j=k+1}^{n}(-1)^j\binom{n}{j}\right)\right)$$ Maybe this sum can use ...
3
votes
1answer
138 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
512 views

finding the combinatorial sum [duplicate]

How to find the sum of combinatorial summation of the following series, where $C(n, k)$ denotes the number of combinations of $n$ given $k$ are the same? $$\sum_{k=0}^{n/2} C(n-k, k)$$ Need help on ...
3
votes
4answers
263 views

Computing a sum of binomial coefficients

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a lot ...
3
votes
2answers
346 views

how to visualize binomial theorem geometrically?

How does $ \binom{n}{k} $ 'n choose k' get involved with coefficient of $ (a+b)^n $. Is there any intuitive geometrical picture (interpretation) that it seems ...
3
votes
2answers
228 views

simplify $(a_1 + a_2 +a_3+… +a_n)^m$

How to simplify this best $(a_1 + a_2 +a_3+... +a_n)^m$ for $m=n, m<n, m>n$ I could only get $\sum_{i=0}^{m}\binom{m}{i}a_i^i\sum_{j=0}^{m-i}\binom{m-i}{j}a_j ... $
3
votes
3answers
191 views

Proofs from the BOOK: Bertrand's postulate: $\binom{2m+1}{m}\leq 2^{2m}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 8: It's about the part, where the author says: $$\binom{2m+1}{m}\leq 2^{2m}$$ because ...
3
votes
4answers
61 views

Showing $\binom{2n}{n} = (-4)^n \binom{-1/2}{n}$

Is there a proof for the following identity that only uses the definition of the (generalized) binomial coefficient and basic transformations? Let $n$ be a non-negative integer. $$\binom{2n}{n} = ...
3
votes
4answers
120 views

Closed form for a formula with a summation over $i\binom{n-i}{k-1}$, and combinatorial proof?

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end. $$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i ...
3
votes
2answers
134 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?
3
votes
3answers
589 views

The sum of series involving binomial coefficients

Could someone help me find: $$\sum_{k}k \binom{n}{k}p^k(1-p)^{n-k}\\ and \sum_{k}k^2 \binom{n}{k}p^k(1-p)^{n-k}\\ 0\leq p\leq 1, k\in N, n\ggg k $$ I know the answer to the first one is np, and the ...
3
votes
2answers
130 views

If $x_n = (\prod_{k=0}^n \binom{n}{k})^\frac{2}{n(n+1)}$ then $\lim_{n \to \infty} x_n = e$

I try to prove the following: $$x_n = \left(\prod_{k=0}^n \binom{n}{k}\right)^\frac{2}{n(n+1)}$$ $$\lim_{n \to \infty} x_n = e$$ I want to use double sided theorem, so I've proven that $$x_n \ge ...
3
votes
3answers
129 views

How prove this $\binom{n}{m}\equiv 0\pmod p$

let $p$ is prime number,and such $p\mid n,p\nmid m,n\ge m$ show that $$p\>\Big|\>\binom{n}{m}$$ I know that: if $p$ is prime number,then $$\binom{n}{p}\equiv \left[\dfrac{n}{p}\right] \pmod ...
3
votes
3answers
108 views

Find the coefficient using binomial theorem.

What is the coefficient of $x^{20}$ in the expression: $$(x+1)^{10}.(x^2 -1)^8$$
3
votes
5answers
169 views

Can $\frac{n!}{(n-r)!r!}$ be simplified?

I'm trying to calculate in a program the number of possible unique subsets of a set of unique numbers, given the subset size, using the following formula: $\dfrac{n!}{(n-r)!r!}$ The trouble is, on ...
3
votes
3answers
530 views

Evaluate a sum with binomial coefficients

$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$ I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$ ...
3
votes
1answer
307 views

Proof that $\binom{n}{\smash{0}}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{\smash{2}n}{n}$ using a counting argument

Prove the following by way of a counting argument: $$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$$
3
votes
1answer
250 views

Proof of identity involving binomial coefficients

I'll be happy if you could help me prove this argument with algebraic tools: $${N\choose 0}a^N+{N\choose 1}a^{N-2}+{N\choose 2}a^{N-4}+{N\choose 3}a^{N-6}+\dots = \frac{a^2+1}{a}$$ Thanks, Don