Tagged Questions
9
votes
5answers
89 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
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 ...
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 ...
9
votes
3answers
129 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
121 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
112 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
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}$. ...
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}$$
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
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.
1
vote
2answers
53 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
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 ...
4
votes
0answers
54 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 ...
3
votes
4answers
93 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 . . ...
0
votes
1answer
32 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
0answers
112 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
44 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} =\;\; ?$$
3
votes
3answers
81 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
2answers
46 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
0answers
53 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 ...
4
votes
4answers
135 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 ...
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
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 ...
6
votes
5answers
246 views
Simplify $\sum_{i=0}^n (i+1)\binom ni$
Simplifying this expression$$1\cdot\binom{n}{0}+ 2\cdot\binom{n}{1}+3\cdot\binom{n}{2}+ \cdots+(n+1)\cdot\binom{n}{n}= ?$$
$$\text{Hint: } \binom{n}{k}= \frac{n}{k}\cdot\binom{n-1}{k-1} $$
4
votes
2answers
134 views
Compact form of sum (binomial coefficients)
Find compact formula of the following sum:
$$ \sum_{i,j,k \in \Bbb Z} {{n}\choose{i+j}}{{n}\choose{j+k}}{{n}\choose{k+i}} $$
Could you give me any HINT how to start it?
I've tried this way:
$$ ...
0
votes
1answer
54 views
Calculating a recursive power term binomial sum
Could someone please help me or give me a hint on how to calculate this sum:
$$\sum_{k=0}^n \binom{n}{k}(-1)^{n-k}(x-2(k+1))^n.$$
I have been trying for a few hours now and I start thinking it may ...
1
vote
1answer
91 views
Sum of the first k binomial coefficients for fixed n
I am reading Remarks on a Ramsey theory for trees by Janos Pach, Jozsef Solymosi and Gabor Tardos.
Let $k, d, n \geq 2$ be integers. Somethig interesting happens when $$2^{n/k} > \sum_{i=0}^{d-1} ...
13
votes
3answers
411 views
Proving that $\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\frac{1}{2}n^n$
How can we prove that
$$\displaystyle\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\dfrac{1}{2}n^n$$
where $\displaystyle\binom{n}{i}=\dfrac{n!}{i!(n-i)!}$.
This inequality is very interesting. I ...
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
3answers
73 views
Combinatoric Explanation of General Identity
When $k \lt n$, what is the value of the sum $$\sum\limits_{j=0}^n {n \choose j}(-1)^j (n-j)^k.$$ Explain combinatorially.
Any ideas on where to start?
1
vote
1answer
15 views
how to get a binomial from a summation
An urn contains 6 Red balls and 1 Blue ball. A fair die having faces f1;2;3;4;5;6g is
rolled. If the top face on the die shows m, then m random balls are removed from the urn.
What is the expected ...
5
votes
1answer
78 views
How to compute the sum of every $k$-th binomial coefficient?
My teacher was discussing binomial expansions of $(1 + x)^n$ and he gave as an interesting example with $x = i$ whereby you could obtain the sum of all the odd coefficients ($C_n^1+ C_n^3+ C_n^5 ...$) ...
10
votes
7answers
303 views
Summation simplification $\sum_{k=0}^{n} \binom{2n}{k}^2$
$\sum_{k=0}^{n} \binom{2n}{k}^2$
So i'm trying to simplify this one and I'm stuck in nowhere. Some kind of tip would be appreciated.
Thanks! :)
5
votes
1answer
80 views
$\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof
Is there a simple combinatorial proof for the following identity?
$$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$
where $m,j \geq 0$, $k \geq n \geq 0$.
4
votes
2answers
255 views
Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$
I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$
I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
3
votes
2answers
74 views
How to get the sum of the values in a $N \times N$ table?
How to get the sum of the values in a $N \times N$ table (without adding repeating products such as $6 \times 7$ and $7 \times 6$ twice and without counting perfect squares)?
Figured out that
$1 ...
6
votes
1answer
127 views
Closed-form expression for $\sum_{n=1}^{k} (-1)^{n+1}n^2(n^2-1)\binom{2k}{k-n}$?
Wolframalpha tells me that
$$\sum_{n=1}^{k} (-1)^{n+1}n^2(n^2-1)\binom{2k}{k-n}=0$$ for $k>2$
However I have not been able to come up with a proof and I simply don't see how to do it. Does anyone ...
1
vote
3answers
106 views
Can the identity $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem?
Can this identity be derived from the binomial theorem?
$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$
Please, explain how.
I tried starting from $2^n = \sum_{i=0}^{n} \binom{n}{i}$ and ...
7
votes
1answer
180 views
Summation of an Infinite Series: $\sum_{n=1}^\infty \frac{4^{2n}}{n^3 \binom{2n}{n}^2} = 8\pi G-14\zeta(3)$
I am having trouble proving that
$$\sum_{n=1}^\infty \frac{4^{2n}}{n^3 \binom{2n}{n}^2} = 8\pi G-14\zeta(3)$$
I know that
$$\frac{2x \ \arcsin(x)}{\sqrt{1-x^2}} = \sum_{n=1}^\infty ...
2
votes
1answer
85 views
How to simpify the following equation involving binomial coefficients?
How can one simplify this equation:
$$
\sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{k+1}
$$
4
votes
4answers
68 views
Verify that $\sum^{8564}_{i=82} \binom{8564}{i} < 2^{8564}$
I have to tell if the following inequality is true: $$\sum^{8564}_{i=82} \binom{8564}{i} < 2^{8564}$$
but how do I tackle that? I reckon the standard formula for calculate the value of the ...
0
votes
1answer
140 views
Sum of following binomial series :
I need to solve this binomial summation but cant seem to get it using binomial identities I learnt in school and college first-year:
$$S=\sum_{i=q}^{p-q}{\binom{i}{q}}{\binom{n-i}{p-q}}$$
p,q,n are ...
11
votes
0answers
204 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}$$
5
votes
2answers
108 views
Generalization Of The Binomial Theorem
Consider the sum
$$\sum_{k=0}^{n_0} {n \choose k} \cdot \alpha^k$$
where $\alpha \in \mathbb{R}$ arbritary, $n_0 < n$. So it looks like binomial theorem,
$$\sum_{k=0}^n {n \choose k} \cdot ...
5
votes
0answers
236 views
Proof for an identity involving a sum of binomial coefficients
I am moving through a On The Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my skills are ...
1
vote
2answers
117 views
$\sum_{m=0}^n (m-np)^2 {n \choose m} p^m q^{n-m} = npq$
How to show that:
$\sum_{m=0}^n (m-np)^2 {n \choose m} p^m q^{n-m} = npq$
1
vote
2answers
63 views
Finding the summation of a product of the particular binomial coefficients
How can I simplify the following expression?
$$\sum_{j=0}^{k} \binom{n-j}{p} \binom{m+j}{q}$$
where $n,m,p,q,k$ are positive constants
such that $n-k \ge p$ and $m \ge q$.
5
votes
2answers
115 views
Simplifiying sum through integral?
I wanted to compute the sum $$\sum_{k=1}^{n}\frac{1}{k}\binom{n}{k}.$$
And I thought it would be easiest to do this by making it a function, differentiating it and integrating it then.
So I did: ...
