Tagged Questions
2
votes
3answers
51 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 ...
1
vote
0answers
34 views
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)!}.$$
...
3
votes
1answer
38 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.
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 ...
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
83 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
141 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
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
131 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$$
...
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 ...
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 ...
2
votes
1answer
68 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
2answers
70 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}$$
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
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
146 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
84 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
51 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 ...
1
vote
1answer
39 views
Manipulation of Geometric Series and Binomial Theorem
I was just hoping to confirm that the following manipulations make sense:
Say I begin with $\frac{1}{(1-x)^n}$. Then we have $(1-x)^{-n} = $$\sum$ $-n\choose k$ $(-x)^k$ = $\sum$ $(-1)^k$ $n+k-1 ...
3
votes
0answers
44 views
In Pursuit of a Broader Understanding of Complicated Binomial Coefficient Sums
$$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$
The above identity was posted once before by me, however, all results were obtained numerically exploring the identity rather than understanding ...
3
votes
1answer
43 views
Combinatorial Proof of a Binomial Identity
$$\sum_k {m\choose k} {n \choose k} = {m+n \choose n}$$
In this identity we seem to be choosing subsets that do $\it not$ contain k of type m and type n for all possible k. In the style of ...
3
votes
3answers
47 views
Constructing A Combinatorial Proof of a Binomial Identity
Consider:
$$\sum_{k=0}^m \binom{n+k}k = \binom{m+n+1}m.$$
The LHS counts the number of subsets whose size is equal to its maximal element plus some fixed value. Alternatively, we can choose how ...
3
votes
1answer
51 views
Combinatorial Proof of a Binomial Coefficient Identity
I am looking to prove the following identity combinatorially:
$\sum_k$ $n \choose 2k$ $2k \choose k$ $2^{n-2k}$ = $2n \choose n$
Clearly the RHS counts the number of ways to choose n elements ...
0
votes
1answer
34 views
Combinatorial Proofs for Simple Binomial Identities
Consider $\sum k(k-1)(k-2)$ $n\choose k$ = $n(n-1)(n-2)$ $n-3 \choose 3$ for k >= 0 n >=3
I had initially thought the right side counted the ways to select three distinct objects from n and then ...
2
votes
1answer
37 views
Proof of asymptotic expansion of binomial coefficient
here's the problem I'm currently stuck on:
Prove that (for $k$ fixed):
$$\binom{N}{k}=\frac{N^{k}}{k!}+O(N^{k-1})$$
I know that:
$$\binom{N}{k}\le\frac{N^{k}}{k!}$$
But I'm not sure how to ...
4
votes
4answers
108 views
Evaluating Sums Algebraically or Combinatorially
Consider
(1) $$\sum_{k=0}^{n}\binom{n}{k}2^{k-n}$$
(2) $$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$
These sums appear too difficult (in my mind) to evaluate combinatorially. What are some ...
3
votes
1answer
53 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
4answers
57 views
Combinatorial Proof
I have trouble coming up with combinatorial proofs. How would you justify this equality?
$$
n\binom {n-1}{k-1} = k \binom nk
$$
-2
votes
2answers
105 views
Finding the coefficient of $x^5 y^7 z^4$ in $(2x+3y+5z)^{16}$ [closed]
What is the coefficient at $x^5 y^7 z^4$ in $(2x+3y+5z)^{16}$?
0
votes
0answers
113 views
proving inequality for combinatorial sum
If somone can prove the following for every $d\leq r$ (for $d=0,1$ its easy, see below, the case d=r may be also simple, I didn't find something helpful)
$$\frac{(d!)^2}{2^{n-2d}}\sum_{k=0}^{n}{n ...
5
votes
3answers
157 views
Calculate $\sum\limits_{k=801}^{849}{ \binom {2400} {k}} $
Is any formula which can help me to calculate directly the following sum :
$$\sum_{k=801}^{849} \binom {2400} {k} \text{ ? } $$
Or can you help me for an approximation?
Thanks :)
0
votes
2answers
27 views
How to combine the fraction over the common denominator?
How to combine the fractions on the righthand side over the common denominator:
$\frac{(n+1)!n!}{k!(k-1)!(n-k+1)!}=\frac{(n+k)n!(n-1)!}{k!(k-1)!(n-k)!}+\frac{n!(n-1)!}{(k-1)!(k-2)!(n-k+1)!}$
3
votes
3answers
84 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 ...
4
votes
2answers
69 views
Finding a closed form expression for this sum [duplicate]
For non-negative $n$, find
$$
\sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}.
$$
I can't figure this out. Any ideas?
3
votes
2answers
47 views
Expression for power of a natural number in terms of binomial coefficients
Is there a general expression for the pth power of a natural number k in terms of binomial coefficients?
I found this identity in a high-school text, which was obtained by simply equating ...
1
vote
2answers
58 views
How many strings of length 17 contain at least 5 ones? [duplicate]
This is for binary strings, as in 1's and 0's.
My friend said:
$\sum\limits_{k=5}^{17} {17 \choose k} = 127858$
While my answer was much longer to show but I believe is correct:
Basically for ...
4
votes
4answers
137 views
Proving that $\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$
I have to prove that:
$$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$
I tried to open up the right side with Pascal's definition that:
$$ { n \choose k} = {n-1 \choose {k}} + {n-1 ...
-2
votes
1answer
88 views
Showing that the Lah numbers satisfy $L(n + 1, k) = (n + k)L(n, k) + L(n, k - 1)$
Show that the Lah numbers satisfy the following recurrence relation:
$$L(n + 1, k) = (n + k)L(n, k) + L(n, k - 1).$$
3
votes
0answers
32 views
Proving two summations equivalent [duplicate]
Let $h_n$ be an infinite sequence. I need to show that:
\begin{align}\dfrac{1}{1+x}H\left(\dfrac{x}{1+x}\right) = \sum\limits_{k=0}^\infty \sum\limits_{i=0}^k(-1)^{k-j}{k\choose i}x^kh_i
\end{align}
...
4
votes
2answers
121 views
How many 9 letter strings are there that contain at least 3 vowels?
I'm studying for my exams and stuck on this one question.
The way I'm thinking of doing this is by:
$$26^9 - \binom{26}3-\binom{26}2-\binom{26}1-\binom{26}0= 5,429,503,676,728$$
But that seems ...
1
vote
3answers
58 views
Negative Binomial Coefficients
Is it true that Pascal's Rule holds for binomial coefficients with a negative upper index?
With $n = -1$ and $k = 3$, for example, it appears not to hold.
4
votes
3answers
111 views
Find a simple formula for
$$\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+...+\binom{n}{n-1}\binom{n}{n}$$
All I could think of so far is to turn this expression into a sum. But that does not necessarily simplify the ...
