Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
3
votes
0answers
25 views
Binomial coefficient sum over top index
I am trying to evaluate a sum over binomial coefficients which is giving me some problems. Specifically I want to calculate:
$$\sum_{r=0}^{c-1}\binom{r+n}{n}\frac{1}{c-r}$$
My main thought was to ...
1
vote
4answers
77 views
Is $\sum^{n-1}_{k=1}{n\choose k}x^{n-k}y^k$ always even?
Is
$$ f(n,x,y)=\sum^{n-1}_{k=1}{n\choose k}x^{n-k}y^k,\qquad\qquad\forall~n>0~\text{and}~x,y\in\mathbb{Z}$$
always divisible by $2$?
1
vote
2answers
33 views
Binomial coefficient series
I'm practicing for my maths term test mainly on binomial coefficients. I can't seem to find out how to prove the following identity. Any advice?
$$ \sum\limits_{k=1}^n (-1)^{k+1} k{{n}\choose k} = 0 ...
2
votes
3answers
52 views
Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$
Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$
I ...
2
votes
0answers
48 views
+50
On a sum related to alternating sign matrices
I'm trying to prove that
$$A_{n,k} = \binom{n+k-2}{k-1}\frac{(2n-k-1)!}{(n-k)!}\prod_{j=0}^{n-2}\frac{(3j+1)!}{(n+j)!}$$
implies
$$A_n = \sum_{k=1}^nA_{n,k}=\prod_{j=0}^{n-1}\frac{(3j+1)!}{(n+j)!}.$$
...
0
votes
1answer
32 views
Binomial sum of derivatives
I would like to know the result of the following sum:
$$\sum_{p=0}^m \binom{m}{p}(-1)^{p-1}\frac{\partial^{p-1}}{\partial x^{p-1}}f(x)\cdot(-1)^{m-p-1}\frac{\partial^{m-p-1}}{\partial ...
3
votes
1answer
39 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.
10
votes
6answers
129 views
A limit on binomial coefficients
Let $$x_n=\frac{1}{n^2}\sum_{k=0}^n \ln\left(n\atop k\right).$$ Find the limit of $x_n$.
What I can do is just use Stolz formula. But I could not proceed.
0
votes
2answers
19 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$
...
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
132 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$ ...
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
32 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 ...
0
votes
1answer
59 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 ...
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 ...
3
votes
2answers
29 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, ...
1
vote
3answers
32 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
82 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
84 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 ...
10
votes
3answers
142 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 ...
5
votes
2answers
58 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
132 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$$
...
8
votes
2answers
119 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}.$$
2
votes
3answers
67 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 ...
1
vote
0answers
25 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 ...
4
votes
1answer
42 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: ...
2
votes
0answers
84 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 ...
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
2answers
37 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}$$
...
2
votes
1answer
36 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 ...
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
34 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 ...
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 ...
6
votes
3answers
57 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
28 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) ...
2
votes
1answer
70 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 ...
2
votes
1answer
54 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}$. ...
2
votes
2answers
71 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}$$
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
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?
3
votes
1answer
55 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.
2
votes
3answers
110 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
2answers
38 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 ...
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
149 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
85 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
54 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 ...
10
votes
2answers
180 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 ...
1
vote
2answers
52 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 ...
