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
4answers
156 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
3answers
135 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
241 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
320 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
3answers
189 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
110 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
3answers
328 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
129 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
127 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
2answers
2k 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
3answers
107 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
165 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
1answer
297 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
3answers
227 views

Combinatorial proof of $\binom{n}{k} = \binom{n}{n-k}$

How do I prove this combinatorially? $$\displaystyle \binom{n}{k} = \binom{n}{n-k}$$
3
votes
1answer
247 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
295 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
128 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
239 views

General Leibniz rule for triple products

I have a question regarding the General Leibniz rule which is the rule for the $n^{th}$ derivative of a product and reads: $$ (f g)^{(n)}=\sum_{k=0}^{n} {n \choose k} \,f^{(k)} g^{(n-k)}. $$ ...
3
votes
1answer
487 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
336 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
103 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
232 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 ...
3
votes
4answers
76 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
3
votes
3answers
185 views

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ...
3
votes
4answers
130 views

Find $\sum_{r=0}^{2n}\frac{r}{r+2}\binom{2n}r\;.$

Find $$\sum_{r=0}^{2n}\frac{r}{r+2}\binom{2n}r\;.$$ I got $$\frac{2^{2n+1}(2n^2+n+1)-1}{(2n+1)(2n+2)}$$ but the answer is $$\frac{2^{2n+1}(2n^2-n+1)-2}{(2n+1)(2n+2)}$$ Thanks for the help...
3
votes
3answers
184 views

Proving an Identity involving $4^N$ [duplicate]

I am trying to prove the following identity: $$\sum_{k=0}^N\left({2 \, N - 2 \, k \choose N - k}{2 \, k \choose k}\right)=4^N$$ I have tried writing $4^N=2^{2N}=(1+1)^{2N}=(1+1)^N(1+1)^N$, and ...
3
votes
3answers
83 views

Manipulation of a binomial coefficient

In obtaining a formula for the Catalan numbers I have got the expression $-\frac{1}{2}\binom{1/2}{n}(-4)^n$. All my efforts to show that this simplifies to $\frac{1}{n}\binom{2n-2}{n-1}$ have not ...
3
votes
2answers
197 views

what is the easiest way to represent $ \sqrt{1 + x} $ in series

How to expand $ \sqrt{1 + x}$. $$ \sum_{n = 0}^\infty {{\left ( 1 \over 2\right )!}x^n \over n! \left({1 \over 2 }- n\right )!} = 1 + \sum_{n = 1}^\infty {{\left ( 1 \over 2\right )!}x^n \over n! ...
3
votes
2answers
140 views

Combinations and Gaussian function

I notice that the function $\binom{C}{x}$, where $C$ is some constant, resembles a Gaussian function; for example, here is the plot for $\binom{20}{x}$: This corresponds to the Gaussian function $a ...
3
votes
3answers
380 views

Proof of a Binomial Identity using a combinatorial argument

Question Prove that if $k$ and $l$ are two positive integer with $k ≥ l$, then $\binom{2k}{2} =\binom{k−l}{2}+ \binom{k+l}{2}+ k^2 − l^2$ using a combinatorial argument. I tried using Vandermonde's ...
3
votes
2answers
484 views

Sum of cubes of binomial coefficients

I reduced a homework problem in combinatorics to giving an asymptotic estimate for $\sum_{k=0}^n{n \choose k}^3$. I assume Stirling's approximation can help, but I'm not experienced with making ...
3
votes
2answers
212 views

Unusual version of the binomial theorem?

This was an old problem I had years ago, but never really solved. Maybe it can be cracked here? The situation is as follows. Denote by $\mathbb{Q}(q)[X,Y]$ the algebra of polynomials over ...
3
votes
2answers
2k views

How can I determine asymptotic growth of binomial coefficients?

Say I have a binomial coefficient $y=\binom{5n+3}{n+2}$ or $y=\binom{n^2+4}{3n}$ something of the sorts in terms of the variable $n$. How can I determine $f$ so that $y = O(f)$? Is there a general ...
3
votes
3answers
65 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
3
votes
2answers
45 views

Silly mistake on evaluating the sixth term of $\left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$?

I am trying to evaluate the sixth term of $\displaystyle \left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$ with the binomial theorem. I've done the following: The sixth term might be the term for $k=5$ ...
3
votes
3answers
333 views

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$?

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$? How can we calculate this expression ? I've applied the binomial theorem formula and got $91$ terms but I am not sure if it is right ...
3
votes
4answers
213 views

Coefficient of $x^n$ in the series

How will we find the coefficient of $x^n$ in the following series: $$(1+x+2x^2+3x^3+...)^n$$ Please suggest if there is some formula or if it can be computed using the computer in $\log n$ time. I ...
3
votes
1answer
91 views

How to prove the identity $(n-k)! \sum _{i=0}^{n-k} \frac{(k+i-1)!}{i!} = \frac{n!}{k}$?

I am stuck in proving the following : $$(n-k)! \sum _{i=0}^{n-k} \frac{(k+i-1)!}{i!} = \frac{n!}{k}$$ NOTE: I don't want any combinatorial proof. I think it is some algebraic manipulation.
3
votes
2answers
81 views

Expression for power of a natural number in terms of binomial coefficients

Is there a general expression for the pth power of a natural number k in terms of binomial coefficients? I found this identity in a high-school text, which was obtained by simply equating ...
3
votes
2answers
92 views

How to get the sum of the values in a $N \times N$ table?

How to get the sum of the values in a $N \times N$ table (without adding repeating products such as $6 \times 7$ and $7 \times 6$ twice and without counting perfect squares)? Figured out that $1 ...
3
votes
3answers
123 views

Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$ I got this far before I got stuck: $\begin{eqnarray*} ...
3
votes
4answers
2k views

Proving q-binomial identities

I was wondering if anyone could show me how to prove q-binomial identities? I do not have a single example in my notes, and I can't seem to find any online. For example, consider: ${a + 1 + b \brack ...
3
votes
2answers
3k views

Find the coefficient of $x^3y^2z^3$ in the expansion $(2x+3y-4z+w)^9$

The exercise says: In the expansion $(2x+3y-4z+w)^9$, find the coefficient of $x^3y^2z^3$. The formula to find the coefficient of $x_1^{r_1}x_2^{r^2}\dots x_k^{r_k}$ in $(x_1+x_2+\dots+x_k)^n$ ...
3
votes
2answers
2k views

How to prove it by means of a combinatorial argument?(A combinatorial exercise) [duplicate]

Possible Duplicate: 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 It is an exercise in a book on discrete ...
3
votes
3answers
90 views

Is this expression right? If yes how can I prove it combinatorially?

Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please
3
votes
1answer
638 views

Binomial coefficient equal to $\binom nk + 3\binom{n}{k-1} + 3\binom{n}{k-2} + \binom{n}{k-3}$?

Find one binomial coefficient equal to the following expression: $$\binom nk + 3\binom{n}{k-1} + 3\binom{n}{k-2} + \binom{n}{k-3}$$ I tried to expand using the definition of $\dbinom{n}{k} = ...
3
votes
1answer
203 views

Find $\sum\limits_{k=\frac{n+1}{2}}^n{n \choose k}$ closed form

Write $$\sum\limits_{k=\frac{n+1}{2}}^n{n \choose k}$$ in its closed form. $n \in N_{odd}$ First time to confront this kind of problem. How do I solve it? (If its a "you are asking for too ...
3
votes
1answer
66 views

Good approximation for $\binom{N}{\frac{N}{2}}$

$$\log_2\binom{N}{\frac{N}{2}}\approx N\log_2N - 2(N-\frac{N}{2})\log_2(N-\frac{N}{2})=N\log_2N - 2\frac{N}{2}\log_2(\frac{N}{2})$$ $$=N\log_2N - {N}{}\log_2({N}) + {N}{}=N$$ ...
3
votes
4answers
104 views

Question about ${n+1\choose k} = {n\choose k} + {n\choose k-1}$ proof?

I've found past proofs of this problem and for the most part I'm able to follow. $$\eqalign{{n\choose k}+{n\choose k-1}&= {n!\over (n-k)!k!}+ {n!\over (n-(k-1))! (k-1)!} \text{ (step 1)}\cr ...
3
votes
3answers
69 views

difficult problem about binomial coefficients

If $r,m,n\in \mathbb N$ so that $r\le \min \{n,m\}$, then $$\binom{n+m}{r} = \binom{n}{0}.\binom{m}{r}+\binom{n}{1}.\binom{m}{r-1}+...+\binom{n}{r}.\binom{m}{0}.$$ If $\min \{n,m\} < r$, then how ...