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.

  • 1
    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.]2011-11-19
  • 0
    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.2011-11-19
  • 1
    But the i for the second summation represent the value of the first summation2011-11-19
  • 1
    @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.2011-11-19
  • 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 $itwo 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}.$$