# A composition on finite sequence

I conjectured that $\left(\sum _ {i_k = 1} ^ n\right) ^ k i = {_{n+k} C _ {k+1}}$ where $n , k \in \mathbb N$ and $i_k = \left(\sum _ {i_{(k-1)} = 1} ^ n\right) ^ {(k-1)} i$. The notation I adopted is similar with the notation used for composition of function $f^2 (x) = f(f(x)) \neq (f(x))^2$. Now if for a specific natural number $k$ is given, then the conjecture can be proved using mathematical induction. But how can we prove for any $k$. Thank you.

-
I do not follow your notation. Your explanation "The notation I adopted is similar with the notation used for composition of function $f^2(x)=f(f(x))$" is also a little cryptic. Can you clarify what you mean? [Perhaps explicitly writing out what you mean for $k=2$ might help.] –  Srivatsan Nov 19 '11 at 4:35
Suppose k = 2. $(\sum _ {i= 1} ^ n) ^ k i = _{(n+k)} C _ {(k+1)}$ will become $\sum_{i= 1} ^ n \sum_{i= 1} ^ n i =\frac {(n+2)!}{3! (n-1)!}$. I hope it helps. –  ken Nov 19 '11 at 4:52
But the i for the second summation represent the value of the first summation –  ken Nov 19 '11 at 5:00
@Srivatsan: my guess (ken please confirm or deny) is $\sum_{i= 1} ^ n \sum_{i= 1} ^ n i =\sum_{i= 1} ^ n \frac{n(n+1)}{2}$ (which should be) $\sum_{i= 1} ^ n \frac{i(i+1)}{2}=\frac{n(n+1)(2n+1}{12}+\frac{n(n+1)}{2}$ but that doesn't equal $\frac {(n+2)!}{3! (n-1)!}$ ken, you should use different dummy variables in the nested sums-one should use $j$ for example. –  Ross Millikan Nov 19 '11 at 5:27
Yes. thank you.@ Ross Millikan: Thank you for the notation and the answer. :) –  ken Nov 19 '11 at 5:32

Your conjecture is correct. For comfort, we use a more familiar notation. Let $$f_1(n)=\sum_{i=1}^{n} i =\binom{n+1}{2}.$$ Define the functions $f_k$ recursively by $$f_{k+1}(n)=\sum_{i=1}^n f_k(i).$$ We want a closed form for $f_k(n)$. To this end, we use the important fact $$\binom{N+1}{m+1}=\sum_{i=1}^{N+1}\binom{i}{m}\qquad\qquad(\ast)$$ (the binomial coefficients $\binom{i}{m}$ are $0$ if $i<m$, so they do no harm). This fact can be proved in many ways. The neatest is the combinatorial approach. We wish to choose $m+1$ numbers from the numbers $1, 2, \dots, N+1$. We count the number of such choices in two different ways.
First way: By definition, the number of choices is $\binom{N+1}{m+1}$.
Second way: The largest number in our chosen set of $m+1$ numbers could be $N+1$. In that case, there are $\binom{N}{m}$ ways of choosing the rest. Or else the largest chosen number could be $N$, in which case there are $\binom{N-1}{m}$ ways of choosing the rest. And so on. Add up. We get the sum on the right-hand side of $(\ast)$, written backwards.
The two ways each count the number of choices, so the answers they give must be the same. This completes the proof of $(\ast)$.
The rest is straightforward. We have $f_1(n)=\binom{n+1}{2}$. Thus, by $(\ast)$ and the definition of $f_2$, we have $f_2(n)=\binom{n+2}{3}$. Thus, by $(\ast)$ and the definition of $f_3$, we have $f_3(n)=\binom{n+3}{4}$. And so on. The pattern is obvious and can be proved by a formal induction. In general $$f_k(n)=\binom{n+k}{k+1}.$$