Questions tagged [binomial-coefficients]
For questions that explicitly reference the binomial coefficients, Pascal's Triangle, and Binomial identities.
98 questions
128
votes
17
answers
105k
views
Sum of 'the first $k$' binomial coefficients for fixed $N$
I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...
- 1,358
23
votes
8
answers
14k
views
Lower bound for sum of binomial coefficients?
Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...
- 263
12
votes
4
answers
6k
views
Estimating a partial sum of weighted binomial coefficients
There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$:
$$ \sum_{k=0}^{\alpha n}\...
- 491
48
votes
5
answers
6k
views
Integer-valued factorial ratios
This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...
- 13.7k
23
votes
1
answer
7k
views
Are there good bounds on binomial coefficients?
Motivated by the central limit theorem, one expects that
$$\binom{n}{k} \approx \frac{2^n}{\sqrt{\pi n/2}} \exp\left(-\frac{(k-n/2)^2}{n/2}\right).$$
Computations suggest that the ratio of the two ...
- 9,864
56
votes
4
answers
5k
views
When do binomial coefficients sum to a power of 2?
Define the function $$S(N, n) = \sum_{k=0}^n \binom{N}{k}.$$
For what values of $N$ and $n$ does this function equal a power of 2?
There are three classes of solutions:
$n = 0$ or $n = N$,
$N$ is odd ...
- 5,317
43
votes
2
answers
7k
views
Alternating sum of square roots of binomial coefficients
Let
$$ c_n = \sum_{r=0}^n (-1)^r \sqrt{\binom{n}{r}}. $$
It is clear that $c_n = 0$ if $n$ is odd. Remarkably, it appears that despite the huge positive and negative contributions in the sum ...
- 11.9k
26
votes
3
answers
4k
views
Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$
I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...
4
votes
2
answers
3k
views
Estimate on sum of squares of multinomial coefficients
I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.
$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$
or more general,
$a_\...
- 145
2
votes
0
answers
238
views
On $a_n(x)=\sum_{i,j=0}^n\binom ni^2\binom nj^2\binom{i+j}ix^{i+j}$ (I)
Recall that the Apéry numbers are given by
$$A_n=\sum_{k=0}^n\binom nk^2\binom {n+k}k^2\ \ (n\in\mathbb N=\{0,1,2,\ldots\}).$$
In a 2012 JNT paper I conjectured that for any odd prime $p$ we have
$$\...
- 18k
35
votes
3
answers
3k
views
A binomial generalization of the FLT: Bombieri's Napkin Problem
This is an extract from Apéry's biography
(which some of the people have already enjoyed in
this answer).
During a mathematician's dinner in
Kingston, Canada, in 1979, the
conversation turned to ...
- 13.7k
18
votes
3
answers
909
views
$\prod_k(x\pm k)$ in binomial basis?
Let $x$ be an indeterminate and $n$ a non-negative integer.
Question. The following seems to be true. Is it?
$$x\prod_{k=1}^n(k^2-x^2)=\frac1{4^n}\sum_{m=0}^n\binom{n-x}m\binom{n+x}{n-m}(x+2m-n)^{...
- 43.9k
10
votes
2
answers
1k
views
Some series related to $\pi^4$ and $\zeta(3)$
Recently, I discovered the following identity
$$\sum_{k=0}^{\infty}\frac{\left(3 k +2\right) \left(7 k^{2}+9 k +3\right) 256^{k +1}}{\left(2 k +1\right)^{7} {\binom{2 k}{k}}^{7}}=(2\pi)^4.\tag{1}$$
My ...
- 1,248
9
votes
1
answer
611
views
Eigenvalues of a matrix with binomial entries
I am trying to determine the eigenvalues and eigenvectors of the following matrix:
$$M_{ij} = 4^{-j}\binom{2j}{i}$$
where it is understood that the binomial coefficient $\binom{m}{k}$ is zero if $k&...
- 924
6
votes
1
answer
987
views
What is the degree of a symmetric boolean function?
(previous title " Zero sum of binomials coefficients - a stronger version ")
This is a stronger version of another question.
Is there an $N\in \mathbb N$ and a sequence of non-constant functions $ \...
- 337