Maths Olympiad Prep

Library / /42 of 43

Number theory Difficulty 8.3 Shortlist Find the answer

For every positive integer nn, let f(n)f(n), g(n)g(n) be the minimal positive integers such that
1+11!+12!++1n!=f(n)g(n).1+\frac{1}{1!}+\frac{1}{2!}+\dots +\frac{1}{n!}=\frac{f(n)}{g(n)}.
Determine whether there exists a positive integer nn for which g(n)>n0.999ng(n)>n^{0.999n}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given a positive integer n n , we are tasked with determining if there exists a positive integer n n for which the denominator g(n) g(n) of the rational representation of the sum

1+11!+12!++1n!=f(n)g(n) 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{n!} = \frac{f(n)}{g(n)}

satisfies g(n)>n0.999n g(n) > n^{0.999n} .

### Step-by-Step Analysis

1. Expression for the Sum:
The given series represents the partial sum of the exponential function's series expansion up to the n n -th term. The series is

Sn=1+11!+12!++1n!. S_n = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{n!}.

This sum can be written as a single fraction:

Sn=f(n)g(n) S_n = \frac{f(n)}{g(n)}

where both f(n) f(n) and g(n) g(n) are integers and gcd(f(n),g(n))=1 \gcd(f(n), g(n)) = 1 .

2. Approximation and Properties:
The series Sn S_n approaches the value of e e (Euler's number) as n n increases. This is evident because

Sn=e(1(n+1)!+1(n+2)!+). S_n = e - \left( \frac{1}{(n+1)!} + \frac{1}{(n+2)!} + \cdots \right).

While evaluating the denominator g(n) g(n) , note that each 1k! \frac{1}{k!} can be expressed with k! k! as a common denominator. Consequently,

Sn=(k=1nk!)n! S_n = \frac{\left(\prod_{k=1}^{n} k! \right)}{n!}

3. **Growth of g(n) g(n) **:
The common denominator can be computed by considering the least common multiple, which is approximately (n!)n (n!)^n particularly for large n n . Thus, g(n) g(n) can grow substantially, approximated using factorial growth:

n!2πn(ne)n. n! \approx \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n.

Hence,

(n!)n(2πn(ne)n)n. (n!)^n \approx \left(\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n\right)^n.

4. **Comparison with n0.999n n^{0.999n} **:
We consider n0.999n n^{0.999n} and g(n)(n!)n g(n) \approx (n!)^n . The factorial grows faster than the polynomial:

g(n)(n!)nn0.999n. g(n) \approx (n!)^n \gg n^{0.999n}.

5. **Existence of n n with g(n)>n0.999n g(n) > n^{0.999n} **:
As factorial growth is much more rapid than the polynomial given, there exists an n n such that

g(n)=Θ((n!)n)>n0.999n. g(n) = \Theta((n!)^n) > n^{0.999n}.

Thus, there indeed exists such an n n .

The conclusion is that there exists positive integers n n for which g(n)>n0.999n g(n) > n^{0.999n} , thus:

yes \boxed{\text{yes}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.