Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
2
votes
1answer
61 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
45 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
81 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
32 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
62 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 ...
8
votes
4answers
132 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
53 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
34 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 ...
8
votes
2answers
125 views
+50
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
34 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 ...
2
votes
3answers
71 views
To prove $\sum_{i=0}^k\binom{n}{3i}\leq \frac{1}{3}(2^n+2)$
If $n\in \mathbb{Z^+}$ and $k$ is the largest integer for which $3k\leq n$, then is it true that $\sum_{i=0}^k\binom{n}{3i}\leq \frac{1}{3}(2^n+2)$?
My work: We can break this into two cases: ...
1
vote
1answer
33 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
41 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
38 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
40 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
46 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 ...
3
votes
0answers
39 views
Sum with binomial coefficients and a square root
I encountered this sum from working on an integral:
$$\sum_{k=0}^{n}\binom{n}{k}(-1)^{k}\sqrt{k}$$
I don't think it can be written as a hypergeometric function, because of this square root.
Does ...
2
votes
1answer
20 views
Finding the coefficient in the closed form of the generating function
I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form
\begin{eqnarray*}
...
0
votes
1answer
23 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 ...
1
vote
2answers
30 views
$\sum_{i=0}^n (-1)^k \cdot C(n,k)$
Use the Binomial Theorem to Show
$$\sum_{i=0}^n (-1)^k \cdot C(n,k)$$
I'm not sure where to start here . . . I know it is missing an $a^{n-k}$ and a $b^{k}$ term that maybe I should set to be 1?
3
votes
4answers
89 views
Find the Sum $1\cdot2+2\cdot3+\cdots + (n-1)\cdot n$
Find the sum $$1\cdot2 + 2\cdot3 + \cdot \cdot \cdot + (n-1)\cdot n.$$
This is related to the binomial theorem. My guess is we use the combination formula . . .
$C(n, k) = n!/k!\cdot(n-k)!$
so . . ...
2
votes
1answer
29 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
97 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
50 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
2answers
59 views
How can I solve $\sum\limits_{i = 1}^k i \binom{k}{i-1}$
If anyone could help with the steps in solving this summation. I've been playing with it most of the day. It started from me trying to prove $\sum\limits_{i=0}^{k+1} \left(i\binom{k+1}{i}\right) = ...
2
votes
4answers
59 views
Binomial Coefficients for $(x+1)^4$
Find $(x + 1)^4$ using binomial coefficients.
I'm confused as to how to start this, as I thought binomial coefficients were things like $9 \choose 2$.
0
votes
1answer
29 views
Sum of $\sum\limits_{m = 1}^\infty {\frac{{m(m + 1)}}{2}} {p^{\frac{{m(m - 1)}}{2}}}\left( {1 - {p^m}} \right)$
I'm trying to find if the following sum is converging to some known identity:
$$\sum\limits_{m = 1}^\infty {\frac{{m(m + 1)}}{2}} {p^{\frac{{m(m - 1)}}{2}}}\left( {1 - {p^m}} \right)$$
$$ p \in ...
0
votes
2answers
29 views
Binomial Theorem and number of subsets
I'm reading my textbook on binomial theorem and there's an example question with the solution. I don't understand it. Can someone please explain? Thanks in advance.
How many subsets are there of a ...
3
votes
4answers
49 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
92 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}$?
3
votes
1answer
102 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 ...
5
votes
1answer
62 views
How to compute the asymptotic growth of $\binom{n}{\log n}$?
I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$
It sounds like it's something simple, but I can't get a nice expression I can use.
Any ideas on how to do this?
0
votes
0answers
100 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
155 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)!}$
1
vote
0answers
28 views
Compute the value of a sum (as an expression involving one or two binomial coefficients)
I've been asked to compute the value of a sum. The answer should be an expression involving one or two binomial coefficients.
The initial expression:
$$
\sum_{k} \binom{80}{k} \binom{k+1}{31}
$$
...
0
votes
2answers
38 views
Calculation of binomial sum $\displaystyle \sum_{r=1}^{n}r.\binom{n}{r}x^r.(1-x)^{n-r} = \;\;?$
How can I calculate
$$\displaystyle \sum_{r=1}^{n} r \binom{n}{r}x^r (1-x)^{n-r} =\;\; ?$$
14
votes
2answers
462 views
Asymptotics of sum of binomials
How can you compute the asymptotics of
$$S=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$
We have that $n \geq m$ and $n,m \geq 1$.
A simple application of ...
0
votes
1answer
46 views
Binomial expansion for solving american put option identity [duplicate]
For american put option I have to prove that:
1) As $D$ tends to $\infty$, $a_n$ tends to $-r/D$ so that $S^*$ tends to $0$.
2) As $D$ tends to $-\infty$, $a_n$ tends to $2D/ \sigma^2$ so that ...
3
votes
3answers
67 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
1answer
57 views
how compute $\gcd\Bigl(\binom{n}{1},\binom{n}{2},\binom{n}{3},…,\binom{n}{n-1}\Bigr)?$
how to prove $$\gcd\Biggl(\binom{n}{1},\binom{n}{2},\binom{n}{3},...,\binom{n}{n-1}\Biggr)=\begin{cases}
p, & \text{$n=p^m$ ;$p$ is prime} \\
1, & \text{o.w} \\
\end{cases}$$
thanks in ...
4
votes
2answers
61 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?
0
votes
1answer
11 views
General relation in binomial expansion
If $3$rd, $4$th, $5$th and $6$th terms in the expansion of $(x + a)^n$ be respectively $a$, $b$, $c$ and $d$ then:
$\frac{b^2 - ac}{c^2 - bd}$ = $\frac{5a}{3c}$.
Similarly,
If $6$th, $7$th, $8$th ...
3
votes
2answers
43 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
votes
0answers
51 views
Prove this identity $\sum\limits_{k=0}^n {n\choose k}(k+a)^{k-1}(n-k+b)^{n-k-1}=\frac{(a+b)(a+b+n)^{n-1}}{ab}$
Given $a,b,n\in \mathbb N^*$
Prove that:
$$\sum_{k=0}^n {n\choose k}(k+a)^{k-1}(n-k+b)^{n-k-1}=\frac{(a+b)(a+b+n)^{n-1}}{ab}$$
1
vote
0answers
46 views
Double sum with binomial coefficients
Find a closed form formula for this sum:
$$\sum_{1\le i<j\le m} \sum_{\substack{1\le k,l\le n \\ k+l\le n}}{n\choose k} {n-k\choose l} (j-i-1)^{n-k-l}$$
It's quite likely that it can be ...
1
vote
2answers
56 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
109 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 ...
5
votes
4answers
103 views
Proving $\binom{2n}{n}\le 4^n$ for all $n$ by smallest counterexample
Prove $$\binom{2n}{n}\le 4^n$$ for all natural numbers $n$ by smallest (minimal) counterexample.
My attempt:
First, $$\binom{2n}n = \frac{(2n)!}{(n!)^2} \le 4^n\;.$$ We know that $x\ne 0$ because ...
-2
votes
1answer
85 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).$$
