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)

3
votes
3answers
285 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
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
92 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
176 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
571 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
536 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
226 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
331 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
675 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
120 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
258 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
759 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
426 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
139 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
381 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
708 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
865 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
13k 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
83 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
181 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
134 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
498 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
261 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
339 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
190 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
117 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
525 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
168 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
512 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
305 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
3
votes
3answers
353 views

Integral with binomial coefficient

Is it possible to evaluate this integral without using the gamma function $$ \int_0^1 {a \choose b}x^b(1-x)^{a-b} dx$$ It looks a little like part of binomial theorem, but I don't have an idea how to ...
3
votes
2answers
3k views

Prove $\sum \binom nk 2^k = 3^n$ using the binomial theorem

I'm studying for a midterm and need some help with proving summation using the binomial theorem. $\sum\limits_{k=0}^n {n \choose k} 2^k = 3^n$ This is what I'm thinking so far: In the binomial ...
3
votes
1answer
105 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 ...
3
votes
1answer
512 views

Binomial fraction sum to infinity

Compute the limit: $$\lim_{n\to\infty} \sum_{k=0}^n \frac {\dbinom{n}{k}}{\dbinom{2n-1}{k}}$$ Here i tried to give some k values to the sum hoping to see a possible pattern, but i didn't figure out ...
3
votes
2answers
361 views

lacunary sum of binomial coefficients

I am sure there must be a known estimate for sums of the form: $$ S_d(n)=\sum_{j=0}^n \binom{dn}{dj} $$ where $d\ge 1$. For $d=1$, the answer is obvious. For $d=2$, the answer is here: Sum with ...
3
votes
2answers
104 views

Digit in the ten's place of an expression

What is the digit in the ten's place of $23^{41}* 25^{40}$ ? How do you calculate this? The usual method for this kind of problem is using the Binomial theorem, but I couldn't solve it.
3
votes
2answers
233 views

A question about binomial-coefficients

How to compute the following $\sum_{t=0}^{k}{2m-1-t \choose t}{2m-1-(k-t) \choose k-t}$, where $1\leq k\leq 2m-1$? Please point me to some references if this has already been studied. Thanks for ...