Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $c > 0$. I'm trying to show that the sequence $\displaystyle\sum\limits_{k=0}^n \left|\frac{n^k-\frac{n!}{(n-k)!}}{n^k}\right|\frac{c^k}{k!}$ converges to zero, as $n \to \infty$.

I know that the nominator is a polynomial of $n$ of degree $k-1$, while the denominator is a polynomial of degree $k$. Therefore the whole expression in the absolute value behaves like $\frac{1}{n}$ for large values of $n$, and the sequence $\sum\limits_{k=0}^n \frac{1}{n}\frac{c^k}{k!}$ obviously converges to zero (it's $\frac{1}{n}$ times the expression for exponent). Therefore my problem is showing that the expression behaves like $\frac{1}{n}$. That's mainly because the polynomial in the nominator's coefficients depend on $k$.

Anybody got an idea?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

We have $n^k-\frac{n!}{(n-k)!}=\prod_{j=1}^kn-\prod_{j=1}^k(n-j+1)$. We use the following lemma, which can be shown by induction:

If $a_k,b_k, 1\leq k\leq N$ are complex numbers of modulus $\leq R$ then $$\left|\prod_{j=1}^Na_j-\prod_{j=1}^Nb_j\right|\leq r^{N-1}\sum_{j=1}^N|a_j-b_j|.$$

We get that $$\left|n^k-\frac{n!}{(n-k)!}\right|\leq n^{k-1}\sum_{j=1}^k(j-1)=n^{k-1}\frac{k(k-1)}2$$ hence $$\sum_{k=0}^n\left|n^k-\frac{n!}{(n-k)!}\right|\frac 1{n^k}\frac{c^k}{k!}\leq \frac 1n\sum_{k=2}^n\frac{c^k}{(k-2)!}\leq \frac{c^2}ne^c.$$

share|improve this answer
    
That's brilliant. I think I can also prove the lemma. Could you maybe give me a hint as for how you came up with this great idea? –  George Jun 2 '12 at 14:22
    
Comparing the modulus of two product is used in a proof of central limit theorem. It tried to apply this idea here. Did you also post it at math.overflow ? –  Davide Giraudo Jun 2 '12 at 14:23
    
Maybe I should've taken probability first, then... :-) I didn't, but I've been working on this idea with a friend so he might have done it. –  George Jun 2 '12 at 14:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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