Show $\sum_{k=1}^n \frac{(n-1)!}{k!(n-k)!(10n)^{k-1}} \leq 1.06$

Question

I was reading Lecture 7 of Afternotes on Numerical Analysis by G. W. Stewart, and he mentions without proof the following result:

If $n \epsilon_M \leq 0.1$ and $\epsilon_i \leq \epsilon_M (i = 1,2,...,n)$, then

$(1+\epsilon_1)(1+\epsilon_2)\cdots(1+\epsilon_n) = 1 + \eta$

where

$\eta \leq 1.06n \epsilon_M$.

I wanted to figure out where this comes from, and, from pretty standard manipulations, I found that it suffices to show that

$\sum_{k=1}^n \frac{(n-1)!}{k!(n-k)!(10n)^{k-1}} \leq 1.06$. I graphed this on Desmos, and it does appear that this inequality is true. However, I have no idea how to go about showing this or where to even really start with this. Any insight would be appreciated!

Answer 1

The answer above covers the computational part of the question more than adequately but it does not answer how to prove that a bound like that can be rigorously obtained.

Here's an outline of a proof using some basic calculus.

• Lemma 1: The function $f(x)=(1+\frac{a}{x})^x$ is increasing for all $x>0$ and $\lim_{x\to\infty}(1+\frac{a}{x})^x=e^a$.
• Lemma 2: (Obtaining a bound) $\frac{e^x-1}{x}\leq\frac{2+x}{2-x^2}~,~ x\in(0,\sqrt{2})$

Proof of Lemma 1: One can take a derivative of $f$ noting that $$f'(x)=f(x)\left[\log\frac{x+a}{x}+\frac{x}{x+a}-1\right]$$ Now use the well known inequality $\log t\leq t-1$, which valid for any argument and plug in $t=\frac{x}{x+a}$. This readily establishes that $$\log\left(\frac{x+a}{x}\right)\geq-\frac{x}{x+a}+1$$ which in turn shows that f is increasing since it's derivative is positive. The second part of the lemma can be proven in a variety of ways but I will skip the proof here. The monotonicity along with the limit at infinity show that for any $x,a>0$

$$f(x)\leq e^a$$

With Lemma 1 proven we establish that with $x=n, a=1/10$: $$10\left[\left(1+\frac{1}{10n}\right)^n-1\right]\leq \frac{e^{1/10}-1}{1/10}$$

Proof of Lemma 2: For any $n$, one can show using integration by parts and the fundamental theorem of calculus that $$f(x)=f(0)+xf'(0)+...+f^{(n)}(0)\frac{x^n}{n!}+\frac{1}{n!}\int_{0}^x (x-t)^nf^{(n+1)}(t)dt$$ Select $n=2$ and $f(x)=e^x$. Then

$$e^x-1=x+\frac{x^2}{2}+\int_0^x \frac{(x-t)^2}{2}e^t dt\leq x+\frac{x^2}{2}+\frac{x^2}{2}\int_0^x e^t dt=x+\frac{x^2}{2}+\frac{x^2}{2}(e^x-1)$$ Now if we rearrange and restrict $x$ to be in the range $0<x<\sqrt{2}$ which guarantees that the denominator is positive we can conclude that $$\frac{e^x-1}{x}\leq\frac{1+\frac{x}{2}}{1-\frac{x^2}{2}}$$ Finally, with $x=1/10$, one obtains a tight upper bound $$\frac{e^{1/10}-1}{1/10}\leq \frac{210}{199}<1.06$$ and the proof is complete.

Answer 2

$\sum \limits_{k=1}^{n} \frac{(n-1)!}{k! (n-k)! (10 n)^{k-1}} = \frac{1}{n} \sum \limits_{k=1}^{n} \frac{(n)!}{ k! (n-k)! } (\frac{1}{10n})^{k-1} = 10\sum \limits_{k=1}^{n} \binom{n}{k}(\frac{1}{10n})^{k} = 10((1+\frac{1}{10n})^n-1) \to 10 (e^{\frac{1}{10}}-1) $ as $n \to \infty$ and $ 10 (e^{\frac{1}{10}}-1) \approx 1.05171$