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
1answer
46 views

Prove combination identity

$ \sum_{k=0}^n {2k \choose k} {2n-2k \choose n-k} = 4^n $ I tried with mathematical induction only to fail. Is this formula related to some special function like Beta, Gamma, etc?
3
votes
1answer
38 views

How to simplify a sum with binomial coefficients multiplied by $k^3/2^k$?

The sum is $$\sum_{k=5}^{\infty}\binom{k-1}{k-5}\frac{k^3}{2^{k}} $$ The first thing I thought of was the binomial coefficient. So I re-indexed it ...
3
votes
2answers
75 views

Integer sum as binomial coefficient

What's the rule for expressing integer sums as binomial coefficients? That is, for $p=1$ it is $$\sum_{n=1}^N n^p = {{N+1}\choose 2} $$ What is it for higher powers?
3
votes
4answers
128 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
3
votes
2answers
35 views

show that these two equation holds by binomial theorem

I know the binomial theorem, but I have no idea how to simplify this. I tried to write it as (y+x)^n+(y+x)^n-(y+x)^0+(y+x)^n-(y+x)^1+...+(y+x)^n-(y+x)^(n-1), but it didnt work out.
3
votes
1answer
44 views

A combinatorics question on a sequence of binomial coefficents

On a past-paper of a Combinatorics exam I will be taking they ask the question: Prove that for $k$ odd and greater than 1, the sequence of numbers $\binom{k}{1}, \binom{k}{2}, ..., ...
3
votes
2answers
130 views

$\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$?

Is it true that $\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$ ? I feel that it is true because if we define $H_1 (x,r)=rx(1+x)^{r-1}$ , and $H_{m+1}(x,r)=x \dfrac d ...
3
votes
3answers
71 views

undetermined coefficients. What am I doing wrong?

I am having some trouble to solve the following differential equation for the undetermined coefficient: $$ y''+2y'+y=xe^{-x} $$ I have been watching some videos on youtube and done some reading but ...
3
votes
2answers
80 views

Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
3
votes
1answer
137 views

Find the coefficient of $x^m$ in the expansion $(1 + ax + bx^2)^n$

Find the coefficient of $x^m$ in the expansion of $(1 + ax + bx^2)^n$ One approach would be: Let $p = 1+ax$ and $q = bx^2$ Now expand $(p+q)^n$ and then expand $p$ and $q$ individually. But ...
3
votes
3answers
137 views

Stirling Binomial Polynomial

Let $\{\cdot\}$ denote Stirling Numbers of the second kind. Let $(\cdot)$ denote the usual binomial coefficients. It is known that $$\sum_{j=k}^n {n\choose j} \left\{\begin{matrix} j \\ k ...
3
votes
1answer
153 views

How do i reduce this expression of binomial coefficients

I was solving a problem and am stuck with this expression. Any leads on how can I simplify this expression? $$\frac{{\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} ...
3
votes
2answers
98 views

What is the exponent of the last term of $(2x^2+3y^3)^{10}$?

What is the exponent of the last term of: $$(2x^2+3y^3)^{10}$$ Hi! I'm sorry if this question seems a bit amateurish. I'm quite confused with this question that was asked in a quiz about binomial ...
3
votes
1answer
439 views

Number of possible triangle for the given triangle.

An equilateral triangle has n equally spaced dots on each side. How many triangles can be formed (of any size)? Analysis If there are n dots on each side then total no of dots =n(n+1)/2 Number of ...
3
votes
1answer
476 views

Combinatorial Argument

Can you give a Combinatorial argument that $$\binom{3n}{3}=3\binom{n}{3}+(3)(2)\binom{n}{2}\binom{n}{1}+\binom{n}{1}\binom{n}{1}\binom{n}{1}?$$
3
votes
3answers
99 views

Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$ \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
3
votes
3answers
55 views

Sum of products of binomial coefficients

In a proof I've come across the following identity: $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$ I see that it's right, when plugging in numbers, but I don't see the ...
3
votes
2answers
94 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...
3
votes
3answers
128 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
3
votes
1answer
47 views

Binomial coefficient difference

I have the following difference of binomial coefficients: $$f(m)={m+n\choose n}-{m-d+n\choose n}$$ I believe the following two things should hold true: For $m$ large enough, $f(m)$ is a polynomial ...
3
votes
2answers
76 views

$2^n=C_0+C_1+\dots+C_n$

Could anyone give me hints for this one? $2^n=C_0+C_1+\dots+C_n$ Thats all I can say and I know tricks like integrating or differentiating both side and then put $x=1$ or what ever we need. but ...
3
votes
3answers
174 views

Find the 100th derivative of $x \sinh(2x)$

If $f(x) = x \sinh(2x)$, find $f^{({100})}(x)$. My (Incorrect) working so far: Using Leibniz' Formula for derivatives: $$(fg)^{(n)}=\sum_{k=0}^n{n\choose k}f^{(k)}g^{(n-k)}$$ ...
3
votes
2answers
84 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
1answer
88 views

Bertrand's postulate proof

Regarding http://michaelnielsen.org/polymath1/index.php?title=Bertrand%27s_postulate I think the last inequality should be $4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}$. But even when the RHS is decreased from ...
3
votes
1answer
70 views

Evaluating Sums Combinatorially

Consider the following finite sums: (1) $\sum k(k!)$ for k from 1 to n (2) $\sum (k-1)(n-k)$ from 1 to n I am trying to determine how to evaluate these sums combinatorially. It seems the first is ...
3
votes
3answers
282 views

Induction proof of $\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$

Does anynone have some hints to prove the following equation by induction for all $n\geq 1$ and $m\in\mathbb{Z} $ $$\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$$ use for ...
3
votes
1answer
50 views

Binomial coefficient help?

I'm studying for my exams and would appreciate any help with binomial coefficients. I think I got the idea but having trouble with a specific one: Q) If a there are 11 dogs and 9 cats: a) How many 7 ...
3
votes
3answers
114 views

Probability someone's phone will ring during a movie?

Trying to figure out what the probability is that in a room of 200 people what the probability that at least one will get a phone call during a certain time window... In this case 2 hours ...
3
votes
1answer
135 views

Choosing k Multisets from [n]

We are to play a lottery game where five numbers are drawn out of [90], but the numbers drawn are put back into the basket right after being selected. To win the jackpot, one must have played the same ...
3
votes
2answers
275 views

Lower Bound of Central Binomial Coefficients

I would like to prove by induction the following inequality: $\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1. Any hints?
3
votes
2answers
124 views

A combinatorial exercise

Suppose to have a jar containing 100 coins. I want to count the possibile configuration with pennies, nickels, dimes, quarters and half-dollars. This is what I have done, but I realized that it's ...
3
votes
1answer
237 views

binomial expansion

$\displaystyle \binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}$ $\displaystyle \left(1+x\right)^{n} = \left(1+x\right)\left(1+x\right)^{n-1}$ how do I use binomial expansion on the second equations ...
3
votes
1answer
372 views

Finding a simple expression - Binomial Theorem

How does one find a simple expression of the one below applying the binomial theorem: $$\sum_{k=1}^n k \cdot 2^k{ n \choose k}$$ Edit: $\frac{d}{dx}(x^k)=kx^{k-1}$ $(1 + x)^n = \sum_{k=0}^n { n ...
3
votes
1answer
23 views

Show by committee selection argument

First post in Stack Exchange and feel bad to be in need of help. But, I'm having a hard time understanding this one or rather showing the argument. $\binom{n}{k} = \binom{n-2}{k-2} + ...
3
votes
1answer
51 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
3
votes
1answer
45 views

How prove $\binom{n}{m}\le\left(\frac{en}{m}\right)^m$ [duplicate]

Show that $$\binom{n}{m}\le\left(\dfrac{en}{m}\right)^m$$ where $0<m\le n,m,n\in N^{+}$ My idea: since ...
3
votes
1answer
230 views

Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$

So, I wonder what is the evaluation of $$\sum_{k = 0}^{n} {n\choose k} k^m\text{,}\qquad (*)$$ where $m,n\in \mathbb{N}$. One of my tries: knowing that $$k^m = \sum_{j = 0}^{m}\text{S}(m,j)\cdot ...
3
votes
1answer
108 views

A generalization of the Vandermonde's convolution

I need to find a closed formula for the following sum: \begin{equation} \sum_{i=0}^{n}i^{k}\left(\begin{array}{c} n\\ i \end{array}\right)\left(\begin{array}{c} n^{2}-n\\ c-i \end{array}\right) ...
3
votes
1answer
114 views

Pascal Triangle general formula

I'm working on a presentation on the Binomial Theorem for my Algebra 2 class and while writing Pascal's Triangle, I came across one of the properties that I haven't seen in a while. That being ...
3
votes
1answer
107 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 ...
3
votes
2answers
443 views

German tank problem, simple derivation [duplicate]

I was reading the recent question on the German tank problem, and had trouble with one of the derivations in this section. $$\sum_{m=k}^N m \frac{\binom{m-1}{k-1}}{\binom N k} = ...
3
votes
1answer
111 views

Vandermonde-like sum

I know a Vandermonde's identity as $$ \sum_{i=0}^c {a \choose i} {b \choose c-i} = {a+b \choose c} $$ $$ a, b, c \in \mathbb{N} $$ I am looking for a way to simplify these expressions: $$ ...
3
votes
1answer
269 views

Average absolute value of sum with Rademacher random variables

Let $a_1, \ldots, a_n $ be independent Rademacher random variables with distribution $P(a_i=1) = P(a_i=-1) = \frac 12$. Estimate from below $$E \left|\sum_{i=1}^n a_i\right|.$$ I've reduced this ...
3
votes
2answers
178 views

Proving Binomial Idenity without calculus

How to establish the following identities without the help of calculus: For positive integer $n, $ $$\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r=\sum_{1\le r\le n}\frac1r $$ and $$\sum_{0\le r\le ...
3
votes
2answers
691 views

Binomial theorem in probability

We know according to binomial probability theorem , $$P= \binom{n}{r} p^r (1-p)^{n-r} \tag{1}$$ Now If I flip a coin 10 times and want to get the probability for 4 heads then we get according to the ...
3
votes
1answer
215 views

Approximating hypergeometric distribution with poisson

I'm am currently trying to show that the hypergeometric distribution converges to the Poisson distribution. $$ \lim_{n,r,s \to \infty, \frac{n \cdot r}{r+s} \to \lambda} \frac{\binom{r}{k} ...
3
votes
1answer
61 views

An equality involving binomial coefitients

I am wondering why formula $$\sum_{j=k}^n\binom{n}{j}(-1)^j = (-1)^k\binom{n-1}{k-1} $$ is correct only for $1<k<n+1$. Could it be extended to $0<k<n+1$? I found this formula here.
3
votes
2answers
274 views

Sum of product of binomial coefficients $ = (-1)^n$

Based on the binomial expansion of $(1+x)^n$, show that: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$$ This is a question from a very old high school exam paper I came across. It ...
3
votes
2answers
67 views

Identity of binomial series with factorial.

I'm looking for a simple identity for the formula: $$ \sum_{k = 0}^{p} \binom{p}{k} \cdot k! \cdot x^k $$ In words, I have $p$ "players" who can choose to play or not (every player is represented by ...
3
votes
1answer
131 views

Is $\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k} \sim\frac{n^{2n}}{2\pi} $?

How can you compute the asymptotics of $$T=\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k}\;?$$ This is related to Asymptotics of sum of binomials . I attempted to simply use Stirling's ...