0
$\begingroup$

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.

  • 0
    Yes. thank you.@ Ross Millikan: Thank you for the notation and the answer. :)2011-11-19

1 Answers 1

2

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, 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}.$