3
$\begingroup$

I am looking for closed forms, or at least a good approximation for

$$f(n) = \sum_{k=1}^{k=n} \genfrac\{\}{0pt}{}{n}{k}(n)_kk$$

I know that

$$\sum_{k=1}^{k=n} \genfrac\{\}{0pt}{}{n}{k}(n)_k = n^n$$

I have the intuition that $f(n)$ is bounded above by $n^{n+1}$ and approaches $n^{n+1}$ for large $n$ but I am not entirely sure and don't know how to form a proof (or anti-proof).

Sorry if this question is too basic for math overflow, I wasn't sure if it belonged here or elsewhere.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Calculate the first few terms and then look it up in the Online Encyclopedia of Integer Sequences. $\endgroup$
    – Gerry Myerson
    Commented Jan 7, 2022 at 22:18
  • $\begingroup$ @MichaelHardy, I believe that the consensus is generally to avoid edits that solely introduce LaTeX in titles. $\endgroup$
    – LSpice
    Commented Jan 8, 2022 at 17:37

1 Answer 1

Reset to default
7
$\begingroup$

We have that $(x)_k - (x-1)_k = k (x-1)_{k-1}$. So applying the linear operator $f \mapsto xf(x) - xf(x-1)$, to the identity $$ \sum_{k=1}^{n} \genfrac\{\}{0pt}{}{n}{k}(x)_k = x^n $$ we get that $$\sum_{k = 1}^n \genfrac\{\}{0pt}{}{n}{k} k (x)_k = x^{n+1} - x(x-1)^n.$$

Edit: In retrospect, there is also a enumerative proof. The left hand side counts the set of functions from $[n] \to [x]$ together with a choice of point in the image. The right hand counts the set offunctions from $[n] \sqcup * \to [x]$ minus the set of functions such that the image of $*$ and $[n]$ are disjoint.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .