All Questions
65
questions
5
votes
3
answers
207
views
Showing $ \frac{2^j(2k-j)!}{(k-j)!}=\sum_{l=j}^k\frac{2^ll(2k-l-1)!}{(k-l)!} $
For any given $j,k\in\mathbb{N}$, with $j\leq k$, how is it possible to prove the following equivalence?
$$
\frac{2^j(2k-j)!}{(k-j)!}=\sum_{l=j}^k\frac{2^ll(2k-l-1)!}{(k-l)!}
$$
My attempt is:
$$
\...
- 53
14
votes
1
answer
253
views
Showing that, in Pascal's triangle, the product of the numbers along each median is always the same.
On Pascal's triangle with any number of rows, draw the three medians.
For each median, calculate the product of the numbers that zig-zag along that median.
The three products are always equal! (proof ...
- 25.8k
0
votes
1
answer
61
views
Help me prove a fun identity of binomial coefficients [duplicate]
Let $M$ be a positive integer. Then I believe that the following fun identity is true:
$$\sum_{k=0}^{\text{Floor}(M/2)}2^{M-2k}{M\choose 2k}{2k\choose k} = {2M\choose M}$$
Numerically it checks out ...
- 285
1
vote
0
answers
54
views
Alternating sum of products of half-shifted binomial coefficients
I have observed that the following identity seens to hold:
Let $k \geq 2$ and $0 \leq p, q \leq k+1$. Then
$$\sum_{m = 0}^{k+1-q} \begin{pmatrix}
-\frac12 + \lceil \frac{m+q}{2} \rceil ...
- 121
2
votes
1
answer
192
views
Formula related to combinatorial number
I got the following result from WolframAlpha. For positive integer $k$, $$\sum_{i=1}^n i^{2k} C_{2n}^{n-i} = 2^{2n-k-1}\left((2k-1)!!n^k+o(n^k)\right),$$
$$\sum_{i=1}^n i^{2k-1} C_{2n}^{n-i} = \frac12 ...
- 145
2
votes
1
answer
219
views
Stirling's formula and binary entropy to get binomial coefficient asymptotic
I am trying to prove the following
$${n \choose an} \sim \frac{1}{\sqrt{2\pi a (1-a)n}}2^{nH(a)}$$
I have this so far but it seems like I made an error somewhere and I am unable to identify where.
Let ...
- 79
0
votes
1
answer
41
views
How do we handle the factorials in the binomials/choice numbers?
Apparently the following is a known equality:
$\frac{1}{n + 1} {2n \choose n} = \frac{2n!}{n!(n + 1)!} = \frac{1}{2n + 1}{2n + 1 \choose n}$
but I can't really figure out how to produce the equality.
...
- 1,609
0
votes
0
answers
30
views
Expansion of factorial as linear combination of binomial coefficients [duplicate]
Let $k \leq n$ be positive integers. I would like a proof of the following identity:
$$
n!=\sum_{k=0}^n \binom{n}{k} (-1)^{n-k} k^n.
$$
EDIT: For context, I am using this to verify the below ...
- 579
1
vote
1
answer
66
views
Prove that $\sum_{q=0}^{d-r}\sum_{s=r+q}^{d}{{\binom {r-1+q}{r-1}}(r-1)!s}=\sum_{s=r}^{d}{\binom{s}{r}(r-1)!s}$ by sum manipulation [closed]
I know the sums $$\sum_{q=0}^{d-r}\sum_{s=r+q}^{d}{{\binom {r-1+q}{r-1}}(r-1)!s}$$ and $$\sum_{s=r}^{d}{\binom{s}{r}(r-1)!s}$$ are equal. How do I manipulate the double sum to look exactly like the ...
- 372
3
votes
2
answers
174
views
What is the order of magnitude of $\sum\limits_{n=1}^kn\binom{k}{n}\frac{(2k-2n-1)!!}{(2k-1)!!}$ as $k\to\infty$? [closed]
What is the order of magnitude of the function $f(k)$ below in the limit as $k \rightarrow \infty$? Does it diverge, converge to a positive limit, or converge to zero?
$$
f(k) = \sum\limits_{n=1}^{k} ...
- 200
1
vote
1
answer
204
views
Application of Stirling's formula
I'm currently frequenting a course in Combinatorics and I've come to this problem where I'm supposed to compute the following limit:
$$\lim_{n \to \infty} \sqrt [n] {\sum_{k=0}^{n} {n\choose k} ^{t}}$$...
- 297
1
vote
2
answers
80
views
Guidance on the function $\sum_{k=1}^{n}\binom{2n}{n-k}k^{2j}$
I am writing this post to gather whether or not anyone has some knowledge or information about the function
\begin{equation}
\sum_{k=0}^{n-1}\binom{2n}{k}(n-k)^{2j} = \sum_{k=1}^{n}\binom{2n}{n-k}k^{...
- 21
1
vote
2
answers
136
views
Upper bound for sum of binomials $\sum_{k=0}^{d}{N-1\choose k}$
I am interested to find a proof for the following upper bound.
$$\sum_{k=0}^{d}\begin{pmatrix}N-1\\k\end{pmatrix} \leq \frac{2N^d}{d!}$$
for $N\geq 3d$. I have tried to bound the sum by $(d+1)$ times ...
- 99
1
vote
4
answers
429
views
In how many ways $n$ distinct objects can be distributed to $k$ identical bins if bins may be left empty?
In how many ways $n$ distinct objects can be distributed to $k$ identical bins if bins may be left empty?
$$\sum_{r_{1}+...+r_{k}=n}^{ }\frac{1}{k!}\binom{n}{r_1}\binom{n-r_1}{r_2}\cdot\cdot\cdot\...
user801358
0
votes
1
answer
75
views
Can one simplify this expression involving products of binomial coefficients?
I was wondering if there is a way to simplify the following expression. $N, M, L, K, n, Q$ are fixed natural numbers. Also n is supposed to be even.
\begin{align*}
\sum_{q=0}^Q & \sum_{l=0}^L (-1)^...
- 36