1

after developing a formula, I came up against this :

$$f_0(n)=2n−1,\\ f_{k+1}(n)=\sum_{i=1}^nf_k(i)$$

So, for example :$$f_1(n)= n^2\\ f_2(n) = \frac{n(n+1)(2n+1)}{6}$$ Can we find $f_n(n)$ ?

Thanks to Jens Renders for his advice of rewriting it in a more logical way

Theman Op
  • 23
  • Just a notation advice: you are using $n$ as a variable, as the index of summation and as the last term of the sum at the same time. This is confusing, not to mention it does not make much sense. – IamWill May 19 '20 at 19:44
  • $n$ can't be both a dumb variable in $\sum$ and the upper bound for this same variable. – Bernard May 19 '20 at 19:45
  • I know, but I cannot see how I could chose a different index name. If I had chosen i for the index name, the second example wouldn't make any sence either – Theman Op May 19 '20 at 19:53
  • 1
    I do understand the question, and I understand why it is difficult to write down. I would write it like this: $f_0(n) = 2n-1$, $f_{k+1}(n) = \sum_{i=1}^n f_k(i)$. You want to know what is $f_n(n)$ or maybe more generally $f_k(n)$ in closed form. If you agree, could you edit that in your question? – Jens Renders May 19 '20 at 19:58
  • 1
    Maybe you can use this https://math.stackexchange.com/a/2266856/399263, but you have to clarify your indexes, it is still vague what you want to sum. It looks like the question I linked, but this is just one interpretation. – zwim May 19 '20 at 20:01
  • 1
    If you mean what I wrote in my previous comment, you can check out the pattern here – Jens Renders May 19 '20 at 20:19

1 Answers1

2

Applying the Hockey-Stick Identity repeatedly gives $$ f_1(n)=\sum_{k=1}^nf_0(k)=\binom{n}{2}+\binom{n+1}{2} $$ $$ f_2(n)=\sum_{k=1}^nf_1(k)=\binom{n+1}{3}+\binom{n+2}{3} $$ $$ f_3(n)=\sum_{k=1}^nf_2(k)=\binom{n+2}{4}+\binom{n+3}{4} $$ Following this pattern, we get $$ f_k(n)=\binom{n+k-1}{k+1}+\binom{n+k}{k+1} $$ Thus, setting $k=n$, we get $$ f_n(n)=\binom{2n-1}{n+1}+\binom{2n}{n+1} $$

robjohn
  • 345,667