12
$\begingroup$

Let $X_1, X_2, \dots, X_k$ each be random digits. That is, they are independent random variables each uniformly distributed over the finite set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Let $S = X_1 + X_2 + \dots + X_k$. Given some large integer $n$, what is the probability that $S = n$?

When $n$ or $k$ is small, the exact number can be computed as

$$[z^n]\left(\frac{1-z^{10}}{1-z}\right)^k = \frac{1}{10^k} \sum_{10r+s=n} (-1)^{r+s} \binom{k}{r} \binom{-k}{s} = \frac{1}{10^k} \sum_{r} (-1)^{r} \binom{k}{r} \binom{k+n-10r-1}{n-10r}$$

(see the long list of questions below to see derivations) but what I need is an asymptotic expression useful for large $n$ and $k$, and I don't know how to either derive one from this formula, or arrive at one independently.

(For now, I'm not worrying about the complication of insisting that $X_1$ be nonzero, though feel free to consider it if it actually helps.)


What I have tried, part 1: As the $X_i$s are IID random variables (with mean $\mu = 4.5$ and variance $\sigma^2 = 8.25$), the central limit theorem applies, so we expect $\Pr(S = n)$ to be highest for $n$ around $4.5k$, and the probability distribution of $S$ to be bell-curve-shaped around that value (and most of the probability will be distributed for $n$ about $O(\sqrt{k})$ from that value).

Trying to make this more precise, the central limit theorem gives us
$$\sqrt{k}(S/k - 4.5) \xrightarrow{d} N(0,8.25) \quad \text{i.e.} \quad \lim _{k\to \infty}\Pr \left[\sqrt{k}(S_{k}/k- 4.5)\le z\right]= \Phi\left(\frac {z}{\sqrt{8.25}}\right)$$ where $\Phi(x) = \frac12 \left[1+\operatorname{erf} \left(\frac{x}{\sqrt {2}}\right)\right]$ is the CDF of the standard normal distribution $N(0,1)$ (and erf is a special function) and therefore $$\Pr(S \le x) = \Pr(S/\sqrt{k} - 4.5\sqrt{k} \le x/\sqrt{k} - 4.5\sqrt{k}) \to \Phi\left(\frac{x - 4.5k}{\sqrt{8.25k}}\right)$$ and so, applying a continuity correction, $$\begin{align}\Pr(S = n) &\approx \Pr(n - 0.5 < S \le n + 0.5) \\ &\to \Phi\left(\frac{n + 0.5 - 4.5k}{\sqrt{8.25k}}\right) - \Phi\left(\frac{n - 0.5 - 4.5k}{\sqrt{8.25k}}\right) \\ &= \frac12\operatorname{erf}\left(\frac{2n+1-9k}{\sqrt{66k}}\right) - \frac12\operatorname{erf}\left(\frac{2n-1-9k}{\sqrt{66k}}\right) \\ &\overset{?}{\approx} \frac{2}{\sqrt{\pi}}\frac{1}{\sqrt{66k}}\exp\left(-\left(\frac{2n-9k}{\sqrt{66k}}\right)^2\right) \end{align}$$ but I neither know whether this is correct and rigorous, nor what to do with this next.


What I have tried, part 2: There are many questions on this site about calculating this number exactly:

The best that can be got from reading all of them is the exact formula mentioned at the top of the question (done with generating functions or inclusion-exclusion), not an asymptotic one. In particular I'd like to be able to get something which can be summed over $k$, to answer the following question:


Question 2: Let $X_{i,j}$ each be IID random digits as before, for $i = 1, 2, \dots$ and $j = 1, 2, \dots, i$. Let $S_k = X_{k,1} + X_{k,2} + \dots + X_{k,k}$ be the sum of $k$ random digits. So we have an infinite sequence of random variables (sums) $S_1, S_2, S_3, \dots$ each obtained by adding the digits of a random number of a different length. Given an integer $n$, what is the probability that some element of this sequence is exactly equal to $n$?

In other words, for each $k$ there is a probability distribution over $n$, and we want to know the total probability that falls on a single integer $n$. (Basically for each $n$ there will be some significant probability for $k$ around $n/4.5$ and the probability will fall off significantly for $k$ further away from this.)

(Again, feel free to add or remove the condition that $X_{k,1}$ is actually distributed over the set $\{1, 2, \dots, 9\}$, i.e. is nonzero.)


What I have tried, part 3: I tried to read Distribution of the sum-of-digits function of random integers: A survey (which I found by searching for some relevant terms), and many of the papers it references. But I got pretty lost trying to figure out what is true for base-$2$ versus base-$10$, and things like that. Perhaps the answer to my question is buried somewhere in there, but I'm not sure.

$\endgroup$
  • $\begingroup$ I would give you +100 if i could for thoroughness. Great question... $\endgroup$ – Eleven-Eleven Jan 7 at 17:23
4
$\begingroup$

Here we show the main term $\frac{2}{\sqrt{\pi}}\frac{1}{\sqrt{66k}}$ in OPs asymptotic expansion is correct using the saddle-point method.

The coefficients in the expansion of the polynomials \begin{align*} \left(\frac{1-z^{10}}{1-z}\right)^{k}=\left(1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9\right)^{k}\tag{1} \end{align*} form a unimodal sequence. Taking even values $2k$ the maximum is the coefficient of the middle term \begin{align*} [z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}\qquad k\geq 0\tag{2} \end{align*}

The coefficients in (2) form a sequence starting with $(1,10,670, 55\,252,4\,816\,030,\ldots)$. These numbers are called Lucky ticket numbers and are stored in OEIS. In fact they are the even central decanomial coefficients which are the largest coefficients in the expansion of (1).

They also cite an asymptotic formula for the largest coefficient of $\left(1+z+\cdots+z^q\right)^k$ which gives in the case (2) \begin{align*} \color{blue}{[z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}\sim 10^{2k}\frac{1}{\sqrt{33\pi k}}}\tag{3} \end{align*} corresponding to OPs main term in his expansion ($k$ even).

We can prove the asymptotic expansion (3) using the saddle-point method. In order to do so we closely follow section VIII.8 Large Powers in Analytic Combinatorics by P. Flajolet and R. Sedgewick. We also give a little bit of surrounding information to ease readability.

VIII.8 Large powers:

  • (p. 585): The extraction of coefficients in powers of a fixed function and more generally in functions of the form $A(z)B(z)^k$ constitutes a prototypical and easy application of the saddle-point method. We will accordingly be concerned here with the problem of estimating \begin{align*} [z^K]A(z)\cdot B(z)^k=\frac{1}{2\pi i}\oint A(z)B(z)^k\frac{dz}{z^{K+1}} \end{align*} as both $k$ and $K$ get large.

In our situation (3) we have $A(z)=1$ and $B(z)=\left(1+z+z^2+\cdots+z^9\right)^2$ with $K=9k$. What follows are conditions which need to be fulfilled by $A(z)$ and $B(z)$ in order to apply the saddle-point method.

VIII. 8.1. Large powers: saddle-point bounds: We consider throughout this section two fixed functions, $A(z)$ and $B(z)$ satisfying the following conditions.

  • L1: The functions $A(z)=\sum_{j\geq 0}a_jz^j$ and $B(z)=\sum_{j\geq 0}a_jz^j$ are analytic at $0$ and have non-negative coefficients; furthermore it is assumed (without loss of generality) that $B(0) \ne 0$.

  • L2: The function $B(z)$ is aperiodic in the sense that $\gcd\{j|b_j>0\}=1$. (Thus $B(z)$ is not a function of the form $\beta(z^p)$ for some integer $p\geq 2$ and some $\beta$ analytic at $0$.)

  • L3: Let $R\leq \infty$ be the radius of convergence of $B(z)$; the radius of convergence of $A(z)$ is at least as large as $R$.

We observe conditions L1 to L3 are fulfilled for $A(z)=1$ and $B(z)=\left(1+z+z^2+\cdots+z^9\right)^2$ with radius of convergence $R=\infty$. In the following we need the quantity $T$ called spread which is defined as

\begin{align*} \color{blue}{T}&:=\lim_{z\to R^{-}}\frac{zB^{\prime}(z)}{B(z)}\\ &=\lim_{z\to \infty}\frac{2z\left(1+z+\cdots+z^9\right)\left(1+2z+\cdots+9z^8\right)}{\left(1+z+\cdots+z^9\right)^2}\\ &=\lim_{z\to\infty}\frac{2z\left(1+2z+\cdots+9z^8\right)}{1+z+\cdots+z^9}\\ &\,\,\color{blue}{=18} \end{align*}

The purpose is to analyse the coefficients \begin{align*} [z^K]A(z)\cdot B(z)^k \end{align*} when $K$ and $k$ are linearly related. In order to do so the condition $K<Tk$ will be imposed which is inherent in the nature of the problem. Note that in our case we have $K=9k$ and with $T=18$ the condition $K<Tk$ evaluates to $9k<18k$ which is valid.

We also need a quantity $\zeta$ which is introduced in Proposition VIII.7 and since this is a useful and easily derived upper bound for the coefficients we note

Proposition VIII.7 (Saddle-point bounds for large powers):

  • Consider functions $A(z)$ and $B(z)$ satisfying the conditions L1,L2,L3 above. Let $\lambda$ be a positive number with $0<\lambda <T$ and let $\zeta$ be the unique positive root of the equation

\begin{align*} \zeta\frac{B^{\prime}{(\zeta)}}{B(\zeta)}=\lambda \tag{4} \end{align*}

Then, for $K=\lambda k$ an integer; one has \begin{align*} [z^K]A(z)\cdot B(z)^k\leq A(\zeta)B(\zeta)^k\zeta^{-K}\tag{5} \end{align*}

We start with calculating the roots of (4). We set $\lambda =9$ and obtain according to (4) \begin{align*} z\frac{B^{\prime}(z)}{B(z)}&=9\\ \end{align*} which gives with $B(z)=\left(1+z+\cdots+z^9\right)^2$: \begin{align*} \color{blue}{9z^9+7z^8+5z^7+3z^6+z^5-z^4-3z^3-5z^2-7z-9=0} \end{align*} from which we easily derive the positive root $\color{blue}{\zeta =1}$.

We find as upper bound according to (5) \begin{align*} [z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}\leq \left(\sum_{k=0}^91\right)^{2k}\cdot 1^{-9k}=10^{2k} \end{align*} This upper bound isn't really sharp but it may be useful whenever only rough order of magnitude estimates are sought.

Now we are well prepared for the main theorem.

Theorem VIII.8 (Saddle-point estimates of large powers).

  • Under the conditions of Proposition VIII.7, with $\lambda = K/k$, one has \begin{align*} \color{blue}{[z^K]A(z)\cdot B(z)^k=A(\zeta)\frac{B(\zeta)^k}{\zeta^{K+1}\sqrt{2\pi n \xi}}\left(1+o(1)\right)}\tag{6} \end{align*}

    where $\zeta$ is the unique root of $\zeta B^{\prime}(\zeta)B(\zeta)=\lambda$ and

\begin{align*} \xi=\frac{d^2}{d\zeta^2}\left(\log B(\zeta)-\lambda\log \zeta\right).\tag{7} \end{align*}

  • In addition, a full expansion in descending powers of $k$ exists.

These estimates hold uniformly for $\lambda$ in any compact interval of $(0,T)$, i.e., any interval $[\lambda^{\prime},\lambda^{\prime\prime}]$ with $0<\lambda^{\prime}<\lambda^{\prime\prime}<T$, where $T$ is the spread.

Now it's time to harvest. At first we calculate $\xi$ according to (7). We obtain with $B(z)=\left(1+z+\cdots+z^9\right)^{2}$ and $\lambda=9$: \begin{align*} \color{blue}{\xi}&=\left.\left(\frac{d^2}{dz^2}\left(\log (B(z)-9\log z\right)\right)\right|_{z=1}\\ &=\left.\left(\frac{d}{dz}\left(\frac{B^{\prime}(z)}{B(z)}-\frac{9}{z}\right)\right)\right|_{z=1}\\ &=\frac{B^{\prime\prime}(1)}{B(1)}-\left(\frac{B^{\prime}(1)}{B(1)}\right)^2+9\\ &=\frac{177}{2}-81+9\\ &\,\,\color{blue}{=\frac{33}{2}}\tag{8} \end{align*}

Putting all together into (6) we finally obtain with $B(\zeta)=B(1)=\left.\left(1+z+\cdots+z^9\right)^{2k}\right|_{z=1}=10^{2k}$: \begin{align*} \color{blue}{[z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}} &=\frac{10^{2k}}{1^{9k+1}\sqrt{2\pi k \frac{33}{2}}}(1+o(1))\\ &\,\,\color{blue}{=10^{2k}\frac{1}{\sqrt{33\pi k}}(1+o(1))} \end{align*}

in accordance with the claim (3).

Note: We have according to theorem VIII.8 the possibility to calculate a full expansion in descending powers of $k$. We can also study asymptotic expansions of $[z^K]B(z)^{k}$ for other quantities of $K$ as long as we fulfill the spread condition $K<Tk$.

$\endgroup$
  • $\begingroup$ Thank you, those are useful references! $\endgroup$ – ShreevatsaR Jan 12 at 16:56
  • $\begingroup$ @ShreevatsaR: You're welcome. $\endgroup$ – Markus Scheuer Jan 12 at 16:58
  • $\begingroup$ Thanks very much for a very clear and informative answer. I've often heard of the saddle-point method but never got around to learning it (e.g. didn't get that far in the Analytic Combinatorics book); now I have some idea. So if I understand this answer correctly, this gives the asymptotics of the largest coefficient... and we need to appeal to probability arguments etc to show that for the other coefficients, the probability drops off exponentially from this main (largest) term. $\endgroup$ – ShreevatsaR Jan 15 at 19:25
  • $\begingroup$ @ShreevatsaR: You're welcome and I agree with your considerations. I'd like to point to the introductory paragraph (the first one) in section VIII.9: Saddle-points and probability distributions. This section might go in the directions you are interested in. $\endgroup$ – Markus Scheuer Jan 15 at 19:36
3
$\begingroup$

You can prove that your asymptotic expression is correct using the Edgeworth series.

Let $F_k$ be the cdf for $\sqrt{\frac{k}{8.25}}(S_k/k-4.5)$. By the Central Limit theorem, $F_k(x)$ is approximately equal to $\Phi(x)$. Specifically, the Edgeworth series shows that $$ F_k(x)=\Phi(x) -\frac{\lambda_3}{6\sqrt k}\Phi'''(x)+O(k^{-1}) $$ Here, $\lambda_3$ is the skewness of a single random digit. Since this skewness is zero, as the distribution is symmetric about $[0,9]$, we get $$ F_k(x)=\Phi(x)+O(k^{-1}). $$ This shows the error in the central limit approximation is linear in $k$. Therefore, \begin{align} P(S_k=n) &=P(n-\tfrac12<S_k\le n+\tfrac12) \\&=F_k\left(\frac{n+\frac12-4.5k}{\sqrt{8.25 k}}\right)-F_k\left(\frac{n-\frac12-4.5k}{\sqrt{8.25 k}}\right) \\&=\Phi\left(\frac{n+\frac12-4.5k}{\sqrt{8.25 k}}\right)-\Phi\left(\frac{n-\frac12-4.5k}{\sqrt{8.25 k}}\right)+O(k^{-1}) \\&\stackrel1= \Phi'(\xi)\cdot\frac1{\sqrt{8.25k}}+O(k^{-1}) \\&= \frac1{\sqrt{8.25k}}\left(\Phi'(\xi)-\Phi'\left(\frac{n-4.5k}{\sqrt{8.25k}}\right)+\Phi'\left(\frac{n-4.5k}{\sqrt{8.25k}}\right)\right)+O(k^{-1}) \\&\stackrel2= \frac1{\sqrt{8.25k}}\Phi'\left(\frac{n-4.5k}{\sqrt{8.25k}}\right)+\frac1{8.25k}\Phi''(\eta)+O(k^{-1}) \\&\stackrel3= \frac1{\sqrt{8.25k}}\Phi'\left(\frac{n-4.5k}{\sqrt{8.25k}}\right)+O(k^{-1}) \end{align}

Explanations:

  1. Here, we are applying the mean value theorem. $\xi$ is a number between $\frac{n\pm\frac12-4.5k}{\sqrt{8.25 k}}$.

  2. Now we apply the mean value theorem to $\Phi'$. Here, $\eta$ is a number between $\xi$ and $\frac{n-4.5k}{\sqrt{8.25 k}}$

  3. We can absorb the $\frac1{8.25k}\Phi''(\eta)$ into the $O(k^{-1})$ because $\Phi''$ is bounded.

This is exactly the asymptotic expansion you guessed; however, the above rigorously shows that your answer is correct, with the error decreasing linearly as $k\to\infty$.

$\endgroup$
  • $\begingroup$ Actually, this is omitting some details; in order for the Edgeworth series to work when the variables are integer valued, you need to add in a correction term which is periodic, as described in jstor.org/stable/2242145?seq=1#metadata_info_tab_contents. This term ends up canceling out; I will add in more details later. $\endgroup$ – Mike Earnest Jan 12 at 20:03
  • $\begingroup$ Wow these look like powerful techniques; thanks for sharing. $\endgroup$ – ShreevatsaR Jan 12 at 20:16
  • $\begingroup$ @ShreevatsaR I said I would post more info, but I have tried and been unable to figure out the correct result. I would suggest you try to look into the Edgeworth series, and specifically the series for lattice variables, and see if you can figure it out. $\endgroup$ – Mike Earnest Jan 14 at 23:40
  • $\begingroup$ Sure, thanks for your effort and for a very useful lead, and what matters is that I learned something new and useful... yes I'll try to look into this further too. $\endgroup$ – ShreevatsaR Jan 15 at 18:45
2
+200
$\begingroup$

Each digit in a $(r+1)$-ary base is a discrete uniform random variable, with support $[0,r]$.
The relevant mean and variance are $$ \mu = {r \over 2}\quad \sigma ^{\,2} = {{\left( {r + 1} \right)^{\,2} - 1} \over {12}} $$

By the Central Limit Theorem the sum$n$ of $k$ of them will tend to be Normally distributed with mean $k \mu$ and variance $k \sigma ^2$.
That is the expression that you give will tend (very quickly) to $$ {1 \over {\sqrt {2\pi k\sigma ^{\,2} } }}e^{\, - \,{{\left( {n - k\mu } \right)^{\,2} } \over {2k\sigma ^{\,2} }}} = {{\sqrt {6/\pi } } \over {\sqrt {k\,r\left( {r + 2} \right)} }}e^{\, - \,6{{\left( {n - kr/2} \right)^{\,2} } \over {k\,r\left( {r + 2} \right)}}} $$

Then just replace $r=9$.

That for what concerns the asymptotic distribution.

Concerning your other questions, I did not understood properly what you want to compute.

------ Addendum in reply to your comment ------

1) A discrete uniform variable $0 \le n \le r$ is approximable to a continuous uniform variable $-1/2 \le \nu \le r+1/2$, with $p(n) \approx p(n-1/2 \le \nu \le n+1/2)$.

2) If $p(n\;;\,r,\,k)$ denotes the probability above (either "exact" or "approximated") to get $n$ as the sum of $k$ $(r+1)$-ary digits (i.i.d.), then its complement is $$ q(n\;;\,r,\,k) = 1 - p(n\;;\,r,\,k) $$ So, the probability that $n$ is not attained as the sum of either $1$, or $2$, .., or $m$ digits will be $$ Q(n\;;\,r,\,m) = \prod\limits_{1\, \le \,k\, \le \,m} {q(n\;;\,r,\,k)} = \prod\limits_{1\, \le \,k\, \le \,m} {\left( {1 - p(n\;;\,r,\,k)} \right)} $$ For small $p(n\;;\,r,\,k)$ (i.e. high $r,k$) we can approximate the above as $$ \eqalign{ & \ln Q(n\;;\,r,\,m) = \sum\limits_{1\, \le \,k\, \le \,m} {\ln \left( {1 - p(n\;;\,r,\,k)} \right)} \approx \cr & \approx - \sum\limits_{1\, \le \,k\, \le \,m} {p(n\;;\,r,\,k) + O\left( {p(n\;;\,r,\,k)^{\,2} } \right)} \cr} $$

3) Finally note that the exact $p(n\;;\,r,\,k)$ can be better written as $$ \eqalign{ & p(n\;;\,r,\,k) = {{N_{\,b} (n,r,k)} \over {\left( {r + 1} \right)^{\,m} }} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( { \le \,{n \over {r + 1}}\, \le \,k} \right)} {\left( { - 1} \right)^j \binom{k}{j} \binom{n + k - 1 - j\left( {r + 1} \right)}{ n - j\left( {r + 1} \right)} } \cr} $$

which, as thoroughly explained in this related post, gives the advantage that the sum limits are implicit in the binomial coefficient, thereby simplifying its algebraic manipulation.

$\endgroup$
  • $\begingroup$ Thanks… (1) can you explain how you deal with the fact that the normal distribution is a continuous one and we're asking about the sum being exactly one $n$ (a point)? (2) My second question was about summing the above over all integers $k$. In other words, first we take the sum $S_1$ of one random digit, then the sum $S_2$ of two random digits, then the sum $S_3$ of three random digits and so on, and ask what is the probability that $n$ is a member of this sequence. We have one normal distribution for each $k$, and we want the total probability distribution that falls on $n$. $\endgroup$ – ShreevatsaR Jan 7 at 3:57
  • $\begingroup$ @ShreevatsaR: I expanded my answer in reply to your comment: does it meet your requirements ? $\endgroup$ – G Cab Jan 7 at 17:21
  • $\begingroup$ Thank you very much (+1). I'll think about this a bit more but I think the initial part matches. BTW for the second part, I was interested in the case where (in your notation) $m \to \infty$ -- note that as $k$ becomes larger than than some threshold, again the probability of hitting $n$ starts falling off exponentially, so it should be possible to sum over all $k$ and get an expression $Q(n; r)$ (in your notation) that depends only on $n$ (and $r$). Maybe not even $n$... $\endgroup$ – ShreevatsaR Jan 7 at 18:36
  • $\begingroup$ increasing $k$ increases the mean of the gaussian $p(n,r,k)$, while the std dev. increases with $\sqrt{k}$. So, keeping $n$ fixed, the gaussian will move towards and then beyond it, with an $O(exp(-k)/ \sqrt{k})$ which is certainly summable. $\endgroup$ – G Cab Jan 7 at 19:22
  • $\begingroup$ Yes exactly; that's what I expect and that's why I'd like to know asymptotically what the sum is equal to. Maybe I'll post a separate question about how to sum it over all $k$. :-) (and accept this one after a while). $\endgroup$ – ShreevatsaR Jan 7 at 20:25
1
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

  • Let $X_{1},\ldots,X_{k}$ each be random digits. That is, they are independent random variables each uniformly distributed over the finite set $\braces{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$.
  • Let $S \equiv X_{1} + \cdots + X_{k}$.
  • Given some integer $n$, what is the probability that $S = n$ ?.

\begin{align} &\mathbb{P}\bracks{X_{1} + \cdots + X_{k} = n} \equiv \bbox[10px,#ffd]{\sum_{x_{1} = 0}^{9}{1 \over 10}\cdots \sum_{x_{k} = 0}^{9}{1 \over 10} \bracks{z^{n}}z^{x_{1}\ +\ \cdots\ +\ x_{k}}} \\[5mm] = &\ {1 \over 10^{k}}\bracks{z^{n}}\pars{\sum_{x = 0}^{9}z^{x}}^{k} = {1 \over 10^{k}}\bracks{z^{n}}\pars{z^{10} - 1 \over z - 1}^{k} \\[5mm] = &\ {1 \over 10^{k}}\bracks{z^{n}} \pars{1 - z^{10}}^{k}\pars{1 - z}^{-k} \\[5mm] = &\ {1 \over 10^{k}}\bracks{z^{n}} \bracks{\sum_{\ell = 0}^{k}{k \choose \ell}\pars{-z^{10}}^{\ell}} \bracks{\sum_{m = 0}^{\infty}{-k \choose m}\pars{-z}^{m}} \\[5mm] = &\ {1 \over 10^{k}} \sum_{\ell = 0}^{k}{k \choose \ell}\sum_{m = 0}^{\infty} \bracks{{k + m - 1 \choose m}\pars{-1}^{m}}\pars{-1}^{\ell + m} \bracks{10\ell + m = n} \\[5mm] = &\ {1 \over 10^{k}} \sum_{\ell = 0}^{k}{k \choose \ell}\pars{-1}^{\ell} \sum_{m = 0}^{\infty}{k + m - 1 \choose k - 1} \bracks{m = n - 10\ell} \\[5mm] = &\ {1 \over 10^{k}} \sum_{\ell = 0}^{k}{k \choose \ell}\pars{-1}^{\ell} {k + n - 10\ell - 1 \choose k - 1}\bracks{n - 10\ell \geq 0} \\[5mm] = &\ \bbx{{1 \over 10^{k}} \sum_{\ell = 0}^{\color{red}{M}}{k \choose \ell} {k + n - 1 - 10\ell \choose k - 1}\pars{-1}^{\ell}\,,\quad \color{red}{M} \equiv \min\braces{k,\left\lfloor{n \over 10}\right\rfloor}} \end{align}

$\endgroup$
  • 1
    $\begingroup$ This is already mentioned in the question (after the list of 19 other questions on this site). It's not useful because I want an asymptotic expression for large $n$ and $k$. $\endgroup$ – ShreevatsaR Jan 6 at 21:21
  • $\begingroup$ But thanks for taking the effort of typing this up, and please let me know how I could have written the question more clearly to avoid this — maybe assume that not everyone will read the whole question, and move this part to the top? $\endgroup$ – ShreevatsaR Jan 6 at 21:25
  • $\begingroup$ I've moved the formula from the middle to the top of the question — sorry for wasting your time; it didn't occur to me that someone might not read the whole question and end up writing something that's already mentioned in the question and in the answers to several other questions. Hope it's better now. $\endgroup$ – ShreevatsaR Jan 6 at 22:05
  • $\begingroup$ @ShreevatsaR Don't worry about it. It's fine you recognize my answer as useful one. Thanks. $\endgroup$ – Felix Marin Jan 7 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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