Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
8
votes
2answers
111 views
A sum with binomial coefficients
Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$
4
votes
3answers
69 views
A binomial identity from Mathematical Reflections
Here is the problem:
Let $m,n$ be positive integers with $n>m$. Prove that
$\displaystyle\sum_{k=0}^{n} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$
This problem is O243 of ...
0
votes
2answers
17 views
Some algebraic inequalities with the binomial theorem.
I am working on proving the following limits.
1), $\lim_{n \to \infty} \sqrt[n]{n} = 1$
2), If $p >0$ and $\alpha \in \Bbb R$, then $\lim_{n \to \infty} {n^{\alpha}\over{(1+p)^n}} =0$
...
1
vote
4answers
144 views
Finding coefficient of a complicated binomial expression?
Say we have something like
$$
(x+2+y)^{23}
$$
How does one go about finding the co efficient of say $$ x^6y^7 $$
0
votes
1answer
39 views
What is the function given by $\sum_{n=0}^\infty \binom{b+2n}{b+n} x^n$, where $b\ge 0$, $|x| <1$
For a nonnegative integer $b$, and $|x|<1$, what is the function given by the power series
$$
\sum_{n=0}^\infty \binom{b+2n}{b+n} x^n.
$$
For $b=0$, this post shows
$$
\sum_{n=0}^\infty ...
5
votes
2answers
131 views
What's the intuition behind this equality involving combinatorics? [duplicate]
What is the intuition behind
$$
\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}
$$
? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ ...
0
votes
1answer
30 views
How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?
Short Version of the Question:
How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?
Long Version of the Question:
I'm currently attempting ...
1
vote
1answer
43 views
Weighted sum of ratio of partial sum of binomial coefficients
I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$,
$$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
4
votes
2answers
52 views
Binomial Coefficients Combinatorics
For a positive integers n, prove that
$$\displaystyle\sum\limits_{v=0}^n \frac{(2n)!}{(v!)^2 ((n-v)!)^2} = \binom{2n}{n}^2.$$
If somebody could please help me with this question, I would greatly ...
0
votes
1answer
52 views
Sum of binomial probabilities
One of my friends is building a game where the player will get questions from 6 different categories. Each category has a total of 50 questions. A single game consists of answering one question from ...
9
votes
3answers
128 views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove
$$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement ...
3
votes
2answers
26 views
Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem
So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
2
votes
3answers
65 views
Factorial Equality Problem
I'm stuck on this problem, any help would be appreciated.
Find all $n \in \mathbb{Z}$ which satisfy the following equation:
$${12 \choose n} = \binom{12}{n-2}$$
I have tried to put each of them ...
2
votes
1answer
47 views
Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$
Find the expected number of edges in $G \in \mathcal G(n,p)$.
Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. ...
1
vote
3answers
30 views
Proof that $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \frac{2^{m+1}-1}{m+1}$ [duplicate]
Recently I needed to compute $E[\frac{1}{X+1}]$ where $X\sim Bin(m, \frac 1 2)$.
While expanding, I came across the sum $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1}$, which I was unable to solve. Plugging ...
4
votes
2answers
81 views
Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$
I just found this identity but without any proof, could you just give me an hint how I could prove it?
$$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$
I know that $$2^n = ...
4
votes
3answers
81 views
Counting the numbers between $1$ and $1,000,000$ whose digits sum to $30$
What's the number of numbers between $1$ and $1,000,000$ whose digits sum is $30$?
So I thought of this as a stars and sticks problem, so in the case you have $35\choose 5$ numbers whose sum is ...
5
votes
2answers
57 views
Binomial probability with summation
Show that
$$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$
Attempt:
It becomes:
$$\sum_{k=0}^{m } \frac{\binom{m}{k}}{\binom{n}{k}}$$
Telescoping, pairing, binomial theorem don't ...
1
vote
3answers
120 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$$
...
10
votes
6answers
637 views
Proving a binomial sum identity
Mathematica tells me that
$$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$
Although I have not been able to come up with a proof.
Proofs, hints, or references are all ...
1
vote
0answers
23 views
Binomial Expansion problem error
I tried solving this question but failed.
a) Expand $(1+2x)^{1/4}$ in ascending powers of $x$ up to and including the term in $x^3$, simplifying each term as far as possible.
b) By substituting ...
2
votes
0answers
79 views
Prime numbers with binomial coefficients
Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n^{}\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$
for every $$j\in ...
4
votes
1answer
39 views
Binomial theorem for prime exponent
Could you explain to me why for prime $p$ we have the following?
$$(x+y)^p - (x^p + y^p)= x^p + \binom{p}{1}x^{p-1}y + \binom{p}{2}x^{p-2}y^2 + \binom{p}{p-1}xy^{p-1} + y^p.$$
I found it here: ...
5
votes
1answer
50 views
Prime numbers with binomial coefficients
Question:
Prove that for any prime $p>3$, the number $\binom{2p-1}{p-1}-1$ is divisible by $p^{3}$.
Attempt:
Since every integer that is relatively prime to p has a multiplicative inverse
modulo ...
2
votes
1answer
31 views
When are the binomial coefficients equal to a generalization involving the Gamma function?
Let $\Gamma$ be the Gamma function and abbreviate $x!:=\Gamma(x+1)$, $x>-1$.
For $\alpha>0$ lets generalize the binomial coefficients in the following way:
$\binom{n+m}{n}_\alpha:=\frac{(\alpha ...
2
votes
2answers
35 views
Prove that a sum converges to a trigonometric expression
$$2^n \cos \left (\frac{n \pi}{2} \right )=\sum_{k=0}^{n} (-1)^k \binom{2n}{2k}$$
I expanded the LHS and got $$\binom{2n}{0}-\binom{2n}{2}+\binom{2n}{4}-\binom{2n}{6}+\cdots+(-1)^{n}\binom{2n}{2n}$$
...
1
vote
4answers
548 views
Problem with binomial coefficients
I have a problem with the binomial coefficient $\binom{5}{7}$. I know that the solution is zero, but I have problems to reproduce that:
${\displaystyle ...
11
votes
0answers
202 views
Binomial sum of $n$ terms in closed form
Can we calculate the given combinatorial sum in closed form?
$$ \frac{\binom{2}{0}}{1}+\frac{\binom{4}{1}}{2}+\frac{\binom{8}{2}}{3}+\frac{\binom{16}{3}}{4}+\cdots+\frac{\binom{2^n}{n-1}}{n}$$
0
votes
0answers
27 views
Sum involving binomial cofficients [duplicate]
I want to Solve a binomial Series of type :
aC0*bCd + aC1*bc(d-1) -----------------(aC(k-1))*(bCd-(k-1))
Can anyone please suggest on how to reduce such series?
...
4
votes
1answer
30 views
$\frac{1}{4^n}\binom{1/2}{n} \stackrel{?}{=} \frac{1}{1+2n}\binom{n+1/2}{2n}$ - An identity for fractional binomial coefficients
In trying to write an answer to this question:
calculate the roots of $z = 1 + z^{1/2}$ using Lagrange expansion
I have come across the identity
$$
\frac{1}{4^n}\binom{1/2}{n} = ...
0
votes
1answer
33 views
Summing ratio of partial sums of binomial coefficients
I would like to approximate the following when $n \gg k$.
$\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$
The formula can be re-written ...
2
votes
1answer
67 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 ...
6
votes
3answers
54 views
Show that ${-n \choose i} = (-1)^i{n+i-1 \choose i} $
Show that ${-n \choose i} = (-1)^i{n+i-1 \choose i} $. This is a homework exercise I have to make and I just cant get started on it. The problem lies with the $-n$. Using the definition I get:
$${-n ...
0
votes
2answers
27 views
standard deviation of a certain distribution
If I have a list of N outcomes of drawing a number from the set {-1\$,+1\$}, and I know that the probability of getting (in a single draw) (-1\$) is p, and probability of getting (in a single draw) ...
5
votes
4answers
350 views
Why does this expected value simplify as shown?
I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is:
...
5
votes
2answers
88 views
Is there a closed form expression for the first half of the Binomial series?
I'm looking for a closed form expression for the sum
$P_n(x) =\sum_{0\leq k\leq n/2}\binom{n}{k}x^k$,
where $n$ is a given positive integer and $k$ runs over nonnegative integers between $0$ and ...
0
votes
1answer
37 views
Help with a question on binomial
Prove that $$\sum_{r=1}^{k}(-3)^{r-1}\dbinom{3n}{2r-1}= 0,$$ where $k=\frac{3n}{2}$, and $n$ is an even positive integer
1
vote
2answers
40 views
Summations with binomial coefficients:$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$
Can someone help me solve this equation? How to prove that $$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$
2
votes
2answers
66 views
Looking for combinatorial identity: $\sum\limits_{j=0}^k{n \choose k-j}{m \choose j}$ [duplicate]
Is there a nicer closed form expression for the following expression? $$\sum_{j=0}^k{n \choose k-j}{m \choose j}$$
4
votes
1answer
363 views
Calculation of the moments using Hypergeometric distribution
Let vector $a\in 2n $ is such that first $l$ of its coordinates are $1$ and the rest are $0$ ($a=(1,\ldots, 1,0, \ldots, 0)$). Let $\pi$ be $k$-th permutation of set $\{1, \ldots, 2n\}$.
Define
...
2
votes
1answer
69 views
A combinatorial identity
Let $m$ be a positive integer. I have trouble proving that
$$\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$$
Anyone?
2
votes
3answers
105 views
combinatorial argument and by induction proof
Let n be a fixed natural number. Show that:
$$\sum_{r=0}^m \binom {n+r-1}r = \binom {n+m}{m}$$
(A): using a combinatorial argument and (B): by induction on $m$?
3
votes
1answer
54 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
37 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 ...
10
votes
2answers
175 views
Asymptotics of the sum of squares of binomial coefficients
We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
0
votes
1answer
65 views
Is this binomial coefficient identity already known?
$ \sum_{k=r}^{n} {n \choose k} = \sum_{k = r - 1}^{n-1}{k \choose r -1}2^{n-1-k} $
The proof is trivial but I haven't seen this identity anywhere. Perhaps it's a special case of a more general ...
9
votes
4answers
144 views
Binomial Theorem Identities
What's the actual difference between these two formulas (they're both in the chapter regarding binomial theorem). They're from two different textbooks :
$${n\choose k}+{n\choose k+1}={n+1\choose ...
4
votes
3answers
82 views
Distributing identical objects to identical boxes
We have 6 identical things to be distributed in 4 identical boxes such that empty boxes are allowed the find the number of ways to distribute the things ?
1
vote
2answers
52 views
Sum of square binomial coefficients [duplicate]
Please feel free to close this is necessary as I didn't see exactly this question (some variations that I tried but didn't seem to apply.
Prove:
$$\sum_{k=0}^{n}{\binom{n}{k}^2}=\binom{2n}{n}$$
I ...
1
vote
2answers
49 views
Combinatorial Proof of Binomial Coefficient Identity [duplicate]
Consider the sum $\displaystyle\sum_{j=r}^{n+r-k} \binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}$
I am looking to show this identity combinatorially. Is the general idea perhaps to remove j from n ...
