The task is to find the sum of all numbers (positive integers) that consist of at most $n$ digits, which sum up to $k$ (where $1 \leq k \leq 9$). For instance, if $n=2, k=3$, the desired sum equals $3 + 12 + 21 + 30 = 66$.

What I've come up with is the following, rather nasty recurrence ($a\_{k, n}$ denotes the sum we are to find):

\[ \begin{split} & a\_{k, 1} = k \\ &a\_{k, n} = \sum\_{i=0}^{k}i \cdot 10^{n-1} \cdot{n - 2 + k - i \choose n-2} + a\_{k-i, n-1}. \end{split}\]

I obtained the latter formula by the following observation: the most significant digit in an $n$-digit number can be anything from $1$ to $k$. Each choice of such a digit $i$ contributes $i \cdot 10^{n-1}$, times the number of possible arrangements of digits at the less significant places, to the overall sum. There's ${(n-1) + (k-i) - 1 \choose k-i} = {n - 2 + k - i \choose n-2}$ such arrangements. Then (again, for each $i$), we must recursively include the contribution of "shorter" numbers ($n-1$), which meet our criterion $(k-i)$, to the sum. Finally, we count in the numbers whose length doesn't exceed $n-1$ (that's why the summation begins with $i = 0$).

This formula seems to work (I checked it for some small $n, k$). However, I've been aiming for a better solution - using such a recurrence for higher $n,k$ means an awful lot of computation. Is there a way to obtain a closed-form expression - by either simplifying my result or applying a completely different approach?