Show the rational representation of e "converges to e" under constructive math, i.e. show that $\sum _{k=j+1}^i \frac{1}{k!} \le \frac{1}{n}$.

31 Views Asked by At

I'm trying to show that $e$ has a representation in constructive mathematics from Wikipedia's definition of convergence and definition of finite e.

Here is their definition of "convergence": letting $f$ be a function that takes a positive integer $n$ and outputs a rational $f(n)$, together with a function $g$ such that g takes a positive integer and outputs a positive integer $g(n)$ such that:

Wikipedia

Basically instead of $\epsilon$, they squeeze rational numbers outputted by $f$ together with $1/n$. (It's a very nice trick, in my limited opinion.)

According to Wiki, $e$ has representation given a function f such that $f(n) = \sum_{i=0}^n \frac{1}{i!}$, $g(n) = n$.

I tried to verify that the rational approximation of $e$ given by $f$ and $g$ really does "converge". To do this, I needed to show the above definition holds for the representation given by $f,g$ as below:

f,g

Since the definition of "convergence" was given in terms of $n, i, j$, I restated

$f(i) = \sum_{k=0}^i \frac{1}{k!}$, $f(j) = \sum_{k=0}^j \frac{1}{k!}$

This gave me a very natural bound, i.e. for $i \gt j \geq n \geq 1$,

$|f(i) - f(j)|$ = $\sum_{k=j+1}^i \frac{1}{k!}$ which in turn I have no idea how to bound it by $1/n$.

($i = j$ gives me my result instantly, since $|f(i) - f(j)| = 0 \leq \frac{1}{n}, \forall n \geq 1$ so we assume $i \gt j$ WLOG)

I tried some sum formulas, strong induction, directly manipulating the series, basically everything under the sun but I could not show this.

I feel like it should be easy but I have no clue why I can't get it. Any small hint would be appreciated.

1

There are 1 best solutions below

5
On

You're quite close.

You have $|f(i)-f(j)| = \displaystyle\sum_{k = j+1}^i \dfrac{1}{k!}$. You want to bound that by $1/n$ for some $n$ (actually, note that in the definition of convergence that you stated, the point is to bound $|f(i)-f(j)|$ by a decreasing function that converges to 0 (which is enough to show that the distance between two points will converge to $0$, which in $\mathbb{R}^n$ (a complete space) is the same thing as convergence. So here, you are trying to bound your left-hand-side by $1/n$, but you could use other functions like $1/n^2, 1/n!$, etc... or anything that converges to $0$).

So now let's look at it. Clearly, $(k+1)! > k! \implies \dfrac{1}{(k+1)!} < \dfrac{1}{k!}$.

Therefore, $\displaystyle\sum_{k = j+1}^i \dfrac{1}{k!} = \dfrac{1}{k!} + \dfrac{1}{(k+1)!} + ... + \dfrac{1}{i!} < \dfrac{1}{k!} + \dfrac{1}{k!} + ... + \dfrac{1}{k!} = \dfrac{i-k}{k!}$

Now, you are almost done, because the right hand side converges to $0$ as $k \to \infty$. Indeed, the top of the fraction keeps growing as $i \to \infty$, but it grows very slowly, whereas the bottom is a factorial, so it will "beat" the top and force the fraction to go to $0$.

Now, proceeding from there, your goal is to find a number $n$ such that, for $i,k \geq n$, you have $\dfrac{i-k}{k!} \leq 1/n$. I'll leave you to do this, let me know if you want me to add some stuff to my answer :)

Note: there are many other ways this could have been done. Since it doesn't really matter what we bound $|f(i)-f(j)|$, as long as it converges to $0$, often we end up making "crude" bruteforce approximations in the calculations. So don't be scared about approximating things in your answer: as long as you keep in mind what you are trying to bound, and don't lose any information in the process!

An example of one of those crude approximations, for example, is that in the bound by $\dfrac{i-k}{k!}$, we can replace that fraction by $\dfrac{i}{k!}$. It looks like we are losing some information, but actually not really, because $|f(i)-f(j)| < \dfrac{k-i}{k!} < \dfrac{i}{k!}$. So if we manage to bound above the rightmost term, we can definitely bound the leftmost one.