I joined RSA a few weeks ago. Here, I
met Anoop who loves playing with combinatorics problems. We challenge
each other with combinatorics problems.

I asked him the following question at lunch.

For integers n ≥ 1 and k ≥ 1,

f_{0}(n) = 1.

f_{k}(n) =
Σ^{n}_{i=1} f_{k−1}(i).

Find a closed formula for f_{k}(n).

He asked me one on programming. I have used subscripted variables to
represent the counters for the nested loops in the pseudocode to show
the question.

Consider the following pseudocode with k nested loops.

count = 0
for c_{1} in 1 to n:
for c_{2} in 1 to c_{1}:
for c_{3} in 1 to c_{2}:
…
for c_{k} in 1 to c_{k−1}:
count = count + 1

What is the final value in `count`

after the outermost loop
terminates?

With one question each, we went back to our desks. As I started solving
his question on nested loops, I realized that his problem led me to the
recurrence relation in the question I asked him. If k = 1,
count = n. This is also the value of f_{1}(n). If
k = 2, the inner loop with the counter as c_{2} will
run once when c_{1} = 1, twice when
c_{1} = 2, and so on. So, the final value of count
will be
f_{1}(1) + f_{1}(2) + … + f_{1}(n) = n(n + 1)/2.
This is the value of f_{2}(n) as well.

Extending this argument, one may realize that for any k, count = f_{k−1}(1) + f_{k−1}(2) + … + f_{k−1}(n) = f_{k}(n). In other words, the answer to his question is the
answer to my question. I already knew the answer to this. So, I went
back to his desk with the answer: C(n +k −1, k).

I had arrived at this closed formula earlier by solving f_{k}(n)
for the first few k's using Faulhaber's
formula. I noticed that they were all equal to
C(n + k − 1, k). So, I
proved that this is always true by the principle of strong mathematical
induction. It involved proving that:
f_{k+1}(n) = C(k, k) + C(k + 1, k)
+ … +
C(n + k − 1, k) = C(n + k, k + 1)

This was a remarkable coincidence that we asked each other questions
which had the same answer. When I explained the coincidence to him, he
explained how he arrived at the same result for the question on
nested loops which can be used to determine the closed formula for the
recurrence relation too.

In the question on nested loops, the following condition is always met:
n ≥ c_{1} ≥ c_{2} ≥ … ≥ c_{k} ≥ 1.
So, the number of times `count`

variable would be incremented
is equal to the number of possible ways we can arrange k numbers from
the first n natural numbers in descending order. The answer to this is
the number of possible ways we can arrange n − 1 similar
balls and k similar sticks. If we consider the number of balls to the
right of the ith stick and add one to it, we get a valid value for
c_{i} as the number of balls to the left of a stick can not
increase as we move right and consider (i + 1)th,
(i + 2)th, etc. sticks. Similarly, the number of balls to the
left of a stick can not decrease as we move left and consider
(i − 1)th, (i − 2)th, etc. sticks.
Also, any set of valid values for c_{1}, c_{2},
…, c_{k} can be represented as an arrangement of these
sticks and balls.

We can arrange n − 1 similar balls and k similar sticks
in
^{(n + k − 1)! }⁄_{ (n − 1)! · k!}
= C(n + k − 1, k) number of ways. This is
the answer to the question on nested loops as well as that on the
recurrence relation.