 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/discrete-mathematics-continuous-mathematics-and-probability/3/d/iii/solution

False. It suffices to find a subsequence along which the ratio is unbounded. Set

n = 4 m

. The last

3 m

factors of

(4 m)!

are at least

m

, while the first

m

factors have product at least one. Hence

\frac{( 4 m )!}{( 4 m ) ^{2 m}} \geq \frac{m ^{3 m}}{1 6 ^{m} m ^{2 m}} = (\frac{m}{16})^{m} ⟶ \infty.

This contradicts the eventual uniform bound required by Big O notation. The proof is an elementary factorial comparison, independent of Stirling's approximation.

 New to topics? Read the docs here!