4
$\begingroup$

Do you think the following limits are correct?

$\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\varphi(N) \choose k} {d-1 \choose k-1}}{\varphi(N)^d}=0$

$\displaystyle\lim_{N\to\infty}\frac{\sum\limits_{k=1}^{d} {\varphi(N) \choose k} {d-1 \choose k-1}}{\varphi(N)^d}=c$

I plotted the equations and guessed the results according to the graphs but I could not prove them mathematically by myself. Any hints would be appreciated. Graphs are as follows:

http://deniz.cs.utsa.edu/plots/

Thanks,

  • 0
    What is $N$ in the first one? What is $d$ in the second one?2010-10-14
  • 0
    I changed \phi to \varphi, if you don't like it you can hit revert but I think that is an improvement.2010-10-14
  • 0
    $N$ in the first one and $d$ in the second one are positive integers.2010-10-14
  • 4
    Posted also in http://mathoverflow.net/questions/42181/limit-involving-the-totient-function-and-combination2010-10-14

1 Answers 1

1

From MathOverflow user JBL:

We have the Vandermonde identity:

$$ \sum_{k=1}^d {\varphi(N) \choose k} {d-1 \choose k-1} = {d + \varphi(N) - 1 \choose d}. $$

Thus with $N$ fixed, the numerator of your fraction is polynomial in $d$ and the result follows (with the exception of the values $N = 1, 2$).

The second result follows by the same analysis, since $\varphi(N) \to \infty$ as $N \to \infty$. In particular, the resulting constant is $\frac{1}{d!}$.