5
votes
1answer
81 views

Binomial Congruence

How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ for positive integers m and n and p a prime greater than 5? I can do it for mod p^2 but Im stuck here.
6
votes
0answers
106 views

Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$

I found this question in an old problem set. There's no hint or solution mentioned. For $n \geq 3$, prove or disprove the existence of $(x,y,z) \in \mathbb N^3, ...
1
vote
1answer
20 views

Generalization of Binomial Coefficients Congruence

It is well known and not hard to prove that $\binom{pA}{pB}\equiv\binom{A}{B}\mod p$ where $p$ is a prime. Now, how can we extend to show that this congruence holds $\mod p^2$. Finally, can we extend ...
1
vote
1answer
35 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
0
votes
1answer
52 views

Conditions for which $n | {n \choose k}$ for all $k$

I'm studying for a number theory exam. Our review sheets offers the question: Under what conditions will $n$ divide $n \choose k$ for all 1 $ \leq k \leq n-1$? I can see that this will be true for ...
1
vote
1answer
27 views

Largest K-multiple free set out of a fully ordered set

i'm struggling conceptually with this problem, i don´t know how to approach it in a clever way (without a computer, or at least without a brilliant algorithm). Mathematicians defined a k-multiple set ...
1
vote
2answers
109 views

Help proving ${n \choose k} \equiv 0 \pmod n$ for all $k$ such that $0<k<n$ iff $n$ is prime.

I can prove the $n$ is prime case: If $n$ is prime, then since $k < n$ and $n$ is prime, the factor of $n$ in the numerator won't be cancelled out. So the question boils down to Let an integer ...
1
vote
1answer
86 views

What is the sum of divisors of binomial&factorial

$$\sum_{m|\frac{n!}{i!(n-i)!}} m$$ Perhaps a good start is $$\sum_{m|n!} m$$ When seeing this last sum or also this one $$\sum_{m|lcm(1,2,...,n)} m$$ I sort of want to use $(n+1)n\over2$ somehow.
5
votes
2answers
95 views

Evaluate: $ \sum _ {k=1}^{n}{\frac{k}{n}\binom{n}{k}t^k(1-t)^{n-k}}$

Evaluate: $$ \sum _ {k=1}^{n}{\frac{k}{n}\dbinom{n}{k}t^k(1-t)^{n-k}} $$ $\dbinom{n}{k}$stands for the usual binomial coefficient giving the number of ways of choosing $k$ objects from n objects. ...
4
votes
1answer
238 views

Divisibility of binomial coefficient by prime power - Kummer's theorem

Let's say we have binomial coefficient $\binom{n}{m}$. And we need to find the greatest power of prime $p$ that divides it. Usually Kummer's theorem is stated in terms of the number of carries you ...
10
votes
3answers
582 views

Prove the lecturer is a liar…

I was given this puzzle: At the end of the seminar, the lecturer waited outside to greet the attendees. The first three seen leaving were all women. The lecturer noted " assuming the attendees are ...
0
votes
1answer
70 views

Relation between Binomial coefficient and Stirling number of second type

Is that true, that for every n,k such that $$k>1$$ we have the inequality $${n \choose k} \leq {n \brace k}$$?
3
votes
0answers
44 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 ...
5
votes
4answers
213 views

factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

The successive difference of powers of integers leads to factorial of that power. I think this is the formula $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$ But I found no proof on internet. Please ...
2
votes
0answers
49 views

Bound for squarefree binomial coefficients

Numerical tests up to $x=2000$ seem to suggest that the number of squarefree binomial coefficients is bounded at $\dfrac{112x^{\ y}}{239^{\ y}}$: where ...
3
votes
1answer
99 views

Squarefree binomial coefficients.

At $n=23$, all binomial coefficients are squarefree. Is this the largest value for $n$ where this is the case? Edit A plot up to $n=50$: A plot up to $n=500$: plotted against $n+1$ and ...
4
votes
2answers
89 views

Proofs from the Book - need quick explanation

I've been recently reading this amazing book, namely the chapter on Bertrand's postulate - that for every $n\geq1$ there is a prime $p$ such that $n<p\leq2n$. As an intermediate result, they prove ...
2
votes
5answers
149 views

Proof of binomial coefficient formula.

How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$? This is an accepted fact in every book but i couldn't find a ...
14
votes
2answers
355 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
1
vote
1answer
49 views

About the number of the elements of a set related with binomial coefficients

For $N\in\mathbb N$, let $$P_l(N)=\# \{(n,m)|0\le n\le N, 0\le m\le n,\binom{n}{m}\not\equiv 0 \mod l\}.$$ Suppose that $\binom{n}{0}=1$ for $n\ge 0$ and that $\# S$ represents the number of the ...
14
votes
4answers
374 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ I don't know how to prove this at all. Could you show me how ...
1
vote
0answers
53 views

Smallest $r$ such that $\sum_{k=0,\,\, i+kr = qm}^{\lfloor (n-i)/r \rfloor} \binom{n}{i + kr} = 0 \pmod n$

I want to find the smallest positive integer $r$ such that $$\sum_{k=0,\,\, i+kr = qm}^{\lfloor (n-i)/r \rfloor} \binom{n}{i + kr} = 0 \pmod n$$ where $n=pq$, and every $i+kr = qm$ for some $m$ is ...
0
votes
1answer
118 views

Have you seen this formula for factorial?

Let $p$ always be a prime. $n! = \prod_{p\leq n}p^{\lfloor \frac{n}{p}\rfloor}$. Then $\binom{n}{r} = \prod_{p\leq r}p^{\lfloor n/p \rfloor -\lfloor (n-r)/p \rfloor - \lfloor r/p \rfloor} \times ...
3
votes
2answers
83 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
0
votes
1answer
146 views

Given $p, m$, how many $r, k$ exist such that $\sum_{i=0}^k{m+i \choose p} = {m+r \choose p}$?

I know that ${m+1 \choose p+1} = {m \choose p} + {m \choose p+1}$, does this identity extend further out? My guess is that there exist certain $k$ such that there exists $r > k$ where the title ...
3
votes
1answer
80 views

Bertrand's postulate proof

Regarding http://michaelnielsen.org/polymath1/index.php?title=Bertrand%27s_postulate I think the last inequality should be $4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}$. But even when the RHS is decreased from ...
4
votes
1answer
65 views

how compute $\gcd\Bigl(\binom{n}{1},\binom{n}{2},\binom{n}{3},…,\binom{n}{n-1}\Bigr)?$

how to prove $$\gcd\Biggl(\binom{n}{1},\binom{n}{2},\binom{n}{3},...,\binom{n}{n-1}\Biggr)=\begin{cases} p, & \text{$n=p^m$ ;$p$ is prime} \\ 1, & \text{o.w} \\ \end{cases}$$ thanks in ...
2
votes
2answers
124 views

Stirling's Approximation

A sharp Stirling's approximation form states that $$n! \sim \left(\frac{n}{e}\right)^n\sqrt{2\pi n}.$$ Use that form to show that: $$\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right).$$
2
votes
2answers
94 views

Feature of the Pascal's triangle (OEIS A007318)?

If rows of Pascal's triangle (OEIS's A007318) after their content concatenation {1-1, 1-2-1, 1-3-3-1, 1-4-6-4-1, 1-5-10-10-5-1, 1-6-15-20-15-6-1, 1-7-21-35-35-21-7-1 and so on } be considered as ...
14
votes
3answers
363 views

A relationship between matrices, bernoulli polynomials, and binomial coefficients

We define the following polynomials, for $n≥0$: $$P_n(x)=(x+1)^{n+1}-x^{n+1}=\sum_{k=0}^{n}{\binom{n+1}{k}x^k}$$ For $n=0,1,2,3$ this gives us, $$P_0(x)=1\enspace P_1(x)=2x+1\enspace ...
1
vote
1answer
144 views

Inequality for binomial coefficients

Let $m \leq n, n \leq N$ and $0\leq k \leq m$. I am wondering what is the dependence of $n$ and $N$ that for all $m, k$ $$ \frac{{N-m \choose n-k}}{{N \choose n}}\leq 1. $$ Thank you for your help.
4
votes
2answers
725 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
1
vote
0answers
257 views

The Lucas Theorem and facts

I have studied the Lucas theorem and I encountered the following facts. How to deduce the following facts from The Lucas theorem? (1) If d, q > 1 are integers such that , $$\binom{nd}{md}$$ ...
1
vote
0answers
169 views

Lucas' theorem Consequence

Lucas' theorem consequence $$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$ $$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$ $$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$ ...
0
votes
1answer
394 views

Multi binomial theorem application

If i have the polynomial expression $(a_1x+b_1y+c_1)^p. (a_2x+a_2y+c_2)^d$, and with assumptions $a_1+b_1<<c_1$ , $a_2+b_2<<c_2$, can i expand this as a product of binomials using the ...
14
votes
1answer
1k views

A proof of Wolstenholme's theorem

This was inspired by this question. I tried to use the identity $${2n \choose n}=\sum_{k=0}^n {n \choose k}^2$$ (see this question) to prove that $$\binom{2p}p\equiv2\pmod{p^3}$$ if $p\gt3$ is ...
3
votes
0answers
217 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 ...
13
votes
0answers
441 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: n,k are natural numbers and $k\le n$. t is taken over all ...
3
votes
0answers
310 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 ...
1
vote
1answer
977 views

${n \choose k} \bmod m$ using Chinese remainder theorem?

I don't really see too many sites explaining how this is done. Does anyone know how this works? I'm trying to find $\binom{n}{k}\bmod m$, where $n$ and $k$ are large and $m$ is not prime. I think it ...
1
vote
1answer
382 views

Lucas Theorem for combinatorics?

Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?
0
votes
0answers
100 views

Binomial coefficents with congruencies

I just drawn the following observations in my regular study. I would like to share with other members of this site and I am looking for proof and approach. We know that, the quadratic field ...
1
vote
2answers
193 views

Proof $\binom{2\phi(r)}{\phi(r)+1} \geq 2^{\phi(r)}$

I try to proof the following $$\binom{2\phi(r)}{\phi(r)+1} \geq 2^{\phi(r)}$$ with $r \geq 3$ and $r \in \mathbb{P}$. Do I have to make in induction over $r$ or any better ideas? Any help is ...
16
votes
2answers
338 views

On computing: $ \gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right)$

I would like to calculate $$ d=\gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right) $$ We have: $$ \sum_{k=0}^{n-1}{2n \choose 2k+1}=2^{2n-1} $$ $$ d=2^k, 0\leq k\leq2n-1 $$ ...
7
votes
5answers
337 views

Are there surprisingly identical binomial coefficients?

Suppose $\binom{n}{k}=\binom{n'}{k'}$ with $k \geq 2$, $k' \geq 2$, $n \geq 2k$ and $n' \geq 2k'$. Does it follow that $n=n'$ and $k=k'$? EDIT: Yup, ...
4
votes
1answer
567 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
3
votes
3answers
186 views

Proofs from the BOOK: Bertrand's postulate: $\binom{2m+1}{m}\leq 2^{2m}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 8: It's about the part, where the author says: $$\binom{2m+1}{m}\leq 2^{2m}$$ because ...
20
votes
6answers
4k views

prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the first n even ...
5
votes
3answers
217 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
1
vote
1answer
424 views

Lucas' Theorem and Pascal's Triangle

I have a general question about Lucas' Theorem. Lucas' Theorem says the following: Theorem (Lucas' Theorem) Let $p$ be a prime number. Write $n$ and $k$ in base $p$: $n = a_0 + a_{1}+a_{2}p^{2} + ...