5

Let $$x=\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1$$ where $n,k\in\mathbb{Z}^+$. How to simplify $x$?

I simplified it for $k=1,2,3$ and I got $n$, $\dfrac12n(n+1)$ and $\dfrac16n(n+1)(n+2)$. From this I assumed that for any $k$: $$x=\dfrac n{k+1}{\binom{n+k}{n}}$$ Problem is how to prove it. I tried using mathematical induction, but it seems that this is not an easy way.

  • 6
    It would seem that you are counting the number of $k$ tuples $1\leq a_{k+1} \leq a_k \leq \dots \leq a_2 \leq a_1 \leq n$. – Myself Dec 29 '14 at 18:35
  • 1
    Yes, can you explain how to simplify it? –  Dec 29 '14 at 18:52
  • 3
    @Mathematician171 Have you tried the cases $k=1$; $k=2$? Induction will help. – Pedro Dec 29 '14 at 18:54
  • 5
    @Mathematician171 what Myself meant was $$\sum_{a_1=1}^n\sum_{a_2=1}^{a_1}\sum_{a_3=1}^{a_2}\dots\sum_{a_{k+1}=1}^{a_k}1 = \sum\limits_{1 \le a_{k+1} \le a_k \le \cdots\le a_1 \le n} 1$$ Basically we are counting the number of $k+1$-tuples $(a_1,a_2,\cdots,a_{k+1})$ with the property that: $$1 \le a_{k+1} \le a_k \le \cdots\le a_1 \le n$$ That is $k+1$-tuples $(b_1,\cdots,b_{k+1})$ such that: $1 \le b_{k+1} = a_{k+1} < a_k+1 < b_k = a_{k-1}+2 < \cdots < b_ 1 = a_1 + k \le n+k$ Also we know the number of ways of choosing $k+1$ distinct integers from ${1,2,\cdots,n+k}$ is $$\binom{n+k}{k+1}$$ – r9m Dec 29 '14 at 19:01
  • @Winther $1+2+3+\ldots + n = \binom{n+1}{2}$ :-) – r9m Dec 29 '14 at 19:09
  • @r9m I'm a idiot. Thanks:) – Winther Dec 29 '14 at 19:10
  • 2
    Another way to do this is to notice the relation between the sum for $k$ and for $k-1$. If $x_k(p)$ is the number of $k$ tupples (your sum) satisfying $a_{k+1}\leq a_k \leq \ldots \leq a_1 \leq p$ then we have (why?) $x_k(n) = x_{k-1}(1) + x_{k-1}(2) + \ldots + x_{k-1}(n)$ The identity $\sum_{p=1}^n{p+k\choose k+1} = {n+k+1\choose k+2}$ plus can be useful to use this for an induction proof. – Winther Dec 29 '14 at 19:25

1 Answers1

1

The sum is the same as the number of ways for choosing $(k+1)$-tuple $(a_1,a_2,\ldots,a_{k+1})$ such that $1\leq a_{k+1}\leq a_{k}\leq \ldots a_1$. The different possibilities can be broken down as follows:

  • All number are distinct: This is same as choosing $k+1$ distinct numbers from the set $\{1,2,\ldots,n\}$ sorting them. Thus, this can happen in $\binom{n}{k+1}$ ways.
  • $l$ repetitions are allowed: We note that repetitions happen only at consecutive locations as the tuples entries are in the descending order. Therefore, there are $\binom{k}{l}$ possible locations for repetition. Therefore, we first choose $k-l$ distinct numbers from the set $\{1,2,\ldots,n\}$ and $l$ locations for repetition, to form a valid tuple. Thus, this can happen in $\binom{n}{k+1-l}\binom{k}{l}$ ways.

Thus, we have \begin{align} \sum_{a_1=1}^{n}\sum_{a_2=1}^{a_1}\ldots \sum_{a_{k+1}=1}^{a_{k}}1 &= \sum_{l=0}^{k} \binom{n}{k+1-l}\binom{k}{l} \\ &=\sum_{l=0}^{k+1} \binom{n}{k+1-l}\binom{k}{l} - \binom{n}{0}\binom{k}{k+1}\\ &= \binom{n+k}{k+1}. \end{align} Here, we use Vandermonde's identity to get the last step. The result also agrees with your formula: \begin{equation}\frac{n}{k+1}\binom{n+k}{n} = \frac{n(n+k)!}{n!k!(k+1)}=\frac{(n+k)!}{(n-1)!(k+1)!} =\binom{n+k}{k+1}. \end{equation}

Explorer
  • 3,147