All Questions
96
questions
1
vote
1
answer
38
views
Summation of n-simplex numbers
Gauss proved that every positive integer is a sum of at most three triangular(2-simplex) numbers. I was thinking of an extension related to n-simplex.
Refer: https://upload.wikimedia.org/wikipedia/...
1
vote
0
answers
323
views
A conjecture on representing $\sum\limits_{k=0} ^m (-1)^ka^{m-k}b^k$ as sum of powers of $(a+b)$.
UPATE: I asked this question on MO here.
I was solving problem 1.2.52 in "An introduction to the theory of numbers by by Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery"
Show that if ...
- 6,565
5
votes
1
answer
205
views
Conjecture: $\binom{n}{k } \mod m =0$ for all $k=1,2,3,\dots,n-1$ only when $m $ is a prime number and $n$ is a power of $m$
While playing with Pascal's triangle, I observed that $\binom{4}{k } \mod 2 =0$ for $k=1,2,3$,and $\binom{8}{k } \mod 2 =0$ for $k=1,2,3,4,5,6,7$ This made me curious about the values of $n>1$ and ...
- 6,565
2
votes
1
answer
221
views
Generalization of binomial coefficients to both non-integer arguments
It is known that binomial coefficients can be generalized to the following: for $s\in\mathbb R$ and $k\in\mathbb N$,
\begin{equation*}
\binom{s}{k} := \prod_{i=0}^{k-1} \frac{s-i}{k-i} = \frac{s(s-1)...
- 1,972
4
votes
0
answers
251
views
Sum of even binomial coefficients modulo $p$, without complex numbers
Let $p$ be a prime where $-1$ is not a quadratic residue, (no solutions to $m^2 = -1$ in $p$).
I want to find an easily computable expression for
$$\sum_{k=0}^n {n \choose 2k} (-x)^k$$
modulo $p$. ...
- 4,284
0
votes
0
answers
100
views
Show that $2n\choose n$ divisible by primes $p,$ such that $n<p<2n$? [duplicate]
Suppose on the contrary that $2n \choose n$ is not divisible by $p\in (n,2n)$. There exis $k$ and $0\ne r\lt p$ such that
$(2n)\cdots (n+1)=kp \,n!+r \, n!$. The second term on RHS is not divisible by ...
- 11.5k
-1
votes
1
answer
48
views
Number of ones in the dyadic expansion of m [closed]
I was going through a paper where I stuck on a combinatorial argument as follows
I want help with the first assertion i.e proving the inequality $\alpha(m+l)\le\alpha(m)$.
As the author suggests it is ...
- 1,790
1
vote
1
answer
83
views
prove that: there are exactly ${n-1 \choose k-1}$products that consist of $n-k$ factors
prove that: there are exactly ${n-1 \choose k-1}$products that consist of $n-k$ factors,so that all these factors are elements of $[k]$. Repetition of factors is allowed,
that is my attempt :
for ...
user998997
0
votes
1
answer
61
views
$\sum\limits_{k=1}^{n-1}\binom{n-1}{k-1}\frac{a^{n-k}b^k}{k}=\frac{(a+b)^n-a^n-b^n}{n}$
In "New properties for a composition of some generating functions for primes", properties of generating functions are used to form a primality test, speaking specifically in example 1 the ...
- 1,262
2
votes
0
answers
47
views
A $\Bbb Z$-valued $\Bbb Q$-coefficient polynomial is a $\Bbb Z$-combination of $\binom{x}{k}$s: $q$-analog?
I am wondering what a $q$-analog of the following should be:
Proposition. If $f(x)\in\Bbb Q[x]$ is a polynomial for which $f(\Bbb Z)\subseteq\mathbb{Z}$ (that is, $f(x)$ is an integer for all integers ...
- 152k
5
votes
1
answer
186
views
For how many $n$ is $2021^n$ + $2022^n$ + $2023^n$ + ... + $2029^n$ prime?
For how many $n$ is $2021^n$ + $2022^n$ + $2023^n$ + ... + $2029^n$ prime?
My first thought is set x = 2021 so we can create:
$x^n$ + $(x+1)^n$ + $(x+2)^n$ + ... + $(x+8)^n$
And then we expand each ...
- 199
2
votes
1
answer
108
views
Parity of a Binomial Coefficient Using Lucas' Theorem
I'm trying to prove a property involving the parity of a binomial coefficient using Lucas' theorem. For this, let $r=\lfloor \log_2(k_s)\rfloor+1$, with $k_s\geq2$. We know that if $0\leq i\leq 2^{r}-...
- 453
1
vote
1
answer
53
views
How to summarise pattern in binomial-type expansion into a single expression
I have a series of polynomials as follows:
\begin{eqnarray}
&1\\
&1+4x^3+x^6\\
&1+20x^3+48x^6+20x^9+x^{12}\\
&1+54x^3+405x^6+760x^9+405x^{12}+54x^{15}+ x.^{18}\\
& \vdots\tag{1}
\...
- 317
2
votes
1
answer
697
views
binomial coefficients modulo $3$
Let $a(n)$ be the number of binomial coefficient's on the $n$-th row of Pascal's triangle which leave remainder $1$ upon division by $3$, and $b(n)$ be the number that leave remainder $2$. Show that $...
user765855
12
votes
2
answers
602
views
If a power of 2 divides a number, under what conditions does it divide a binomial coefficient involving the number that it divides?
We have had many questions here about the divisibility of $\binom{n}{k}$, many of them dealing with divisibility by powers of primes, or expressions involving the $\textrm{gcd}(n,k)$ (I originally ...
- 1,068
3
votes
1
answer
164
views
Combinatorial interpretation for $\binom{n}{3}- \lfloor \frac{n}{3} \rfloor$
P2, RMO 2003, India
For any natural number $n\gt7$, prove that $\binom{n}{7}-\lfloor \frac{n}{7} \rfloor$ is divisible by $7$.
My algebraic solution :
$$ \binom{n}{7} = \dfrac{n(n-1)(n-2)(n-3)(n-4)(n-...
- 10.6k
5
votes
2
answers
942
views
Relation between Pascal's Triangle and Euler's Number
My friends and myself were discussing Pascal's Triangle, specifically the following property of it.
First, consider the Pascal's Triangle -
$$1\\ 1\ 1\\ 1\ 2\ 1\\ 1\ 3\ 3\ 1\\ 1\ 4\ 6\ 4\ 1\\ 1\ 5\ ...
- 256
0
votes
1
answer
36
views
On powers of binomial coefficient
Consider $(1+n)^k$. Where both n, k are natural numbers.
We have binomial expansion $\sum_{i=0}^{k} \binom{k}{i}n^i $
Then we have for each i-th term, certain powers of n(at least $>=i$).
As i ...
0
votes
1
answer
45
views
A proof for sum including binomial [duplicate]
I was trying to prove some equation and reached this summation $\sum \limits_{j=0}^{m} {2j\choose{j}} {2m-2j \choose {m-j}} = 4^m $
I tried pascal identity and other known binomial identities but ...
user411780
0
votes
0
answers
48
views
Amount of Compositions of a Number n into k parts when the components are limited to the range [1;m] with m<n
The number of compositions of a number n into k parts is given by the binomial coefficent ${n-1 \choose k-1}$.
Is there a closed formula to this question, when the summands of the composition are ...
- 9
0
votes
1
answer
54
views
Identity on Theory of Numbers
Can anyone help me identify this identity? Or is there a known principle regarding this?
$k\binom{k}{k}-(k-1)\binom{k}{1}+(k-2)\binom{k}{2}-(k-3)\binom{k}{3}+\ldots +(-1)^{k-1}\binom{k}{k-1}$
Any ...
- 13
3
votes
1
answer
720
views
How many non-negative integer solutions exist for: $x+y+z=48$ where, $x<y<z$?
I want to find the number of non-negative integral solutions to the following:
$x+y+z=48$ where, $x<y<z$.
The answer is apparently 192 and the solution provided is $$\frac{\dbinom{50}{2}-\...
- 123
2
votes
1
answer
77
views
Digits patterns in power number
Definition
Given positive integers $a,b$, with $a>1$, let $D(a,b)$ be the sum of the base-$a$ digits of $b$.
In other words
Rearranging, we get: $b = r_{l} a^l + ... + r_2 a^2 + r_1 a^1 + r_0 a^...
- 2,697
4
votes
2
answers
6k
views
$n$ choose $k$ where $n$ is negative
I saw (in the book $A~ Walk~ Through~ Combinatorics$) that $\sum_{n \geq 0}{-3 \choose n} = \sum_{n \geq 0}{n+2 \choose 2}(-1)^n$, which confuses me. It seems that it can be derived directly from ...
- 43
6
votes
0
answers
221
views
What is the growth rate of the products of binomial coefficients?
Claim: Experimental data seems to suggest that
$$
{n \choose 1^a b}{n \choose 2^a b}{n \choose 3^a b}\cdots {n \choose m^a b}
\sim \exp\bigg(\frac{2n^{1 + \frac{1}{a}}}{ab+3b}\bigg)
$$
where $a$ and ...
- 20.8k
3
votes
2
answers
1k
views
Number of six digit numbers divisible by $3$ but none of the digits is $3$
Find number of six digit numbers divisible by $3$ but none of the digits is $3$
My try:
Let the six digits are $a,b,c,d,e,f$ such that
$$a+b+c+d+e+f=3p$$
where $1 \le p \le 18$
Now since $a \ge 1$...
- 10.2k
3
votes
2
answers
204
views
Prove that $x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$
Prove that for every $x,n \in \mathbb{N}$ holds
$$x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$$
This is so called MacMillan Double Binomial Sum, see Mathworld - Power, ...
- 558
2
votes
1
answer
219
views
Are there any power identities which don't belong to this list?
The problem of finding expansions of monomials, binomials etc. is classical and there is a lot of beautiful solutions have been found already, the most prominent examples are
Binomial Theorem, ...
- 558
3
votes
3
answers
200
views
A conjecture on the sum of binomial coefficients
I am looking for a proof, disproof or counter example of the following claim.
Let $C = \{k_1, k_2, \ldots, \}$ be a strictly increasing infinite sequence of positive integers which have a certain ...
- 20.8k
2
votes
2
answers
279
views
Concerning the identity in sums of Binomial coefficients
Let be the following identity
$$\sum_{k=1}^{n}\binom{k}{2}=\sum_{k=0}^{n-1}\binom{k+1}{2}=\sum_{k=1}^{n}k(n-k)=\sum_{k=0}^{n-1}k(n-k)=\frac16(n+1)(n-1)n$$
As we can see the partial sums of binomial ...
- 558
7
votes
5
answers
276
views
On existence of positive integer solution of $\binom{x+y}{2}=ax+by$
How can I prove this?
Prove that for any two positive integers $a,b$ there are two positive integers $x,y$ satisfying the following equation:
$$\binom{x+y}{2}=ax+by$$
My idea was that $\binom{x+...
- 376
27
votes
1
answer
1k
views
What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?
What is known about the asymptotic order and/or lower and upper bound of the sum of the binomial coefficients
$$
S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p}
$$
where the ...
- 20.8k
2
votes
1
answer
165
views
Proof of Gaussian coefficients identity
I want to show the identity $\bigl[\!\begin{smallmatrix} n \\ k \end{smallmatrix}\!\bigr]_q=\bigl[\!\begin{smallmatrix} n-1 \\ k-1 \end{smallmatrix}\!\bigr]_q+q^k\bigl[\!\begin{smallmatrix} n-1 \\ k \...
- 1,381
7
votes
1
answer
540
views
A conjecture about big prime numbers
The fact that each prime number (greater than $9$) ends with one of the four digits $1,3,7,9$, allows us to classify the tens in which the primes are found according to which of these four digits, ...
user559615
10
votes
0
answers
357
views
Dissecting the complexity of prime numbers
Each prime number greater than $9$, written in base $10$, ends with one of the four digits $1,3,7,9$. Therefore, each ten can be classified according to which of these four digits, summed to the ten, ...
user559615
0
votes
2
answers
204
views
Show that $\binom {2n}n \leq(2n)^{\pi (2n)}$ where $\pi(2n) $ is number of prime number less than $2n$
Show that $$\binom {2n}n \leq(2n)^{\pi (2n)}$$
where, as usual, $\pi(2n) $ is number of prime number less than $2n$.
I was solving basic techniques of combinatorial theory by Daniel Cohen.
I was ...
- 103
3
votes
3
answers
177
views
Divisibility of Sum of Equally Spaced Binomial Coefficients
According to a numerical calculation I did for small values of $k$, it appears that the following is true.
$$4|\left[\sum_{j=1}^{n-1}\binom{3n}{3j}\right]$$ or $$\sum_{j=1}^{n-1}\binom{3n}{3j}=4p, p\...
- 1,803
6
votes
1
answer
213
views
Periodic sequences resulting from a summation over the Thue–Morse sequence
Let $s_2(n)$ denote the sum of digits of $n$ in base-2 (OEIS sequence A000120), and $t_n=(-1)^{s_2(n)}$. Note that $t_n$ is the signed Thue–Morse sequence (OEIS sequence A106400), satisfying the ...
- 47.3k
1
vote
1
answer
213
views
Binomial Coefficient divisibility involving Multiples
Good afternoon. I'm looking for a proof, or a counterexample that, given $n,k,N\in\mathbb{Z}$, with $n>k>0$, $N\ge2$,
$$(N+1)|\binom{nN}{kN}$$
Just using the definition,
$$\binom{nN}{kN}=\frac{(...
- 8,837
2
votes
2
answers
2k
views
Is there a formula for sum of all nCr for a given n, such that r varies from 0 to n in steps of 4.
I am trying to compute the number of possible ways, in which $r$ objects can be chosen from a bin containing $n$ distinct objects, such that $r$ is a multiple of $4$. ($r$ can be $0$).
$$\sum_{i=0}^{\...
8
votes
5
answers
312
views
Show that $ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k $ is divisible by $2^n$
I want to prove that
$$
\sum_{k=0}^{n} \binom{2n+1}{2k} 3^k = \sum_{k=0}^{2n} \binom{2n}{k} 3^{\lceil k/2 \rceil}
$$
is divisible by $2^n$.
I tried induction the following way
\begin{align*}
\...
- 18.2k
3
votes
3
answers
704
views
Is it true that $\sum_{k=0}^m\binom{n-k}k$ outputs the $(n+1)$th Fibonacci number, where $m=\frac{n-1}2$ for odd $n$ and $m=\frac n2$ for even $n$?
Does $$\sum_{k=0}^m\binom{n-k}k=F_{n+1}$$ where $m=\left\{\begin{matrix}
\frac{n-1}{2}, \text{for odd} \,n\\
\frac n2, \text{for even} \,n
\end{matrix}\right.$ hold for all positive integers $n$?
...
- 27.1k
3
votes
2
answers
127
views
$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$
I got quite some trouble trying to prove this.
$$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$$
I tried using $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$$ and then ...
- 378
3
votes
1
answer
149
views
Sum of spaced binomial coefficients as a Congruence
Suppose that I have a recurrence relation
$$\sum_{k=0}^n\binom{mn}{mk}A(mk)=0 \Rightarrow A(mn)=-\sum_{k=0}^{n-1}\binom{mn}{mk}A(mk)$$
with conditions $A(0)=1$, and $A(n)=0$ if $n\not\equiv 0\pmod{...
- 866
4
votes
3
answers
155
views
Does $n+1$ divides $\binom{an}{bn}$?
Suppose that $a>b>0$ be integers. Is it true that for an integer $n>2$ that
$$n+1|\binom{an}{bn}$$
or is there a counter example. Certainly i think the right hand side would reduce to
$$\...
- 866
1
vote
3
answers
51
views
Show ($n+1$)$2^n$ = $\sum_{i\geq 0}^{} {n + 1\choose i}i$ algebraically. [duplicate]
Show ($n+1$)$2^n$ = $\sum_{i\geq 0}^{} {n + 1\choose i}i$ algebraically.
I know $2^n$ = $\sum_{i\geq 0}^{} {n\choose i}$. But how do I manipulate the $(n+1)$ to make it look like the right side?
- 87
0
votes
2
answers
420
views
Prove Prove $n2^{n - 1}$ = $\sum_{i\geq 0}^{} {n \choose i}i$ algebraically and using induction.
Suppose $n \in$ natural numbers.
Prove $n2^{n - 1}$ = $\sum_{i\geq 0}^{} {n \choose i}i$
I have proven it combinatorially. Just having troubles algebraically and using induction.
- 87
14
votes
1
answer
352
views
are there known cases where $\binom{n}{k}$ is a perfect prime power?
I was wondering about cases where $\binom{n}{k}=p^j$ with $p$ a prime (nontrivially, so that $ n-k>1$ and $n \neq p^j$.) I had the terrible idea of checking binomial expansions
$$(x+y)^n \equiv x^n+...
- 21k
8
votes
1
answer
172
views
Largest power of $p$ which divides $F_p=\binom{p^{n+1}}{p^n}-\binom{p^{n}}{p^{n-1}}$ [closed]
I would like to know your comments in order to obtain the largest power of the prime number $p$ which divides
$$
F_p=\binom{p^{n+1}}{p^n}-\binom{p^{n}}{p^{n-1}}.
$$
I proved the largest power that ...
- 649
2
votes
2
answers
114
views
How to check if $k$ divides $\binom {n - 1} {k - 1}$ cheaply?
I'm writing a computer algorithm to do binomial expansion in C#. You can view the code here; I am using the following identity to do the computation:
$$
\dbinom n k = \frac n k \dbinom {n - 1} {k - 1}...
- 353