One of the classical characterizations of the Exponential function is to define it by the following limit.
$e^x=\displaystyle\lim_{n \to \infty}\left(1+\frac{x}{n}\right)^n$
Characterizations of the exponential function gives the following as the first few error terms of this limi-expression,
$\displaystyle\left(1+\frac{x}{n}\right)^n=e^x\left(1-\frac{x^2}{2n}+\frac{x^3(8+3x)}{24n^2}-\cdots\right)$
stating that the numerators of the $n^k$ terms are polynomials in $x$ of degree $2k$. However, no mention is made about the computation of the coefficients or their relation with each other (if there is any).
That exactly is the point of this post. We try to derive an expression which allows us to calculate the coefficients as we desire. Considering that this definition of the Exponential function is all over the internet, I was disappointed that I could not find any reference regarding these coefficients.
Based on Wikipedia's expression, we suspect that,
$\displaystyle e^{-x}\left(1+\frac{x}{n}\right)^n=\sum_{i\geq j \geq 0}(-1)^{i}p_{i,j}\frac{x^{i+j}}{n^i}$
where we seek to compute the coefficients $p_{i,j}$. Now using the substitutions $x \to -nx$ and $n \to -1/n$ (in that order), we can see that,
$e^{-x/n}(1-x)^{-1/n}=\displaystyle\sum_{i\geq j \geq 0}p_{i,j}\frac{x^{i+j}}{n^j}$
But $e^{-x/n}(1-x)^{-1/n}=e^{-(x+\ln{(1-x)})/n}=\displaystyle\sum_{j=0}^\infty(-x+\ln{(1-x)^{-1}})^j\frac{1}{n^jj!}$
Comparing the coefficients of powers of $n$, we have,
$x^jp_j(x)=\displaystyle x^j\sum_{i=0}^\infty p_{i,j}x^i=\frac{1}{j!}(-x+\ln{(1-x)^{-1}})^j$
This readily gives a combinatorial representation. That is, $(i+j)!p_{i,j}$ is the number of derangements of $[1,2,3,\cdots,i+j]$ with exactly $j$ cycles. Therefore,
$\displaystyle (i+j)!p_{i,j}=\sum_{k=0}^j (-1)^{j-k}\binom{i+j}{i+k}\begin{bmatrix}i+k\\k\end{bmatrix}=\sum_{k=0}^j (-1)^{i+j-k}\binom{i+j}{i+k}s(i+k,k)$
where $\begin{bmatrix}n\\k\end{bmatrix}$(and $s(n,k)$) are the unsigned (and signed) Stirling numbers of the first kind.
Also, using the same derangement interpretation, we can easily see that,
$\displaystyle \sum_{j=0}^i i!p_{i-j,j}=i!\sum_{j=0}^i\frac{(-1)^j}{j!}\implies \sum_{j=0}^i p_{i-j,j}=\sum_{j=0}^i\frac{(-1)^j}{j!}$
On the other hand, we can derive a recurrence for $p_{i,j}$'s by manipulating $x^jp_j(x)$.
$jxp_j(x)=p_{j-1}(x)(-x+\ln(1-x)^{-1})=\displaystyle p_{j-1}(x)\left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)$
Comparing coefficients of powers of $x$, we have,
$p_{i,j}=\displaystyle\frac{1}{j}\sum_{k=2}^{i+1}\frac{1}{k}p_{i-k+1,j-1}=\frac{1}{j}\sum_{k=0}^{i-1}\frac{p_{k,j-1}}{i-k+1}$
Together with $p_{0,0}=1$ and $p_{i,j}=0$ when $i<j$ (or) $j=0$ enables us to calculate all the coefficients.
Further, we can differentiate $x^jp_j(x)$ to get a different recurrence.
$\displaystyle p_{i,j}=\frac{1}{i+j}p_{i-1,j-1}+\left(1-\frac{1}{i+j}\right)p_{i-1,j}$
This is really magical as we now have a probabilistic interpretation for the $p_{i,j}$'s.
Consider a bot that is initially at point $(i,j)$ with $i\geq j$ in the $x$-$y$ plane. The bot is programmed to move towards the origin such that at each step it either moves down-left to $(i-1,j-1)$ with some probability or moves left to point $(i-1,j)$ with the complementary probability.
If the probability of moving down-right is the inverse of the Manhattan distance between the bot's current position and the origin, then $p_{i,j}$ is the probability that bot reaches the origin without ever touching the $x$-axis or crossing the $x=y$ line.
This is simply wonderful as there does not seem to be a connection between the above probability and the error terms of the exponential function. Again the recurrence with the same boundary conditions as before gives us all the $p_{i,j}$'s.
We conclude the post with more terms of the error terms.
$\displaystyle\left(1+\frac{x}{n}\right)^n=e^x\left(1-\frac{x}{2}\frac{x}{n}+\left(\frac{x}{3}+\frac{x^2}{8}\right)\frac{x^2}{n^2}-\left(\frac{x}{4}+\frac{x^2}{6}+\frac{x^3}{48}\right)\frac{x^3}{n^3}+\left(\frac{x}{5}+\frac{13x^2}{72}+\frac{x^3}{24}+\frac{x^4}{384}\right)\frac{x^4}{n^4}-\cdots\right)$
Noting the linear term in $n$, I had the idea of using the generalized Binomial series to get the following alternate limit form. This is a better form of the limit expression as the resulting asymptotic series does not have linear term either in $n$ or in $x$.
$e^x=\displaystyle\lim_{n \to \infty}\left(1+\frac{x}{n}\right)^{n+x/2}$
That's all for today. Hope you enjoyed it.
Until then
Yours Aye
Me
$e^x=\displaystyle\lim_{n \to \infty}\left(1+\frac{x}{n}\right)^n$
Characterizations of the exponential function gives the following as the first few error terms of this limi-expression,
$\displaystyle\left(1+\frac{x}{n}\right)^n=e^x\left(1-\frac{x^2}{2n}+\frac{x^3(8+3x)}{24n^2}-\cdots\right)$
stating that the numerators of the $n^k$ terms are polynomials in $x$ of degree $2k$. However, no mention is made about the computation of the coefficients or their relation with each other (if there is any).
That exactly is the point of this post. We try to derive an expression which allows us to calculate the coefficients as we desire. Considering that this definition of the Exponential function is all over the internet, I was disappointed that I could not find any reference regarding these coefficients.
Based on Wikipedia's expression, we suspect that,
$\displaystyle e^{-x}\left(1+\frac{x}{n}\right)^n=\sum_{i\geq j \geq 0}(-1)^{i}p_{i,j}\frac{x^{i+j}}{n^i}$
where we seek to compute the coefficients $p_{i,j}$. Now using the substitutions $x \to -nx$ and $n \to -1/n$ (in that order), we can see that,
$e^{-x/n}(1-x)^{-1/n}=\displaystyle\sum_{i\geq j \geq 0}p_{i,j}\frac{x^{i+j}}{n^j}$
But $e^{-x/n}(1-x)^{-1/n}=e^{-(x+\ln{(1-x)})/n}=\displaystyle\sum_{j=0}^\infty(-x+\ln{(1-x)^{-1}})^j\frac{1}{n^jj!}$
Comparing the coefficients of powers of $n$, we have,
$x^jp_j(x)=\displaystyle x^j\sum_{i=0}^\infty p_{i,j}x^i=\frac{1}{j!}(-x+\ln{(1-x)^{-1}})^j$
This readily gives a combinatorial representation. That is, $(i+j)!p_{i,j}$ is the number of derangements of $[1,2,3,\cdots,i+j]$ with exactly $j$ cycles. Therefore,
$\displaystyle (i+j)!p_{i,j}=\sum_{k=0}^j (-1)^{j-k}\binom{i+j}{i+k}\begin{bmatrix}i+k\\k\end{bmatrix}=\sum_{k=0}^j (-1)^{i+j-k}\binom{i+j}{i+k}s(i+k,k)$
where $\begin{bmatrix}n\\k\end{bmatrix}$(and $s(n,k)$) are the unsigned (and signed) Stirling numbers of the first kind.
Also, using the same derangement interpretation, we can easily see that,
$\displaystyle \sum_{j=0}^i i!p_{i-j,j}=i!\sum_{j=0}^i\frac{(-1)^j}{j!}\implies \sum_{j=0}^i p_{i-j,j}=\sum_{j=0}^i\frac{(-1)^j}{j!}$
On the other hand, we can derive a recurrence for $p_{i,j}$'s by manipulating $x^jp_j(x)$.
$jxp_j(x)=p_{j-1}(x)(-x+\ln(1-x)^{-1})=\displaystyle p_{j-1}(x)\left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)$
Comparing coefficients of powers of $x$, we have,
$p_{i,j}=\displaystyle\frac{1}{j}\sum_{k=2}^{i+1}\frac{1}{k}p_{i-k+1,j-1}=\frac{1}{j}\sum_{k=0}^{i-1}\frac{p_{k,j-1}}{i-k+1}$
Together with $p_{0,0}=1$ and $p_{i,j}=0$ when $i<j$ (or) $j=0$ enables us to calculate all the coefficients.
Further, we can differentiate $x^jp_j(x)$ to get a different recurrence.
$\displaystyle p_{i,j}=\frac{1}{i+j}p_{i-1,j-1}+\left(1-\frac{1}{i+j}\right)p_{i-1,j}$
This is really magical as we now have a probabilistic interpretation for the $p_{i,j}$'s.
Consider a bot that is initially at point $(i,j)$ with $i\geq j$ in the $x$-$y$ plane. The bot is programmed to move towards the origin such that at each step it either moves down-left to $(i-1,j-1)$ with some probability or moves left to point $(i-1,j)$ with the complementary probability.
If the probability of moving down-right is the inverse of the Manhattan distance between the bot's current position and the origin, then $p_{i,j}$ is the probability that bot reaches the origin without ever touching the $x$-axis or crossing the $x=y$ line.
This is simply wonderful as there does not seem to be a connection between the above probability and the error terms of the exponential function. Again the recurrence with the same boundary conditions as before gives us all the $p_{i,j}$'s.
We conclude the post with more terms of the error terms.
$\displaystyle\left(1+\frac{x}{n}\right)^n=e^x\left(1-\frac{x}{2}\frac{x}{n}+\left(\frac{x}{3}+\frac{x^2}{8}\right)\frac{x^2}{n^2}-\left(\frac{x}{4}+\frac{x^2}{6}+\frac{x^3}{48}\right)\frac{x^3}{n^3}+\left(\frac{x}{5}+\frac{13x^2}{72}+\frac{x^3}{24}+\frac{x^4}{384}\right)\frac{x^4}{n^4}-\cdots\right)$
Noting the linear term in $n$, I had the idea of using the generalized Binomial series to get the following alternate limit form. This is a better form of the limit expression as the resulting asymptotic series does not have linear term either in $n$ or in $x$.
$e^x=\displaystyle\lim_{n \to \infty}\left(1+\frac{x}{n}\right)^{n+x/2}$
That's all for today. Hope you enjoyed it.
Until then
Yours Aye
Me
No comments:
Post a Comment