1
$\begingroup$

I have a function that I am trying to formally describe, that works as follows:

$$T_0(n)=1 \\ T_1(n)=n \\ T_2(n)=\sum_{i =1}^n i \\ T_3(n)=\sum_{j=1}^n \sum_{i=1}^j i \\ T_4(n)=\sum_{k=1}^n \sum_{j=1}^k \sum_{i=1}^j i $$ and so on.

I'm looking to generalize it to the form $T_k(n)$, where all $k$ are natural numbers zero-inclusive and all $n$ are natural numbers zero exclusive. How would I define this function using formal notation?

Furthermore, these types of functions are of some interest to me, specifically regarding applications in evaluating higher-dimensional space, could you point me towards the name of this type of function and subjects like it?

Update

So it seems I may have accidentally discovered combinations. Thanks 10th-grade stats. However, I still do wonder if there is a formal way to describe repeated successive applications of functions and operators, like the summation. Full points for anyone who answers $n+k-1$ choose $k$, but for future use I'd really like to see how you'd notate repeat application like this. I understand you could define it recursively, are there any other options?

$\endgroup$
1
  • $\begingroup$ I suppose you could write $$T_k(n) = \sum_{i_1=1}^n\sum_{i_2=1}^{i_1}\sum_{i_3=1}^{i_2}\cdots\sum_{i_k=1}^{i_{k-1}}1,$$ but that's a lot more confusing than the recursive form. $\endgroup$
    – user856
    Nov 28 '16 at 23:10
2
$\begingroup$

To answer the first question, define them recursively: $T_0(n)=1$, and

$$T_{k+1}(n)=\sum_{i=1}^nT_k(i)$$

for each $k\in\Bbb N$. However, they can also be defined explicitly: it turns out that $T_k(n)=\binom{n+k-1}k$. This is easily verified by induction, using the recursive definition of the functions.

$\endgroup$
0
0
$\begingroup$

$T_0 = {n\choose 0}\\ T_1 = {n\choose 1}\\ T_2 = {n+1\choose 2}$

Do you think you can come up with a proof that $T_m = {n+m-1\choose m}$?

$\endgroup$
3
  • $\begingroup$ Yes, I was too quick. How about this revision. $\endgroup$
    – Doug M
    Nov 28 '16 at 22:58
  • $\begingroup$ To fit the pattern you'd want $T_0$ to be ${n-1}\choose 0$, wouldn't you? $\endgroup$
    – user856
    Nov 28 '16 at 23:08
  • $\begingroup$ ${n-1\choose 0} = {n\choose 0} = 1$ I suppose you are right, but the pattern doen't become interesting until we get to 2 and above. $\endgroup$
    – Doug M
    Nov 28 '16 at 23:30
0
$\begingroup$

While not technically a direct notation for repeatedly applying summation, if you consider that multiplication is defined as repeated additions, and that the summations above essentially encapsulate multiplication by increasing sequential integers, the function can be expressed as rising factorials. Using Pochhammer notation, this function can be written $$T_k(n) = \frac{n^{(k)}}{k!}$$

Alternatively, it can be written using the notation preferred by Ronald Graham, Donald Knuth and Oren Patashnik among others

$$T_k(n) = \frac{n^{\bar{k}}}{k!}$$

Regardless of notation, both of these expand to the following, which is equivalent to the function produced by the compounding summations.

$$T_k(n) = \frac{n(n+1)(n+2)\cdots(n+k-1)}{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.