Problem 15 - A Computational Introduction to Number Theory and Algebra

Question

Use Euler's summation formula (previous exercise) to show that $$\log (n !)=n \log n-n+\frac{1}{2} \log n+O(1)$$ and from this, conclude that \(n !=\Theta\left((n / e)^{n} \sqrt{n}\right) .\) This is a weak form of Stirling's approximation; a sharper form states that \(n ! \sim(n / e)^{n} \sqrt{2 \pi n}\).

Step-by-Step Solution

Answer

#Answer# Based on the provided step by step solution, the logarithmic approximation of \(n!\) is: $$\log(n!) = n\log{n} - n + \frac{1}{2}\log{n} + O(1)$$ And by raising both sides to the power of \(e\), we can conclude that: $$n! = \Theta((n/e)^n \sqrt{n})$$

Step 1: Applying Euler's Summation Formula

We will apply Euler's summation formula to the function \(f(x)=\log x\). Let's first find the required elements in the formula: - \(f(1) = \log{1} = 0\) - \(f(n) = \log{n}\) - \(\int_{1}^{n} f(x) \,dx = \int_{1}^{n} \log{x} \,dx\) - \(\int_{1}^{n} \lbrace f(x)-\lfloor f(x) \rfloor \rbrace \,dx = \int_{1}^{n} \lbrace\log x - \lfloor \log x \rfloor \rbrace \,dx\) Now, we can apply Euler's summation formula: $$\sum_{k=1}^{n} \log k = \int_{1}^{n} \log{x} \,dx + \frac{\log n}{2} + \int_{1}^{n} \lbrace \log x - \lfloor \log x \rfloor \rbrace \,dx$$

Step 2: Evaluate the integrals

Now, we need to evaluate the remaining integrals: 1. For the first integral: $$\int_{1}^{n} \log{x} \,dx = \left[x\log{x} - x\right]_{1}^{n} = n\log{n}-n+1$$ 2. For the second integral, since the term \(\lbrace\log x - \lfloor \log x \rfloor \rbrace\) is continuous and bounded, we can use Integrating the sum term by term and applying Riemann's conditions: $$\int_{1}^{n} \lbrace \log x - \lfloor \log x \rfloor \rbrace \,dx = O(1)$$ Here, \(O(1)\) denotes a function that has a bounded value as \(n \to \infty\). Now, substitute the integral results back into Euler's summation formula equation: $$\sum_{k=1}^{n} \log k = n\log{n}-n+1+\frac{\log n}{2}+O(1)$$

Step 3: Simplify and find the logarithmic approximation

Since we now have the sum of the logarithmic terms, which is equal to \(\log(n!)\), we can write the resulting expression: $$\log (n!) = n\log{n} - n + \frac{1}{2}\log{n} + 1 + O(1)$$ Group the constant terms together: $$\log (n!) = n\log{n} - n + \frac{1}{2}\log{n} + O(1)$$

Step 4: Conclude the approximation of \(n!\)

Since we have the logarithmic approximation, we can use it to conclude an approximation for \(n!\): $$\log(n!) = n\log{n} - n + \frac{1}{2}\log{n} + O(1)$$ Now, by raising both sides to the power of \(e\), we get: $$n! = e^{n\log{n} - n + \frac{1}{2}\log{n} + O(1)}$$ Using properties of exponentiation, this can be simplified to: $$n! = (n/e)^n \cdot \sqrt{n} \cdot e^{O(1)}$$ Finally, since \(e^{O(1)}\) is a constant, we can write the desired conclusion: $$n! = \Theta((n/e)^n \sqrt{n})$$

Key Concepts

Euler's Summation Formula

Euler's Summation Formula is a useful mathematical tool that helps approximate sums of functions. It bridges the gap between discrete sums and continuous integrals, making it particularly valuable when dealing with sequences that grow large. The formula can be expressed for a function \( f(x) \) as:

• \( \sum_{k=1}^{n} f(k) \approx \int_{1}^{n} f(x) \,dx + \frac{f(n) + f(1)}{2} + \sum_{k=1}^{n} \{ f(k) - \lfloor f(k) \rfloor \} \)

When applying Euler’s Summation Formula to the function \(f(x) = \log x\), we need to evaluate several components:

• The definite integral \( \int_{1}^{n} \log x \, dx \), which captures the main growth of the logarithmic sum.
• The term \(\frac{\log n}{2}\), which is a correction factor for the discrete to continuous transition.
• The sum \( \int_{1}^{n} \{ \log x - \lfloor \log x \rfloor \} \,dx \), accounting for rounding in the logarithmic floor function. This remains bounded and is denoted as \(O(1)\).

Euler's Summation Formula allows us to represent the sum of logarithmic terms, providing a pathway to approximating \(\log(n!)\). This approximation is crucial in deriving the weak form of Stirling's approximation.

Factorials

Factorials, denoted as \( n! \), represent the multiplication of all positive integers up to \( n \). They appear frequently in combinatorial mathematics, probability, and calculus, illustrating growth that is both large and rapid as \( n \) increases:

• \( 1! = 1 \)
• \( 2! = 2 \times 1 = 2 \)
• \( 3! = 3 \times 2 \times 1 = 6 \)
• \( n! = n \times (n-1)! \)

For large \( n \), computing \( n! \) directly becomes challenging due to its rapid growth. This is where approximations, like Stirling's approximation, become essential. Stirling's approximation provides a way to estimate factorials using simpler functions: \[ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \]The expression \( \log(n!) \) is often analyzed instead of \( n! \) itself, leveraging properties of logarithms to simplify calculations. The weak form used here simplifies even further by approximating \( n! \) as \( \Theta((n/e)^n \sqrt{n}) \). This notation emphasizes the essential growth behavior while ignoring lower-order factors.

Logarithmic Functions

Logarithmic functions are the inverse of exponential functions, expressed generally as \( \log_b(x) \) where \( b \) is the base. In mathematics, the natural logarithm, \( \log_e(x) \) or \( \ln(x) \), is particularly significant due to its unique properties in integration and differentiation.

• The natural logarithm of a product results in the sum of the logarithms: \( \log(xy) = \log(x) + \log(y) \).
• It transforms powers into multipliers: \( \log(x^a) = a\log(x) \).

Logarithmic functions are fundamental in simplifying expressions with exponential growth like factorials. They convert products into sums, which are much easier to evaluate. In the context of approximating factorials, the logarithmic properties help format and analyze \( \log(n!) \), leading to expressions like:\[ \log(n!) = n\log(n) - n + \frac{1}{2}\log(n) + O(1) \]This transformation makes it manageable to apply mathematical tools like Euler's Summation Formula, highlighting the underlying patterns in combinatorial or statistical contexts. Understanding these properties makes logarithmic functions an indispensable element in higher mathematics.