All Questions
96
questions
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+...
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 ...
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 \...
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, ...
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, ...
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 ...
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\...
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 ...
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{(...
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*}
\...
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$?
...
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 ...
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{...
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
$$\...