0

Is it possible to simplify this iterated sum

$$f(x)=\sum_{i_{u-1}=u}^{x}\sum_{i_{u-2}=u-1}^{i_{u-1}} \cdots \sum_{i_2=3}^{i_3} \sum_{i_1=2}^{i_2} \sum_{k=1}^{i_1} 1$$

by using a binomial coefficient?

Is this iterated sum still equivalent of $\frac{x^u}{u!}$ ?

This question is related to Iterated sums and asymptotics

In this question, the initial indices are different.

Thank you

Community
  • 1
Dingo13
  • 435
  • Let we solve the case $u=4$ by setting $k=i_0$. By the hockey stick identity we have: $$ \sum_{i_3=4}^{x}\sum_{i_2=3}^{i_3}\sum_{i_1=2}^{i_2}\sum_{i_0=1}^{i_1}1 = \sum_{i_3=4}^{x}\sum_{i_2=3}^{i_3}\sum_{i_1=2}^{i_2}\binom{i_1}{1}=\sum_{i_3=4}^{x}\sum_{i_2=3}^{i_3}\left[\binom{i_2+1}{2}-\binom{2}{1}\right]$$ that equals $$ \sum_{i_3=4}^{x}\left[\binom{i_3+2}{3}-\binom{4}{3}-\binom{2}{1}\binom{i_3-2}{1}\right]$$ or $$ \binom{x+3}{4}-\binom{6}{3}-\binom{4}{3}\binom{x-3}{1}-\binom{2}{1}\binom{x-1}{2}+\binom{2}{1}\binom{2}{2}.$$ The same approach works for any other value of $u$. – Jack D'Aurizio Feb 27 '17 at 17:26
  • @JackD'Aurizio Thank you for your answer. What is the hockey stick identity ? Is it possible to generalize for any $u$? – Dingo13 Feb 27 '17 at 17:59
  • It is a fundamental identity in dealing with power sums or similar sums: https://en.wikipedia.org/wiki/Hockey-stick_identity and the above argument can be easily extended for any value of $u$. – Jack D'Aurizio Feb 27 '17 at 18:03
  • @JackD'Aurizio Thank you again. Can it be simplified to a single term, like done at the provided link? – Dingo13 Feb 27 '17 at 18:15
  • It can be simplified to a polynomial with degree $u$ in the $x$ variable, of course, but I do not think it can be simplified to a single binomial coefficient in the general case, since every summation index $i_k$ starts at a different integer. – Jack D'Aurizio Feb 27 '17 at 18:22
  • @JackD'Aurizio Thank you for your answers. As regards it asymptotic equivalence, can we say this is equivalent to $\frac{x^u}{u!}$ again? – Dingo13 Feb 27 '17 at 18:31
  • That is sure, the dominant term is just the first one. – Jack D'Aurizio Feb 27 '17 at 18:32

0 Answers0