# Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $${\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{*}$$

It has been my wish to prove the following statement: the above formula can never be equal to $p^2$ for $p$ a prime, for any $i$ such that $1 \leq i \leq n-1$.

I induct on $i$ as follows:

Base Case: $i = 1$. Then the above formula becomes ${n + k - 1\choose k}$, which, through the kind efforts of some members of this site, was able to be proven to never be equal to $p^2$ (I have also separately shown that it is never equal to $p$, which becomes relevant at the end of the post).

Now inductively assume the above statement for general $j$. I wish to show that it holds for $i = j +1$.

For $i = j+1$, the formula becomes, if we set $m := n + k$ for simplicity: $${{m -1 \choose 1}{m - 2 \choose 2}\cdots {m - j-1\choose k} \over {k + 1 \choose k }{k + 2 \choose k}\cdots {k + j \choose k }}$$ By the inductive hypothesis, the terms correspond to $i = j$ cannot be equal to $p^2$ i.e., $$\underbrace{{{m -1 \choose 1}{m - 2 \choose 2}\cdots {m - j\choose k} \over {k + 1 \choose k }{k + 2 \choose k}\cdots {k + j-1 \choose k }}}_{\ne p^2 \text{ by IH}} \cdot \underbrace{{{n + k - j-1\choose k} \over {k + j \choose k }}}_{(\dagger)} \stackrel{?}{=} p^2$$

Here my argument is ad hoc

However, since the underlined portion of the left hand side of the equation cannot be equal to $p^2$, it must have distinct prime factors other than $p$. Thus, if the equation were to hold, ${k + j \choose k}$ would not only have to cancel all non-$p$ prime factors from the underbraced left hand portion, but would also have to cancel all non-$p$ factors from ${n + k - j-1\choose k}$. Since $i$ runs between $1$ and $n -1$, $j$ can range from $0$ to $n - 2$.

I suppose I'm stuck here at this point in the proof. It seems impossible, but I'm not sure how to rigorously show that. Is it enough that the underbraced portion cannot be equal to $p^2$, and since the underbraced portion must be an integer (the product in $(*)$ is always equal to a positive integer), that implies that the right hand portion i.e., $(\dagger)$ must be an integer, and since $p^2$ cannot be formed by multiplying two integers, one of which has no factors of $p$, we are done?

Many thanks for taking the time to read through this. Regards.

-
I supposed somewhere the condition $k \ge 2$ was in this, since for $k=1$ and any $n$, taking $i=n-1$ makes your ratio of products simplify to $n$, so that the product ratio takes on all values. YES -- I just checked back on previous question of yours which you alluded to. The condition that $k \ge 2$ should be mentioned right away in the posted question, in my opinion. – coffeemath Jun 15 '13 at 6:01
@coffeemath when you say "yes" are you confirming that I do indeed have this right? I have added the $k \geq 2$ condition thanks for this input. Regards. – Moderat Jun 16 '13 at 1:28
No I don't (yet) see the validity of the induction step, though it can likely be made to work. The "yes" was to the effect that I found in the other question a good reason for the $k \ge 2$ requirement. – coffeemath Jun 16 '13 at 17:47