Spring 2016, problem 13

Consider the binomial coefficients $\binom{n}{k}=\frac{n!}{k!(n-k)!}$, where $k\in\{1,2,\ldots, n-1\}$. Determine all positive integers $n$ for which $\binom{n}{1},\binom{n}{2},\ldots ,\binom{n}{n-1}$ are all even numbers.


5 years ago

Hi, I'm Hubert from Paris ... Luca's theorem shows that $n=2^q$;

using the Wikipedia article notations with $p=2$ we want $N=\binom mn$ even for $1\leq n\leq m-1$,

  • if $m$ is not a power of $2$, then $m_k=m_j=1$ for some $j\lt k$ and the given formula says $\binom m{2^j} \equiv \binom 11 (mod\; 2)$ with $n_j=1,\; n_k=0, \; k\neq j$, odd;

  • now if $m=2^k,\; m_j=0,\; j\lt k$ and $n\lt m\Rightarrow~n_k=0$, and at least one of the $n_0,n_1,\cdots n_{k-1}$ is one, putting a $0=\binom 01$ in the given product, for each $n\in(0,m)$, making each $N$ even.

Note: this strange $\lt$ is the symbol "less than", can someone fix that ?

I need your help now ... :-(

The browser interprets the < as the start of an html tag or something like that. Use \lt and \leq inside $ signs instead.

Nelix 5 years ago
5 years ago

The number $n$ has the required property, if and only if $n = 2^k$ for some positive integer $k$.

I suspect, there's a nice proof for that, involving the binomial theorem and a little group theory, but all I could come up was this rather calculational Proof:

[The notation $\lfloor x \rfloor := floor(x)$ and $\lceil x \rceil := ceil(x)$ is used throughout.]

For every natural $a$, define $\nu(a) := b$, where $b$ is the largest integer, such that $2^b$ divides $a$. Or put another way: $\nu(a)$ is the numbert of twos in the prime factorization of $a$.

A particular case of a result known as Legendre's formula states, that for all $a \in \mathbb{N}$:

$\nu(a!) = \sum_{i=1}^{\infty} \lfloor \frac{a}{2^i} \rfloor$

Also, from the definition of the binomial coefficients, we have:

$\nu ( \binom{n}{k} ) = \nu(n!) -\nu(k!) - \nu([n -k]!)$ (*)

Now assume, that $n$ is not a power of 2. So $n$ lies strictly between two powers $2^j$ and $2^{j + 1}$ of two, i.e. there are $j,r \in \mathbb{N}$, with $0 \lt r \lt 2^j$, such that $n = 2^j + r$.

Then $\nu(n!) = \nu([2^j + r]!) = \sum_{i=1}^{\infty} \lfloor \frac{2^j + r}{2^i} \rfloor = \sum_{i=1}^{j} 2^{j-i }+\lfloor \frac{r}{2^i} \rfloor = \nu([2^j]!) + \nu(r!)$. Note, that the second manipulation only works, because we assume, that $r \lt 2^j$. Plugging this into the equation (*), we get:

$\nu ( \binom{n}{2^j} ) = \nu ( \binom{2^j + r}{2^j} ) = \nu([2^j]!) + \nu(r!) - \nu([2^j]!) - \nu(r!) = 0$

Therefore $\binom{n}{2^j}$ is odd so that $n$ does not have the property required in the problem statement.

This concludes the first half of the proof. We now assume, that $n = 2^j$ for some $j \in \mathbb{N}$ and prove it does indeed have said property.

Pick a $k \in \mathbb{N}$, such that $0 \lt k \lt 2^j$. Then:

$\nu ( \binom{n}{k} ) = \nu ( \binom{2^j}{k} ) = \nu([2^j]!) - \nu([2^j - k]!) - \nu(k!) = \sum_{i=1}^{j} \lceil \frac{k}{2^i} \rceil - \lfloor \frac{k}{2^i} \rfloor$. By the definition of the rounding functions, none of the summands is negative and - from $0 \lt k \lt 2^j$ - the last one is equal to 1. Therefore $\nu ( \binom{n}{k} ) >= 1$ and so $\binom{n}{k}$ is even. This completes the proof.

As an aside, using the general form of Legendre's formula, the proof takes little modification, to show that:

A prime number $p$ divides all of $\binom{n}{1},\binom{n}{2}, \ldots, \binom{n}{n-1}$ iff n is a power of $p$.

3 months ago

Are you looking for a cheap assignment writing service? You are on the right platform; with our services, you will get a good bargain with quality results homework helper. We understand the frugal nature of students and paying for an academic paper is not a priority. However, we assure you of exceptional services at pocket-friendly prices.

2 months ago

The subject of discrete math have always been arduous for me. I've always faced difficulty in solving these complex binomial equations and their deriving their calculation proofs. Thus, at the end of my semester I deliberately went for the option of term paper writing service online, as to stand out in my semester exams without any hurdles. Now after reading this question, all the hurdles and circumstances I faced at that time, flashed back into my memory.

1 month ago

well for any math or physics problem you need to get help from any professional or anyone who can help you out. You can also be in touch with AssignmentMakerUAE who helped me thorugh out my academuc life in my university.

1 month ago

Are you looking for a cheap assignment writing service? Finding the cheap reliable urgent essay writing service is almost impossible task for student who seeking good grades in their academic career. With some good browsing skills and research you can find out cheap reliable urgent essay writing service reviews. Some of the good ways are:Check online for discount codes,Promotional offers,Always keep in mind “Cheaper Isn't Always Better” so not only look for cheap price but also check the quality too.

2 weeks ago

This is very nice and awesome robux generator no human verification 2021 post all time thanks for share it.

2 weeks ago

Argentics is a very cool company with which I had a chance to cooperate at one time, because there are professionals in their field who know a lot about creating games, design and cool art, which helped us a lot and made several cool orders for our team, after which we and our staff were absolutely delighted.

2 weeks ago

If you are facing the problem of math, physics and chemistry, and you want to get the help from experts for your assignments. you can contact to experts assignment writing service in dubai. Who available 24/7 to help you.

1 week ago

Nice article, thanks for sharing سئو - آموزش سئو - خدمات سئو

Post an answer:

To post an answer, please log in