Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

9
votes
0answers
172 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
8
votes
0answers
90 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
7
votes
0answers
151 views

Characterization of Sequences with Integral Binomial Coefficients

For any sequence of positive integers $\{ a_i \}_{i \ge 1}$ we can define the generalized binomial coefficients $\binom{n}{k}_{a}$ as follows: $$m!_a = a_1 a_2 \cdots a_m, \binom{n}{k}_a = ...
6
votes
0answers
150 views

Conjecture $\sum_{n=1}^\infty\frac{(1/2)_n(-1/6)_n}{n!(2/3)_n}H_n\overset{?}={\pi\over 6}+2\sqrt{3}\ln(1+\sqrt{3})-{7\over\sqrt{3}}\ln 2-6+2\sqrt{3}$

Sums involving harmonic numbers have old history and first examples of their evaluations go back to Euler. Lately there has been a lot of interest, both on this forum and among professional ...
6
votes
0answers
97 views

A combinatorial identity involving generalized harmonic numbers

The $n$-th harmonic number is defined as $$ H_n=\sum_{k=1}^{n}\frac{1}{k}, $$ and the generalized harmonic numbers are defined by $$ H_{n}^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}. $$ Recently, I have found ...
6
votes
0answers
195 views

How to prove that $\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$?

How to prove this: $$\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$$ For all $x\in\mathbb R_{\ge0}$ and with $\binom{x}{r}=\frac{\Gamma(x+1)}{\Gamma(r+1)\cdot\Gamma(x-r+1)}$ It is obviously ...
6
votes
0answers
619 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 ...
6
votes
0answers
204 views

Partial sum over $M$, of ${m+j \choose M} {1-M \choose m+i-M}$?

Is there (likely to be) any formula for $$ \sum_{m' \geq m} {m+j \choose m'} {B - m' \choose m+i-m'} $$ ? I am mainly interested in the case $B=1$ (or a prime power), if that's any ...
5
votes
0answers
111 views

When $\frac{1}{n}\binom{n}{r}$ is an integer , again?

This question follows a previous one If $n$ and $r$ are coprime then $a_{n,r}=\frac{1}{n}\binom{n}{r}$ is integer but this is not a necessary condition. Question: what is a necessary and ...
5
votes
0answers
277 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
5
votes
0answers
123 views

Binomial triplets

Solutions to the equation $$\dbinom{a}{n}+\dbinom{b}{n}=\dbinom{c}{n}$$ I will refer to as 'Binomial triplets of order $n$'. These triplets describe simplicial $n$-polytopic numbers that can be ...
5
votes
0answers
163 views

Some rare binomial identities

Long ago , I once saw a nontrivial appealing binomial type of identity that I never saw again. It was something along the line of $\Sigma$$\binom{a(x)}{b(y)}$= where $a$ and $b$ where polynomials not ...
4
votes
0answers
64 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j}.$$ Ideally it should be possible to evaluate it exactly using some ...
4
votes
0answers
54 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also ...
4
votes
0answers
316 views

LCM of binomial coefficients and related functions

I know about the following identity: $$\displaystyle \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \frac{\text{lcm}(1, 2, ... n+1)}{n+1}$$ 1) Is there any method to find ...
4
votes
0answers
84 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
4
votes
0answers
160 views

Proving an equation involving binomial coefficients

Prove that $$\sum_{q=0}^v \binom{v}{q}\frac{q!}{v^{q+1}} = \sum_{q=0}^{v-1} \binom{v-1}{q} \frac{(q+2)!}{v^{q+2}}$$ Thanks. Below are what I have tried: Approach 1: $$\sum_{q=0}^{v-1} ...
4
votes
0answers
242 views

Sum of product of binomial coefficients and exponential function

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
4
votes
0answers
112 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) ...
4
votes
0answers
63 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
4
votes
0answers
434 views

How to calculate this triple summation?

I need to calculate the following summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m-j}\choose{k-j}}}{k\choose j}r^{k-j+i}$$ I do not know if it is a well-known summation or not. ...
4
votes
0answers
146 views

Binomial-like sum involving falling factorials

We know that $\sum_{k=0}^n a^k \frac{n^{\underline k}}{k!} = (1+a)^n$. Is there a known (preferably closed) form for $\sum_{k=0}^n a^k n^{\underline k}$?
4
votes
0answers
92 views

Binomial coefficient sum over top index

I am trying to evaluate a sum over binomial coefficients which is giving me some problems. Specifically I want to calculate: $$\sum_{r=0}^{c-1}\binom{r+n}{n}\frac{1}{c-r}$$ My main thought was to ...
4
votes
0answers
168 views

How to transform series of series into series

I need to prove this equation. $$ \sum_{k=0}^{i-2} \left( e \space α(k+1)\space\frac{(-1)^{i+k+2}}{(i-k-2)!} \right) = \sum_{k=0}^{i-2} \frac{(i-k)^k}{k!} \space e^{i-k} (-1)^k\space where,\space α(i) ...
4
votes
0answers
211 views

Is this formula for $\zeta(15)$ true?

Apery gave, $\begin{aligned} \zeta(3) &= \frac{5}{2}\,\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k^3\,\binom {2k}k}\end{aligned}$ J. Borwein and D. Bradley found this can be generalized to ...
4
votes
0answers
221 views

Simplifying an expression involving binomial coefficients

Consider $$ \prod_{j=0}^{i-1}\binom{n-2j}{2}\left[1+\sum_{k=0}^{N-1}{\left( \prod_{l=0}^{k} \dfrac{N-l}{M-l}\right)\left(1 + \sum_{m=k+1}^{N-1} \prod_{p=k+1}^m \dfrac{N-p}{M-p}\right)+1}\right] $$ ...
4
votes
0answers
261 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
467 views

p-adic numbers and binomial coefficients

Let $\alpha\in \mathbb{Z}_p$ be an $p$-adic integer and define for $n\in \mathbb{Z}_{\geq 0}$ $${\alpha\choose n} := \frac{\alpha(\alpha-1)\cdot\ldots\cdot(\alpha-n+1)}{n!}.$$ This is again a ...
3
votes
0answers
38 views

Is there a closed form for $n^k$ in terms of $\Delta n^{k+1},\Delta n^k$, …?

Let $\Delta$ be a sort of difference operator on a function $f(n)$ such that $$\Delta f(n)=f(n+1)-f(n)$$ Take the basic power function $f(n)=n^k$, $k\in\mathbb{N}\cup\{0\}$. Then we get ...
3
votes
0answers
62 views

How to evaluate: $\int_0^1x^{n-1}(1-x)^{n+1}dx$

How can I evaluate the following integral? ($n \in R$, $n>0$) $$\int_0^1x^{n-1}(1-x)^{n+1}dx$$ I was solving the following problem (as practice) in school: Prove that the sum of $n+1$ terms of ...
3
votes
0answers
39 views

How to prove this $p^{j-\left\lfloor\frac{k}{p}\right\rfloor}\mid c_{j}$

Let $p$ be a prime number and $g\in \mathbb{Z}[x]$. Let $$\binom{x}{k}=\dfrac{x(x-1)(x-2)\cdots(x-k+1)}{k!} \in \mathbb{Q}[x]$$ for every $k \geq 0$. Fix an integer $k$. Write the integer-valued ...
3
votes
0answers
88 views

Square of hockey stick identity: $\sum_{i=r}^n{i \choose r}^2$

Evaluate $\sum_{i=r}^n{i \choose r}^2$ where $n,r\in \mathbb{N},n>r$. This looks like the hockey stick identity but I can't find a way to evaluate it without a computer. Can someone help me out?
3
votes
0answers
44 views

Summing the binomial pmf over $n$, part 2

After the great answers I got to this question, I tried summing a similar-looking series using the same strategies ($k \geq 0, \alpha > 1, p \in (0,1)$): $$ \sum_{n=k}^{\infty} {n \choose k} p^k ...
3
votes
0answers
55 views

Can a certain polynomial have all its coefficients in some basis divisible by a prime $p$?

I fix $n\in\mathbf{N}^{*}$ and $n$ elements $\alpha_1,\ldots,\alpha_n$ in $\mathbf{N}^{*}$. Consider the polynomial $$Q(T)=\prod\limits_{1\leq i \leq n} \prod\limits_{0\leq j \leq \alpha_i -1} ...
3
votes
0answers
187 views

Sum problem involving Factorials

got the following problem to prove for $n \in \mathbb{N}$ and $1 \leq i \leq n$: \begin{equation} \sum_{k=1}^{n-i} \frac{(2n-1-i-2k)! 2^{2k}}{(n-i-k)! (n-k)! 2}=\sum_{k=1}^{n-i} \frac{(2n-1-i-k)! ...
3
votes
0answers
83 views

An inequality concerning non-negative integer matrices with constant row and column sums

I'd appreciate any suggestions for how to prove (or disprove) the inequality described below. Some notation first: for positive integers $k$ and $M$, let ${\mathcal D}_{k,M}$ denote the set of all $k ...
3
votes
0answers
85 views

Asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
3
votes
0answers
316 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
3
votes
0answers
72 views

Lucas' Theorem for $p$-adic integers?

Does Lucas' Theorem hold for $p$-adic integers? More specifically, does it specifically hold for the case that, given a $p$-adic integer: $$x = x_0 + x_1p + x_2p^2 + \cdots = \sum_{i=0}^\infty ...
3
votes
0answers
92 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
3
votes
0answers
32 views

Proving an inequality having binomial coefficients

Suppose that $0 \leq b \leq b+x < a$. How could I prove the inequality \begin{equation} \left(\frac{a-b-x}{a-x}\right)^x \leq \cfrac{\binom{a-x}{b}}{\binom{a}{b}} \leq \left(\frac{a-b}{a}\right)^x ...
3
votes
0answers
93 views

Combinatorical interpretation of $\binom{15}{5} = \binom{14}{6}$

I was reading up on Singmaster's conjecture on repeated binomial coefficiencts and I read that $$\binom{15}{5} = \binom{14}{6}$$ Sure, it's possible to prove it non-combinatorically: ...
3
votes
0answers
167 views

Proving $\sum_{k=1}^{n}\binom{n-1}{k-1}{\binom{n+k}{k}}^{-1}=\frac 12$ combinatorially

Question : How can we prove the following equations combinatorially? $$\begin{eqnarray}\sum_{k=1}^{n}\frac{\binom{n-1}{k-1}}{\binom{n+k}{k}}&=&\frac ...
3
votes
0answers
121 views

How to prove this combinatorial identity

I am wondering how to prove the following identity: $$\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}$$ It seems that I can negating the upper index of ${s \choose k-t} ...
3
votes
0answers
59 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
3
votes
0answers
222 views

Proving identity involving sum

I'm stuck trying to prove the following identity: $$\displaystyle\sum_{i=j}^k\frac{(-1)^{i+j}{k+1 \choose i}{i \choose j}(4S-i-k-3)!(4S-2i-1)}{(4S-i-j-1)!} $$ $$=\frac{(-1)^{j+k}(4S-2k-3)!{k+1 ...
3
votes
0answers
180 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
3
votes
0answers
275 views

Sums of rows in the Pascal triangle

Assume for simplicity that when $k>n$ we have ${n\choose k}=0$. It is well-known that $\sum_k {n\choose 2k}=\sum_k {n\choose 2k+1}=2^{n-1}$ , i.e. the sum of the odd places in each row in Pascal's ...
3
votes
0answers
102 views

max number of times integer $>1$ appears in pascals triangle

$120, 210 ,3003$ appear $6$ times in Pascal's triangle. $120={10\choose3}={16\choose2}={120\choose1}\\$ $210={10\choose4}={21\choose2}={210\choose1}\\$ ...
3
votes
0answers
399 views

Sylvester's Theorem and Schur Theorem

I'll probably end up asking more programming questions on StackExchange forums than math questions, but I'll lead off with a math question. In my Number Theory class this past semester, I worked on a ...