4

Does the expression $$\phi(n,k)=\frac{k(k+1)\cdots(k+n-1) - k^n}{n!k^n}$$ uniformly converge to zero as $k\to \infty$? more precisely,

given $\varepsilon>0$ can we find $N$ such that for all $k\geq N$ and all $n$ it holds that $\phi(n,k)< \varepsilon$?

I'm working on an exercise and if this were true then I'd be done, however, I cannot find a way to prove it. What's your intuition about it? is it true, and if so, how could I prove it?

Daniel
  • 6,999
  • 1
    I encountered a similar problem. I think that you can separate the problem into two cases: (1) $1\leq n < k$;(2) $n\geq k$. – mike Oct 16 '16 at 14:19
  • Am I missing something, or is it enough to just drop the $n!$ in the denominator (giving an upper bound) and show that that expression goes to 0? Should be pretty straightforward with Stirling. – Vik78 Oct 16 '16 at 14:23
  • @mike I think that won't work since you this is supposed to work for all $n$, and this bound should be independent on whether $1\leq n <k$ or $n\ge k$. – Daniel Oct 16 '16 at 14:26
  • @Vik78 Didn't think in using Stirling... however, is the expression without $n!$ convergent to zero? I'm not sure of that... – Daniel Oct 16 '16 at 14:27
  • Yeah, now that I'm seeing it I'm not sure that it does. Think I misread the expression initially. Anyway, using Stirling should help. – Vik78 Oct 16 '16 at 14:28
  • Actually wait, removing the $n!$ should not affect convergence to zero as $k \to \infty$ since $n$ is fixed. – Vik78 Oct 16 '16 at 14:42
  • @Vik78 Indeed, but it may affect the uniform convergence to zero – Daniel Oct 16 '16 at 14:44

1 Answers1

2

We may write $\phi(n,k) \le \frac{(n+k)^n - k^n}{n!k^n}$. You may expand the binomial in this expression and upper bound it further by $\frac{n {n \choose {n/2}}}{k n!}$, taking the ceiling of $n/2$ if $n$ is odd. This upper bound is justified by the fact that the middle binomial coefficient is largest and $n/k > (n/k)^m$ for $m > 1$. To make this less than $\epsilon$, choose $k$ greater than $\frac{n {n \choose {n/2}}}{n! \epsilon}$. We know that $\frac{n {n \choose {n/2}}}{n!}$ is bounded above by a constant, since as $n \to \infty$ it converges to zero and a convergent sequence is bounded, so convergence is uniform.

Vik78
  • 3,877
  • Strange to say that we should pick $k$ greater than an expression that depends on $n$ when it's supposed to be a bound independent of $n$. However since $\frac{n^2+n^3}{kn!}$ is smallest when $n=3$ this should show that $\phi(n,k) < \frac{C}{k}$ where $C$ is independent of $n$ which is what you want. – Kibble Oct 16 '16 at 15:17
  • @Kibble you mean the largest? – mike Oct 16 '16 at 16:01
  • Thanks for your answer! I'm sorry for not replying yesterday, I didn't have the time to write down this. Ok, I must confess I don't know how did you get the bound $\frac{n^2 + n^3}{kn!}$ from $\frac{(n+k)^n-k^n}{n!k^n}$, any hint? – Daniel Oct 17 '16 at 14:57
  • Sorry, I made a slight mistake there. Expand the binomial and cancel the $k^n$. You are left with $n$ terms in the numerator, which are bounded above by the product of the middle binomial coefficient ${{n} \choose {n/2}}$ and $n/k$ (since $k > n$ and the middle binomial coefficient is largest). You then get an upper bound of $\frac{n {{n} \choose {n/2}}}{k n!}$. Since this expression multiplied by $k$ converges to 0 you can argue similarly to show convergence is uniform. – Vik78 Oct 17 '16 at 16:26
  • @Vik78 Ok! that makes sense, thanks a lot for your support! – Daniel Oct 21 '16 at 11:17