0
$\begingroup$

Let n be a positive integer, and assume that j is a positive integer not exceeding $n/2$. Show that in $n \cdot (n-1)\cdot (n-2)\dotsm(n-j+1)\,/\,j!$, if one alternates the multiplications and divisions, then all of the intermediate values in the calculation are integers. Show also that none of these intermediate values exceed the final value

I think the question is asking to show that every term in the denominator is a factor of some term in the numerator. (?) If so, for j = 1, the above is just n/1 which is an integer and is equal to the final value.

For $n = {}$even, $j = n/2$,

$$\frac{n(n-1)(n-2) \dotsm (n/2+1)}{(n/2)(n/2-1)(n/2-2) \dotsm 1} =\frac{2^{n/2}n(n-1)(n-2) \dotsm (n/2+1)}{n(n-2)(n-4) \dotsm 2} =\frac{2^{n/2}(n-1)(n-3) \dotsm (n/2+1)}{(n/2)(n/2-2) \dotsm 2}$$

For $n = {}$odd, $j = (n - 1)/2$,

$$\frac{n(n-1)(n-2) \dotsm (n/2+3/2)}{(n/2-1/2)(n/2-3/2)(n/2-5/2) \dotsm 1}=\frac{2^{(n-1)/2}n(n-2)(n-4) \dotsm (n/2+3/2)}{(n/2+1/2)(n/2-3/2) \dotsm 2}$$

For both cases above, I was able to cancel out half of the terms in the denominator (and I believe their quotient are all $2$ which should not exceed the final value of any $\binom{n}{ \lfloor n/2 \rfloor}$ (?), but am unsure how to show that each term in the half that are left are factors of terms in the numerator or do not exceed the final value.

$\endgroup$
0
$\begingroup$

The numerator has $j$ consecutive factors and since $j \leq n/2$ all of them are strictly greater than $j$. For any given integer $1\leq k \leq j$ it is always possible to find a multiple of it in a sequence of $k$ or more consecutive integers so one can proceed algorithmically. Call $I$ the interval $\{m \in \mathbb{N} : n-j+1 \leq m\leq n\}$

  1. Find $n_j \in I$ such that $n_j \equiv 0 \mod{j}$
  2. Find $n_{j-1} \in I\setminus\{n_j\}$ such that $n_{j-1}\equiv 0\mod{j-1}$,
  3. Keep iterating $\ldots$ (see later why this is allowed)

Each factor $n_k/k$ is integer by construction and is also bigger than one because, as we said earlier, each $n_k$ is bigger than $j \geq k$. Since we multiply factors bigger than one the overall result must be bigger than each factor.

The only thing we yet have to show is that the algorithm works after step 1. For each $k$ we are guaranteed to find $n_k\in I$ but we need to show that it is also possible to find it in $I \setminus \{n_{k+1},\ldots ,n_j\}$. This is motivated as follows: multiples of $k$ that are also multiples of $k' > k $ are multiples of $pk = \mathrm{lcm}(k,k')$ with $p > 1$. The subset of $I$ of all multiples of $p k$ is a strict subset of all multiples of $k$ in $I$ because, for $k < j$, there is at least an entire period contained within $I$.${}^1$


$\qquad{}^1$ By this I mean that there is a subinterval of consecutive integers that goes through all remainders $\mod k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.