All Questions
Tagged with nt.number-theory binomial-coefficients
105 questions
0
votes
1
answer
129
views
Closed form for $\sum\limits_{k=0}^{n} [\operatorname{wt}(k) = m]$ where $\operatorname{wt}(n)$ is the binary weight of $n$
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of $1$'s in binary expansion of $n$).
Let $a(n,m)$ be the family of integer sequences such that
$$
a(n,m) = \sum\limits_{k=0}^{n} [\operatorname{wt}(...
- 4,938
0
votes
0
answers
86
views
How to prove the following equation (involving multiple binomial coefficients sum)?
I encountered the equation below, encountered a problem that has been bothering me for a long time
Does anyone have an idea how to prove it? I would be extremely grateful to you if you come up with an ...
- 41
0
votes
1
answer
169
views
Partial sums of binomial coefficients and related family of polynomials
Let $a(n)$ be A302117. Here
$$
a(n) = 4(n-1)a(n-1) - \frac{1}{3}\prod\limits_{k=0}^{n-1}(2k-3), \\
a(0) = 0.
$$
Let
$$
T(n,k) = \sum\limits_{i=0}^{k} \binom{n}{i}.
$$
Let $P_n(z)$ be the family of ...
- 4,938
4
votes
0
answers
168
views
How to prove the following equation (which involves binomials and determinant of 2×2 matrices)?
I have tried many ways to prove the following equation, such as the method of induction and expanding all the terms in the summation,but things got more complicated.I could not find an appropriate ...
- 41
1
vote
0
answers
138
views
Eisenstein triples (and triangles with rational sides and a rational-degree angle) in Pascal's triangle
This question leads to a follow-up: are there any Eisenstein triples (satisfying $a^2\pm ab+b^2=c^2$) in one row of Pascal's triangle apart from the following:
$\binom{23}{8}^2+\binom{23}{8}\binom{23}{...
- 2,370
22
votes
1
answer
1k
views
We have $\binom{62}{26}^2+\binom{62}{27}^2=\binom{62}{28}^2$. How many other Pythagorean triples are contained in a single row of Pascal's triangle?
At MSE I asked, "Does any row of Pascal's triangle contain a Pythagorean triple?" The answer is yes; the example $\binom{62}{26}^2+\binom{62}{27}^2=\binom{62}{28}^2$ was given. In that ...
- 3,527
0
votes
0
answers
30
views
Are there any numerically-plausible perfect binary code parameters besides (90,2)? [duplicate]
(Formerly on Math StackExchange here, without much progress.)
In order for a perfect binary code on $n$ symbols to correct $k$ errors, we need the sum
$${n\choose 0}+{n\choose 1}+\ldots+{n\choose k}$$
...
- 3,068
6
votes
0
answers
752
views
For all $n\in \mathbb{N}$, How to find $\min\{ m+k\}$ such that $ \binom{m}{k}=n$?
I asked this question on MSE here.
Most numbers in pascal triangle appear only once (excluding the duplicates in the same row of the Pascal's triangle) but certain numbers appear multiple times. ...
- 541
1
vote
0
answers
73
views
Alternating sum of integer coefficients of the triangles related to Eulerian numbers and binomial transforms
Let $W(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n \leqslant 0$ or $k \leqslant 0$ such that
$$
W(n, k, m) = (k+m-1)W(n-1,...
- 4,938
7
votes
1
answer
527
views
Suitable closed form for the A079501
Let $a(n)$ be A079501 (i.e., number of compositions of the integer $n$ with strictly smallest part in the first position).
The sequence begins with
$$
1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, ...
- 4,938
4
votes
1
answer
252
views
About the exact origin of a binomial congruence
Given a prime $p$ and an integer $0 \leq k \leq p-1$, a famous congruence on binomial coefficients states:
$$\binom{p-1}{k} \equiv (-1)^k \pmod{p}$$
It is generally taught as a consequence of Pascal’s ...
- 125
3
votes
1
answer
829
views
binomial coefficients are integers because numerator and denominator form pairs?
I've heard of a claim that when calculating the binomial formula with integer input:
$\mathrm{Bin}(n,k):=\prod^k_{i=1}\frac{n+1-i}{i}\in \mathbb{N}\ (\forall n,k\in\mathbb N)$
each denominator divides ...
- 187
10
votes
0
answers
598
views
Does the interior of Pascal's triangle contain three consecutive integers?
This question defeated Math SE, so I am posting it here.
Consider the interior of Pascal's triangle: the triangle without numbers of the form $\binom{n}{0},\binom{n}{1},\binom{n}{n-1},\binom{n}{n}$.
...
- 3,527
3
votes
1
answer
437
views
Identities for Bernoulli numbers
I arrived at this formula by inductive reasoning, but I don’t know how to prove it.
For any natural numbers $m$ and $k=0,1,2,\ldots, m-1$, $B_i$ - Bernoulli numbers we have:
$$\sum_{i=0}^k (-1)^{k-i}\...
- 31
24
votes
2
answers
2k
views
Are (55, 165, 495, 1485) and (286, 1716, 10296, 61776) the only geometric sequences of length 4 among non-trivial binomials?
Let's define non-trivial binomial coefficients as values of $\binom{n}{k}$, where $n$ and $k$ are positive integers such that $2 \le k \le \frac{n}{2}$. (Therefore, $6$ is the smallest non-trivial ...
- 425
11
votes
1
answer
681
views
Solve $\binom{n}{k}=m$ for $(n,k)$
For an integer $m>0$, put $X(m)=\{(n,k):4\leq 2k\leq n \text{ and } \binom{n}{k}=m\}$. Is there an efficient method to calculate $X(m)$? Is there a uniform upper bound for $|X(m)|$?
By ...
- 56.9k
0
votes
1
answer
179
views
Question in a paper by Erdős on divisibility properties of central binomial coefficient
In Erdős, Graham, Ruzsa, and Straus - On the prime factors of $\binom{2n}n$, at the beginning of the proof of theorem 1, they consider the case where $\log p$ and $\log q$ are commensurable numbers (...
- 111
13
votes
1
answer
468
views
Four new series for $\pi$ and related identities involving harmonic numbers
Recently, I discovered the following four new (conjectural) series for $\pi$:
\begin{align}\sum_{k=1}^\infty\frac{(5k^2-4k+1)8^k\binom{3k}k}{k(3k-1)(3k-2)\binom{2k}k\binom{4k}{2k}}&=\frac{3\pi}2,\...
- 15.6k
1
vote
0
answers
95
views
On level-$12$ of the McKay-Thompson series of the Monster and the Domb numbers
(This continues from level 10.) Given some moonshine functions $j_{N}$. There are nice descending and consistent relations for levels $6m$ with $m= 2,3,5,$
$$j_{12A} = \left(\sqrt{j_{12H}} + \frac{\...
- 12.6k
1
vote
0
answers
116
views
On level $6$ of the McKay–Thompson series of the Monster and Apéry numbers, et al
After the McKay–Thompson series of levels $1$, $2$, $3$, $4$ of the Monster were mentioned in this MO post, level $6$ has very interesting relations as well. (Level 10 is in this post.)
I. Level-6 ...
- 12.6k
2
votes
0
answers
70
views
Integer coefficients such that $T(n,k)=R(n,k)-R(n,k-1)$
Let $a(n)$ be A000085, i.e., the number of self-inverse permutations on $n$ letters, also known as involutions; number of standard Young tableaux with $n$ cells. Here
$$a(n) = a(n-1) + (n-1)a(n-2), a(...
- 4,938
13
votes
1
answer
584
views
A congruence for a product of binomial coefficients?
For every prime $p\geq 5$ one seems to have the congruence
$$(-1)^{(p-1)/2}\prod_{k=0}^{p-1}{p-1\choose k}\equiv 1-p+\frac{3}{2}p^2-\frac{7}{6}p^3\pmod{p^4}\ .$$
(I have checked all primes up to $5000$...
- 17.9k
4
votes
0
answers
117
views
Greatest common divisors of some binomial coefficients
This is cross-posted from math.stackexchange.
While making some computation, I stumbled upon a curious relation among some binomial coefficients.
Consider the sequence of binomial coefficients $a(k,n)$...
- 1,000
10
votes
1
answer
434
views
Series for $\frac{\log m}{\pi}$ with summands involving harmonic numbers
The classical rational Ramanujan-type series for $1/\pi$ have the following four forms:
\begin{align}\sum_{k=0}^\infty(ak+b)\frac{\binom{2k}k^3}{m^k}&=\frac{c}{\pi},\label{1}\tag{1}
\\\sum_{k=0}^\...
- 15.6k
3
votes
2
answers
710
views
Binomial coefficient congruence modulo $p^n$
I am interested in the following congruence
$$\binom{ap^n}{bp^n}\equiv \binom{a}{b}\pmod{p^n}$$
I am aware that by some reference in a book the above it should actually hold modulo $p^{3n}$; the ...
- 847
4
votes
0
answers
279
views
What is the exact value of the series $\sum_{k=0}^\infty \binom{2k}k^4/256^k$?
By Stirling's formula $n!\sim\sqrt{2\pi n}(n/e)^n$, we have
$$\binom{2k}k\sim\frac{4^k}{\sqrt{k\pi}}$$
and hence
$$\frac{\binom{2k}k^4}{256^k}\sim\frac1{k^2\pi^2}.\tag{1}$$
So the series
$$\sum_{k=0}^\...
- 15.6k
2
votes
0
answers
219
views
Question on globally convergent formulas for the Riemann zeta function $\zeta(s)$
Consider the following two formulas for $\zeta(s)$
$$\zeta(s)=\underset{K\to\infty}{\text{lim}}\left(\frac{1}{1-2^{1-s}}\sum\limits_{n=0}^K \frac{1}{2^{n+1}}\sum\limits_{k=0}^n \binom{n}{k} \frac{(-1)^...
- 1,126
24
votes
3
answers
3k
views
Analogue of Fermat's "little" theorem
Let $p$ be a prime, and consider $$S_p(a)=\sum_{\substack{1\le j\le a-1\\(p-1)\mid j}}\binom{a}{j}\;.$$
I have a rather complicated (15 lines) proof that $S_p(a)\equiv0\pmod{p}$. This must be
...
- 13.1k
2
votes
0
answers
112
views
Divisibility based on central binomial coefficients
For some prime $p$, it is a standard approach based on Kummer's criterion to bound the number of positive integers $n<X$ for some parameter $X$, such that $p\nmid \binom{2n}{n}$. However, if we ...
- 1,042
3
votes
0
answers
144
views
Flat polynomials with factors of big height
Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
- 13.4k
2
votes
3
answers
742
views
Asking for a proof for a sum of products of binomials: an "interesting" identity?
The following identity must have received alternative proofs, including a combinatorial argument by David Callan as found at Bijections for the Identity $4^n = \sum_{k = 0}^n \binom{2k}k\binom{2(n - k)...
- 43.2k
55
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,227
0
votes
2
answers
235
views
Closed form expression for power of binomial expression with radical
When performing binomial expansion of $(a+b\sqrt c)^n$ I get $x+y\sqrt c$ where
$x$ is $\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} a^{n-2k} b^{2k} c^k$
$y$ is $\sum_{k=0}^{\lfloor (n-1)/2\rfloor} ...
- 39
2
votes
0
answers
215
views
Two conjectures about generalised A329369
Let $m \geqslant 2$ be a fixed integer.
Let
$$\operatorname{wt}(n,m)=\operatorname{wt}\left(\left\lfloor\frac{n}{m}\right\rfloor,m\right)+n\bmod m, \operatorname{wt}(0,m)=0$$
Then we have an integer ...
- 4,938
2
votes
1
answer
113
views
Modulo $2$ binomial transform of A243499 applied $k$ times
Let $m \geqslant 1$ be a fixed integer.
Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
...
- 4,938
0
votes
1
answer
149
views
Modulo $2$ binomial transform of A124758
Let $f(n)$ be A153733, remove all trailing ones in binary representation of $n$. Here
\begin{align}
f(2n)& = 2n\\
f(2n+1)& = f(n)\\
\end{align}
Then we have an integer sequence given by
\begin{...
- 4,938
1
vote
0
answers
57
views
Inverse modulo $2$ binomial transform of generalised A284005
Let $m \geqslant 1$ be a fixed integer.
Let $\operatorname{wt}(n)$ be A000120, $1$'s-counting sequence: number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).
Let $f(n)$ be A007814, ...
- 4,938
1
vote
0
answers
156
views
Open tours by a biased rook (proof verification)
Related questions:
Number of open tours by a biased rook on a specific $f(n)\times 1$ board which end on a $k$-th cell from the right
Sum with products turned into subsequences
Combinatorial ...
- 4,938
2
votes
2
answers
180
views
Modulo $2$ binomial transform of $m^n$
Let $m \in \mathbb{R}$.
Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
Let $g(n)$ be ...
- 4,938
3
votes
0
answers
151
views
Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005
My question is related to the following:
Sum with products turned into subsequences
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...
- 4,938
1
vote
1
answer
277
views
There seem to be only few primes of the form ${n\choose k}+1$ if $k\geq 3$ is odd
We consider the sequence $n\longmapsto {n\choose k}+1$
for $k\geq 1$ a fixed integer. For $k\geq 3$ odd,
this sequence seems to contain surprisingly few prime numbers
while there are many primes (...
- 17.9k
0
votes
1
answer
427
views
Prove for all $k \in \mathbb{N}$, that $\sum_{j=0}^{2k+1} {n+j-1\choose j} + \sum_{j=0}^{2k+1}(-1)^j{n+2k+2\choose j} = 0$
Prove that this sum holds for all positive integers $k$. I'm quite sure this is right but I can't see immediately how to go about proving it. This will help resolve a problem regarding sums of ...
- 1,109
11
votes
1
answer
643
views
A conjecture on binomial coefficients and roots of unity
Is the following true?
Let $p$ be a prime and let $w$ be a $(p-1)$st root of unity (not necessarily primitive). Then
$$\binom{w}{n}=\frac{w(w-1)\cdots(w-n+1)}{n!}$$ is $p$-integral; i.e., it can be ...
- 17k
1
vote
2
answers
287
views
In search of a combinatorial proof for a multinomial sum
There is this sequence listed on OEIS - named Domb numbers. I'm curious about
QUESTION. Is there a direct combinatorial proof for the identity
$$\sum_{k=0}^n\binom{n}k^2\binom{2k}k\binom{2n-2k}{n-k}
=...
- 43.2k
2
votes
1
answer
290
views
Evaluations of three series involving binomial coefficients
Question. How to prove the following three identities?
\begin{align}\sum_{k=1}^\infty\frac1{k(-2)^k\binom{2k}k}\left(\frac1{k+1}+\ldots+\frac1{2k}\right)=\frac{\log^22}3-\frac{\pi^2}{36},\tag{1}
\end{...
- 15.6k
12
votes
1
answer
840
views
Numbers $k$ with $\{\binom nk:\ n\in\mathbb N\}$ dense in $\mathbb Z_p$ for any prime $p\le k$
Let $k$ be a positive integer and let $p$ be a prime. In my 2011 PAMS paper joint with my former student W. Zhang [Proc. Amer. Math. Soc. 139(2011), 1569-1577], we studied when $$S(k)=\left\{\binom nk:...
- 15.6k
1
vote
0
answers
154
views
An explicit solution to the congruence $x^2\equiv 14(\frac 3p)-(\frac p3)-12\pmod {p}$?
Let $p>3$ be a prime, and let $(\frac{\cdot}p)$ be the Legendre symbol. Then
$$14\left(\frac 3p\right)-\left(\frac p3\right)-12=\begin{cases}1&\text{if}\ p\equiv1\pmod{12},
\\-25&\text{if}\ ...
- 15.6k
7
votes
0
answers
183
views
Some conjectural congruences involving Domb numbers
The Domb numbers are given by
$$D_n=\sum_{k=0}^n\binom{n}{k}^2\binom{2k}k\binom{2(n-k)}{n-k}\ \ \ (n=0,1,2,\ldots).$$
Such numbers have combinatorial interpretation, see, e.g., http://oeis.org/A002895....
- 15.6k
2
votes
1
answer
194
views
Does this series, related to the Hasse/Ser series for $\zeta(s)$, converge for all $s \in \mathbb{C}$?
I have asked this question at math stack exchange, however it did not get any traction. Still curious about the answer though.
Numerical evidence suggests that:
$$\lim_{N \to +\infty} \sum_{n=1}^N\...
- 4,169
1
vote
0
answers
100
views
Divisibility properties of linear combinations of binomial coefficients [closed]
Let $p$ be a prime and $a_0,\ldots,a_n\geq 0$ be integers. Define
$$
S(a_0,\ldots,a_n)=\sum_{k=0}^n a_k\binom{n}{k}.
$$
I am trying to find out how much we know about
$$
v_p(S(a_0,\ldots,a_n)),
$$
...
- 81