Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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.] –  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
1  
But the i for the second summation represent the value of the first summation –  ken Nov 19 '11 at 5:00
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. –  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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.