# Limit involving the totient function and combination

Hi,

Do you think the following limits are correct?

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

$\displaystyle\lim_{N\to\infty}\frac{\sum\limits_{k=1}^{d} {\phi(N) \choose k} {d-1 \choose k-1}}{\phi(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/d_vs_Eq.jpeg

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

Thanks,

-
I don't understand your first graph at all. For fixed $N$ and $d$, the resulting expression is a rational number with denominator $\phi(N)$. So, for example, when $N = 7$ it's a rational number with denominator 6. Where are you getting values like $10^{-10}$ from? – JBL Oct 14 '10 at 18:07
I am sorry but there was a typo, i edited now, the denominator should be $\phi(N)^d$. Sorry again! – Nick Oct 14 '10 at 18:10
Also posted in math.stackexchange.com/questions/6803/… – Arturo Magidin Oct 14 '10 at 19:22

We have $$\sum_{k = 1}^d \binom{\phi(N)}{k} \binom{d - 1}{k - 1} = \binom{d + \phi(N) - 1}{d}$$ (this is the Vandermonde identity). Thus, with $N$ fixed the numerator of your fraction is polynomial in $d$ and so the first result follows (except for $N = 1, 2$).
Edited to add: Okay, and the second result follows by the same analysis, since $\phi(N) \to \infty$ as $N \to \infty$. In particular, the resulting constant is $\frac{1}{d!}$.