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
67 views

Binomial distribution false reasoning

While reading the answer of a previous question Binomial Distribution Question (Exactly/At Least $x$ Trials for Success), it got me thinking a little. I know the reasoning must be flawed somewhere, ...
1
vote
1answer
100 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
24
votes
2answers
556 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
6
votes
4answers
906 views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
2
votes
4answers
866 views

How to determine the coefficient of binomial

Suppose I have $\left(x-2y+3z^{-1}\right)^4$ How to determine coefficient binom of $xyz^{-2}$? I've tried using trinominal expansion like this: $\displaystyle \frac{4!}{1!1!1!} (1)^1 (-2)^1 (3)^2$
3
votes
1answer
165 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
0
votes
1answer
134 views

Combinatorial approach to $\sum\limits_{i=1}^n \binom{i+r-1}i$ [closed]

$$\sum_{i = 1}^n \binom{i+r-1}{i}$$ I want to solve above sum combinatorially.
1
vote
2answers
82 views

${{p^k}\choose{j}}\equiv 0\pmod{p}$ for $0 < j < p^k$

$${{p^k}\choose{j}}\equiv 0\pmod{p}.\ \ \ \text{for $0 < j < p^k$ and p is prime}$$ I can show this for $k=1$ using the fact that in denominator all numbers are less than $p$. I need hint ...
1
vote
1answer
207 views

Why binomial distribution for particles in container?

I read in an introduction to information theory and entropy There is N particles, which can move across a million of boxes. What does author mean by Consider the number of configurations with ...
0
votes
1answer
104 views

identity for squared binomial coefficient

I was wondering if there is an identity for squaring a binomial coefficient. I know there is one with converting it to a linear equation, but I am looking to stay at a "coefficient" level. something ...
3
votes
2answers
203 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 ...
0
votes
1answer
210 views

Evaluating a sum with binomial coefficients

I have come across the following sum evoking the binomial theorem: $$\sum_{k=1}^n {n \choose k} \frac{1}{k^r} a^k b^{n-k},$$ where $r > 0$ is a positive real constant and $a,b \in \mathbb{R}$ are ...
1
vote
1answer
243 views

Change of variable in an infinite sum

I'm currently trying to understand a derivation from WolframMathWorlds. I got to step 6 where a change of variable happens. You can see the equation here. I understand everything except how they get ...
1
vote
1answer
72 views

Proving that the eigenvectors of this class of matrices are the binomial coefficients

So I'm trying to figure out the behavior of this system: you have $N$ coins, and every step, you choose one of the coins randomly and flip them. Now we imagine a bazillion of these systems. We call ...
0
votes
1answer
121 views

A few questions relating to counting for midterm practise exam?

I'm doing some questions for my midterm practise exam (multiple choice) for discrete structures and would appreciate some help (My answer is bolded): Using the 26-letter alphabet {a,b,c,...,z}, how ...
5
votes
1answer
172 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
1
vote
1answer
112 views

$P(X-np>n\varepsilon)\leq E\{e^{\lambda \cdot (X-np-n\varepsilon) }\}$

For $X \mathtt{\sim} \text{Bin}(n,p), \lambda > 0, \varepsilon > 0$, how do you show the following? $$P(X-np>n\varepsilon)\leq E\{e^{\lambda \cdot (X-np-n\varepsilon) }\}$$ Unless I made some ...
0
votes
1answer
162 views

Evaluate $\sum_{k=0}^nk(n-k)$

Evaluate $\sum_{k=0}^nk(n-k)$ I have $\sum_{k=0}^nkn-\sum_{k=0}^nk^2$ then im suppose to use the identity of $\left( \begin{array}{c} r \\ r \end{array} \right)+\left( \begin{array}{c} r+1 \\ r ...
5
votes
4answers
325 views

Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$

I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of ...
0
votes
3answers
162 views

Prove an upper bound for the binomials

This is (supposed to be) an upper bound on the binomial coefficient: $$ \binom{n}{k} \le \frac{n^n}{k^k(n-k)^{n-k}}$$ If we prove it by induction for all integers $0 \le k \le n/2$, we can easily ...
9
votes
4answers
318 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 ...
1
vote
1answer
44 views

value of an integral between 0 and 1 by using the binomial theorem

How can one find the value of the integtral with an integration by parts I found the value m!*n!/(m+n+1)! but still I cannot see how to use the binomial theorem here. Greetings and thanks in advance ...
1
vote
1answer
58 views

About the number of the elements of a set related with binomial coefficients

For $N\in\mathbb N$, let $$P_l(N)=\# \{(n,m)|0\le n\le N, 0\le m\le n,\binom{n}{m}\not\equiv 0 \mod l\}.$$ Suppose that $\binom{n}{0}=1$ for $n\ge 0$ and that $\# S$ represents the number of the ...
1
vote
2answers
735 views

Pascal's formula and Binomial Coefficients

Prove Pascal's formula by substituting the values of the binomials coefficient as given in the equation $$\binom nk= \frac{n!}{k!\,(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}.$$ I guess I ...
0
votes
1answer
253 views

How do I compute the summation where k is greater than or equal to $0$ of $\frac{1}{k+1}{99 \choose k}$ ${200 \choose 120-k}$

How do I compute $$ \sum_{k=0}^{\infty}\frac{1}{k+1}\binom{99}{k}\binom{200}{120-k}. $$ I have expanded it to this: $$ \frac{1}{k+1}\cdot\frac{99!}{k!(99-k)!}\cdot\frac{200!}{(120-k)!(80+k)!} $$ but ...
4
votes
4answers
4k 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 ...
0
votes
1answer
428 views

How do I compute the summation of ${80\choose k}\cdot {k+1 \choose 31}$?

How do I compute the summation of ${80 \choose k}{ k+1 \choose 31}$? I have it expanded in this way $\frac{80!}{k!(80-k)!} \cdot \frac{(k+1)!}{31!(k-30)!}$ Is there a way I can write this as an ...
3
votes
1answer
87 views

Is this equation about binomial-coefficients true?

Question : Is the following true? $$\sum_{r=k}^{n}\frac{\binom{q}{r}}{\binom{p}{r}}=\frac{p+1}{p-q+1}\left(\frac{\binom{q}{k}}{\binom{p+1}{k}}-\frac{\binom{q}{n+1}}{\binom{p+1}{n+1}}\right)$$ for ...
7
votes
2answers
5k 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 ...
1
vote
3answers
448 views

Is there a closed form for the sum $\sum_{k=2}^N {N \choose k} \frac{k-1}{k}$?

I am interested in finding a closed form for the sum $\sum_{k=2}^N {N \choose k} \frac{k-1}{k}$. Does anyone know if there is some Binomial identity that might be helpful here? Thank you.
2
votes
2answers
375 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
170 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
2answers
12k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
4
votes
1answer
169 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
96 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: ...
2
votes
5answers
101 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 ...
-1
votes
1answer
167 views

Understanding a proof of the fact that $\binom{n}{k}$ is always a natural number.

Original source of question and solution. Question is on the left, answer is on the right. Question: Notice that all the numbers in Pascal's triangle are natural numbers. Use part (a) to prove by ...
1
vote
2answers
80 views

Prove $\sum_{i=1}^{n}i\left(\begin{array}{c} n\\ i \end{array}\right)=n2^{n-1}$ using induction.

I have already derived the formula $\sum_{i=1}^{n}i\left(\begin{array}{c}n\\i \end{array}\right)=n2^{n-1}$ directly just by doing some algebraic manipulations to the summand, which is indeed proves ...
2
votes
1answer
206 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
668 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 ...
2
votes
0answers
41 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
112 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
105 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
422 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
156 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 ...
13
votes
4answers
433 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
321 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, ...
5
votes
2answers
1k 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
52 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 ...
2
votes
1answer
45 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?