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)

2
votes
2answers
142 views

How do I prove the negative binomial identity?

I'm having trouble proving the negative binomial identity ${r\choose k} = (-1)^k{k-r-1\choose k}$. Here's what I've got so far: I know that ${k-r-1\choose k} = {(k-r-1)!\over k!(-r-1)!}$, and the ...
3
votes
1answer
86 views

On Elements of $p$th Row in n Pascal's Triangle (For Prime $p$)

If $p$ is a prime number, in Pascal's triangle all the terms in the $p$th row - except the 1s - are multiples of $p$ . It's easy to prove this property using the formula for $\binom{p}{k}$. Is there ...
4
votes
1answer
89 views

Simplify $\sum_{k=0}^n \frac{1}{k!(n-k!)}.$

Is there a way to simplify the expression $$\sum_{k=0}^n \frac{1}{k!(n-k)!}?$$ This came up when I was trying to determine $\mathbb{P}(X+Y =r)$ given a joint mass probability $$m_{X,Y}(j,k) = ...
2
votes
2answers
69 views

Does this sequence of inverse-binomial numbers have a name?

I was inspired by considering the following: $$\left(\sum_{i=1}^n i\right)^2=\sum_{i=1}^n i^3$$ Are there exact formulas for the sums of the powers of the integers? For example, we have: ...
1
vote
5answers
77 views

Calculate $\lim_{n\to\infty}\binom{2n}{n}2^{-n}$

I would like to show that: $$\lim_{n\to\infty}\binom{2n}{n}2^{-n} = \infty$$ I have gotten as far as: $$ \binom{2n}{n}={(2n)!\over (n!)^2}=({n\over1}+1)({n\over2}+1)(\dots)({n\over n}+1)\ge2^n $$ But ...
1
vote
0answers
28 views

Binomial coefficient modulo composite number [closed]

For a prime number n , ${n \choose r} \mod n$ is 0 for all 0 < r < n If n is composite I want to know for which values of r the value of ${n \choose r} \mod n$ becomes 0 (for r in ...
2
votes
1answer
154 views

How prove this $\sum_{k+j=n,0\le k,j\le n}\binom{2k}{k}\binom{2j}{j}=4^n$ [duplicate]

Show that $$ \sum_{k\ +\ j\ =\ n\atop{\vphantom{\LARGE A}0\ \le\ k,\phantom{A} j\ \le\ n}}{2k \choose k}{2j \choose j} = 4^{n} $$ I think use integral solve it. But I don't it,and this problem is ...
2
votes
0answers
157 views

Getting K heads out of N biased coins problem (formula generation ).

Problem- Given a set of coins n with each coin i having Pi probability to give heads. Find the probability of getting k heads, when all coins are tossed together. hi i have solved this problem ...
1
vote
0answers
28 views

Closed form for a binomial containing a differential operator

Is there a closed form for $(x + D)^n$ where D is the differential operator with respect to x? Avi's comment in this post helped me understand this expression a bit better, but I'm still curious if ...
0
votes
1answer
68 views

Combinations and their sum with constraints

I have a number of books (n). They all have different a different thickness and mass. I know that there are (2^n)-1 combinations to place the books. The order of the books does not matter. However ...
0
votes
1answer
87 views

Theory behind multiplication & combinations?

If with the Binomial Coefficient we try to find the possible combinations $\binom{n}{k}$ where $n$ is equal to $k$ what is the theory behind factorial resulting in the correct solution? E.g. ...
4
votes
1answer
216 views

Workshop on Pascal's Triangle for Middle School Students

We're going to hold a three-hour math workshop for some middle school students. It'll about the Pascal's triangle. Well, we can ask the students to find patterns in the triangle, or try to prove some ...
0
votes
3answers
128 views

Help with binomial coefficients using binomial theorem

I am studying for an upcoming test and I was having trouble with this practice problem: Determine the coefficient of $x^{111}y^{444}$ in the expansion of $(17x + 71y)^{555}$. I am thinking of using ...
12
votes
3answers
356 views

How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1 $

Show that $$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$ I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you
1
vote
2answers
150 views

How to perform a binomial expansion on $m*v^2$?

I have been told by a couple of folks in passing, one of whom was a mathematician, that through binomial expansion of $m*v^2$ (where v is used in place of c), that all 5 Major Forces (Strong Force, ...
4
votes
2answers
378 views

Binomial expansion, how to do them quickly?

I'm currently preparing for a test where I'm bound to do a couple of binomial expansions. Since I never encountered them in my formal education, I looked how to do them myself and found out: $ ...
0
votes
1answer
48 views

How to expense $(a+b)^\alpha$ into multinomial with $\alpha \in \mathbb{R}$?

As we all know, the binomial expension is as follows $$ (a+b)^2 = a^2 +2ab +b^2. $$ When the power number is a real number, not a integral, how to expense $(a+b)^\alpha$ into multinomial with $\alpha ...
1
vote
1answer
38 views

Direct proof that $\sum_{k=0}^m \binom{n}{k} \leq n^m$

Is there a short direct proof that $\sum_{k=0}^m \binom{n}{k} \leq n^m$ ? I can prove it by showing it is true for $m=2$ and then proving by induction. Is there a direct non-inductive proof?
1
vote
2answers
70 views

Closed form of the limit of a sequence (weighted average)

I have a sequence, which can actually be seen as Riemann-Stieltjes integration with a binomial distribution. $\rho \in (0,1)$. $$ S_N ...
2
votes
2answers
58 views

If $n = mp^e$ where $e$ is maximal, then $\binom{n}{p^e}$ is not divisible by $p$.

Let $n \geq 2$ be an integer, $p$ a prime with $p^e$ the highest power of $p$ dividing $n$. Then $\binom{n}{p^e}$ is not divisible by $p$. I think you can do it using this formula for ...
2
votes
1answer
90 views

Another binomial identity

Prove that $$(2m-1)^m=\sum_{j=1}^m(2j-1)C^m_j(2m-1)^{m-j},$$ where $C^m_j$ denotes binomial coefficient. I tried induction but got nowhere. I guess some simple binomial coefficient identity will do ...
0
votes
1answer
30 views

how comes this step ? inductive proof with binomial

I am sitting on this problem for couple of hours now but still cannot get the reason why the step which i marked is possible... how has $(n+1)$ disappeared here?
4
votes
3answers
114 views

Proof with binomial coefficient and kronecker delta

I want to prove that $$ \sum_{k=i}^n \binom{n}{k}\binom{k}{i}(-1)^{n-k}=\delta_{n,i} $$ Where $\delta_{n,i}$ is the Kronecker Delta, i.e. $\delta_{n,i}=0$ if $n \neq i$ and $\delta_{n,i}=1$ if $i=n$. ...
7
votes
2answers
301 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} ...
8
votes
3answers
160 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 ...
6
votes
3answers
201 views

Short and intuitive proof that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$

The simple inequality that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$ has a number of different proofs. But is there a particularly intuitive, short and elegant proof that uses the natural ...
1
vote
1answer
194 views

Theorem regarding greatest common divisor of certain Binomial coefficients.

Recently my friend asked following question- find the greatest common divisor of all binomial coefficient for a given n so the problem is in mathematical form ...
3
votes
1answer
98 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 ...
0
votes
1answer
65 views

Inequality with a sum and factorial

For a homework assignment we have the following question that I'm stuck on. Let $ 0 \leq y \leq 1 $ be given. $\forall m \in \mathbb{N}$, define $ \displaystyle S_m(y)=\sum_{k=0}^m \binom{m}{k}y^k$. ...
2
votes
1answer
73 views

Sum of series ${n\choose 2a}{a\choose 0}+ {n\choose {2a+2}}{{a+1}\choose 1} + {n\choose {2a+4}}{{a+2}\choose 2} + \ldots$

I wanted to check the rationality of the cosine function for some rational multiples of $\pi$. And I found out that, $\cos(n \cdot\arccos x)$ generates a polynomial in $x$ whose co-efficients have the ...
5
votes
1answer
300 views

Combinatorial Proof for Series of Stirling Numbers & Binomial Coefficients

I am struggling with the following question from an assignment for an introductory course to combinatorics. Show, by means of a combinatorial argument, that the following holds: ...
1
vote
1answer
81 views

Prove this conjecture

I come across an equality to complete a proof in my paper. I think it is true and I confirm by numerically experimenting with different parameter values, and analytically proving this with n=1,2. But ...
20
votes
1answer
442 views

Evaluating $\sum_{n=1}^{\infty} \frac{1}{n^{3} \binom{2n}{n}} $

Wolfram MathWorld states that $$ \sum_{n=1}^{\infty} \frac{1}{n^{3} \binom{2n}{n}} = \frac{ \pi \sqrt{3}}{18} \Big[ \psi_{1} \left(\frac{1}{3} \right) - \psi_{1} \left(\frac{2}{3} \right) \Big]- ...
0
votes
3answers
134 views

Compute $\sum_{k=0}^{1006}\binom{2013}{2k}$ using mathematical induction.

$$ \mbox{Compute}\quad\sum_{k=0}^{1006}{2013 \choose 2k} $$ Hi, I know that I have to use induction but I am kinda stuck here. any tips or suggestions would be great! Thanks
1
vote
2answers
296 views

How can I prove that $\sum \limits_{i=0}^k {n \choose i}(-1)^i = {n-1 \choose k}(-1)^k$?

I would like to prove this using a combinatorics argument. I have a feeling it involves the theorem $\sum \limits_{i=k}^n {i \choose k} = {n+1 \choose k+1}$. I'm not sure how to manipulate it to get ...
14
votes
4answers
374 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ I don't know how to prove this at all. Could you show me how ...
2
votes
3answers
411 views

Fermat's Combinatorial Identity: How to prove combinatorially?

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$ I don't have much experience with combinatorial proofs, so I'm grateful for all the hints. (Presumptive) ...
1
vote
1answer
34 views

Is there a better/closed form for the Cauchyproduct $A^k + A^{k-1}(A+I)/2 + A^{k-2}((A+I)/2)^2 + … +( (A+I)/2)^k$ ($A,I=A^0$ matrices)?

Is there a better/closed form for the Cauchyproduct $$A^k + A^{k-1}(A+I)/2 + A^{k-2}((A+I)/2)^2 + ... +( (A+I)/2)^k$$ ?Here $I$ is the identity and $A$ the upper subdiagonal filled with the unit ...
1
vote
2answers
148 views

Can I get a little help proving equality between a summation and integral?

Prove$$\sum_{k=0}^x \binom{n}{k}p^{k}(1-p)^{n-k} =(n-x)\binom{n}{x}\int_{0}^{1-p}t^{n-x-1}(1-t)^{x}dt.$$ Can someone show me the steps please? Here is the hint my book gave me: "Integrate by parts ...
6
votes
3answers
126 views

Bounds for $\binom{n}{cn}$ with $0 < c < 1$.

Are there really good upper and lower bounds for $\binom{n}{cn}$ when $c$ is a constant $0 < c < 1$? I know that $\left(\frac{1}{c^{cn}}\right) \leq \binom{n}{cn} \leq ...
2
votes
1answer
113 views

Proof involving $\sum_{k=0}^d {N \choose k}$; missing property to make this work

I solved this problem with the help of someone else who showed me a property that made this solution simple, but I now have to use a similar technique in a different problem and for the life of me I ...
0
votes
3answers
89 views

Asymptotic of binomial coeficient

I was doing a problem, and I found that I needed to calculate asymptotics for $$ \frac{1}{{n - k \choose k}}$$ Supposing $n = k^2$. Any help with this would be appreciated, thanks.
3
votes
2answers
116 views

“Upper summation” binomial identity: different version from “Concrete Mathematics”

The book "Concrete Mathematics: A Foundation for Computer Science", 2nd Edition - authored by Ronald L. Graham, Donald E. Knuth, Oren Patashnik - has, in its page 174, a table called: "Table 174 The ...
0
votes
3answers
904 views

Find a constant in a binomial expansion

Find the constant 'a' in the binomial expansion: $(1-2x)(1+ax)^{10}$ given that the coefficient of $x^6$ is $0$. I get 9.86, is this correct?
1
vote
2answers
66 views

Binomial Expansion involving two terms?

How would you find the 4th term in the expansion $(1+2x)^2 (1-6x)^{15}$? Is there a simple way to do so? Any help would be appreciated
0
votes
1answer
182 views

Induction proof involving prime factor and binomial coefficients

The question in my book is: Use induction on $r$ to prove that if $p$ is a prime integer, then $p$ is a factor $\binom{p}{r}$ for $r=1, 2, . . . , p-1$. I'm not really sure how to go about ...
0
votes
1answer
743 views

Finding the Greatest Coefficient in a Binomial Expansion?

when I do this question, I try not using the: $(n-k+1)/k * b/a$ formula, but rather the $T(k+1)/T(k) ≥ 1$ formula. However, when I do it like that, I get the wrong answer - which is probably a simple ...
1
vote
4answers
456 views

Binomial coefficient question?

I'm unsure how to do these types of questions, so any help would be great: Find the coefficient of $x^2$ in the expansion of $(x+1/x)^3(x-1/x)^5$ Thanks
1
vote
1answer
91 views

Binomial Theorem Coefficients?

Every time I do this question, I get $5$ as my answer, whilst the answers says $4$? Can someone please check this: "In the expansion of $(3+4x)^n$ the coefficients of $x^2$ and $x^3$ are in the ...
0
votes
2answers
64 views

Binomial and series with 2 coefficients

I would be very grateful if you would help me with this question: Find the sum : $$ \sum_{k=0}^{n}\binom{2n}{k} $$