0

I am trying to understand how an equation from a research paper is derived. Suppose that $q$ is a prime power, and for functions $f$ and $g$ of $q$, we write $f = o(g)$ when $\lim_{q \to \infty} f/g = 0$. Further, suppose that $t$ and $k$ are positive integers with $t \leq k$. Additionally, $z$ is an integer satisfying $k \leq z \leq q$, $1 = o(z)$, and $z = o(q^{k-t/k})$. The equation of interest is

${q-k \choose z-k} = {q \choose z}\frac{z^k}{q^k}(1 + o(1))$.

This equation is true provided that $\lim_{q \to \infty} \frac{{q-k \choose z-k}}{{q \choose z} z^k/q^k} = 1$. However, I'm not sure how to prove that this is true.

David Smith
  • 530
  • 1
  • 4
  • 10

1 Answers1

2

Basically the idea is that if $0 \leq k \ll n$ then $\frac{n!}{(n-k)!}$ is "expected to be" approximately $n^k$, since there are $k$ factors each of which is approximately $n$. So in this context, $\frac{q!}{(q-z)!}$ is approximately $q^z$ and $\frac{(q-k)!}{(q-z)!}$ is approximately $q^{z-k}$. Thus ${q \choose z}$ is approximately $\frac{q^z}{z!}$, and ${q-k \choose z-k}$ is approximately $\frac{q^{z-k}}{(z-k)!}$. Taking the ratio of the approximations gives $\frac{q^k (z-k)!}{z!}$ which is approximately $\frac{q^k}{z^k}$ by the same line of reasoning.

To prove this approximation and make the error more precise, you have to clean up the precise hypotheses (for example, is $k$ fixed or can it grow with $n$ at some slower rate?). One way is to use the simple estimate $n^k(1-k/n)^k \leq \frac{n!}{(n-k)!} \leq n^k$ from which it follows that $n^k(1-k^2/n) \leq \frac{n!}{(n-k)!} \leq n^k$. This line of approach suggests a hypothesis of $\lim_{n \to \infty} \frac{k(n)^2}{n} = 0$.

Ian
  • 101,645
  • Thanks for your response. Let's assume that $k$ is fixed. In that case, the analysis you've provided in your first paragraph will suffice, correct? – David Smith Aug 28 '18 at 05:06
  • @DavidSmith Careful...in your problem both $k$ and $z$ "take on the role" of $k$ in my second paragraph. So you will need to be a little bit more careful when arguing that ${q \choose z} \approx \frac{q^z}{z!}$, even if you assume $k$ is fxed. – Ian Aug 28 '18 at 13:21