In some research I'm doing, I've come across some coefficients I'm calling $\alpha^{n}_{j}$, where $$ \alpha^{n}_{j} = \sum_{k_1 = 1}^{n} \sum_{k_2 = 1}^{n-k_1} ... \sum_{k_j = 1}^{n - k_1 - k_2 -... - k_{j-1}}1, \quad \text{ where }\quad \sum_{m=1}^{p<1}1 = 0 $$

For every coefficient I have computed, I've found $\alpha_{j}^{n} = {n\choose j}$. However, I am struggling to prove this. Does anybody have any advice?

By looking at some combinations, I've convinced myself of the following:

$$\alpha_{j}^{n} = 1 + \sum_{k = 1}^{n-j} \sum_{l = 1}^{k} {k-1 \choose l-1}{j \choose l}, \quad \text{ where }\quad{p<m \choose m}=0$$

I'm not sure what the next step to proving this would be though, or if this is the right track.

  • 1
    $\begingroup$ Hi, welcome. What does $\sum_{m=1}^{p < 1} 1 = 0$ mean? And do you mean $\alpha_j^n = \binom{n}{j}$? $\endgroup$ – Matthew Leingang May 24 at 14:54
  • 3
    $\begingroup$ @MatthewLeingang I assume he means that the sum with lower bound $1$ and upper bound anything less than $1$ results in the empty-sum which evaluates to zero. $\endgroup$ – JMoravitz May 24 at 14:56
  • $\begingroup$ Aha, so it's not a constraint, but a notational convention. $\endgroup$ – Matthew Leingang May 24 at 14:57
  • $\begingroup$ for p less than m any possible value of m, the sum will be 0. So anytime $k_1 +k_2 +... + k_i \geq n$, there will be no contribution to the total sum. $\endgroup$ – Willyazaa May 24 at 14:57
  • $\begingroup$ @saulspatz yep, thanks. I fixed it $\endgroup$ – Willyazaa May 24 at 14:59

Your initial expression could be rewritten as

$$\sum_{k_1+k_2+\cdots+k_j\leq n}1$$ where additionally you require each $k_i\geq 1$, i.e. it counts the number of ordered tuples $(k_1,\ldots,k_j)$ with sum at most $n$.

Now there is a transformation between such tuples and subsets of $1,...,n$ of size $j$. The numbers $k_1,k_1+k_2,k_1+k_2+k_3,...$ are all different and in the range $1,...,n$. Conversely for any set of $j$ numbers between $1$ and $n$ there is such a tuple: make $k_1$ the smallest number in the list, $k_2$ the difference between the smallest and second-smallest, and so on. So there is a 1-to-1 correspondence between these tuples and combinations of $j$ numbers from $1,...,n$ - but the number of those is $\binom nj$ by definition.



$$ \eqalign{ & \sum\limits_{0\, \le \,k\, < \,n} 1 = n = \left( \matrix{ n \cr 1 \cr} \right) \cr & \sum\limits_{0\, \le \,k\, < \,n} {\sum\limits_{0\, \le \,j\, < \,n - k} 1 } = \sum\limits_{0\, \le \,k\, < \,n} {\left( \matrix{ n - k \cr 1 \cr} \right)} = \sum\limits_{0\, < \,k\, \le \,n} {\left( \matrix{ k \cr 1 \cr} \right)} = \sum\limits_k {\left( \matrix{ n - k \cr n - k \cr} \right)\left( \matrix{ k \cr k - 1 \cr} \right)} = \left( \matrix{ n + 1 \cr n - 1 \cr} \right) = \left( \matrix{ n + 1 \cr 2 \cr} \right) \cr & \quad \vdots \cr} $$

while, starting the sums from $1$
$$ \eqalign{ & \sum\limits_{1\, \le \,k\, \le \,n} 1 = n = \left( \matrix{ n \cr 1 \cr} \right) \cr & \sum\limits_{1\, \le \,k\, \le \,n} {\sum\limits_{1\, \le \,j\, \le \,n - k} 1 } = \sum\limits_{1\, \le \,k\, \le \,n} {\left( \matrix{ n - k \cr 1 \cr} \right)} = \sum\limits_{0\, \le \,k\, \le \,n - 1} {\left( \matrix{ k \cr 1 \cr} \right)} = \sum\limits_k {\left( \matrix{ n - 1 - k \cr n - 1 - k \cr} \right)\left( \matrix{ k \cr k - 1 \cr} \right)} = \left( \matrix{ n \cr n - 2 \cr} \right) = \left( \matrix{ n \cr 2 \cr} \right) \cr} $$


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.