Now that I've begun to blog a little Mathematics, I suddenly find it difficult hold myself from not blogging. I started digging my amateurish works in mathematics and I found some worth blogging. Lemme start with one on the Exponential Generating Functions.
Well, Generating functions are ubiquitous in Mathematics. There are many forms of generating functions available at a mathematician's arsenal depending on which area of mathematics he's working. If I have to give my favorites, I would go for the Ordinary generating functions (OGFs) and the Exponential generating functions (EGFs) mostly because of their versatility in Combinatorics. Apart from these two, I find Dirichlet's generating functions (DGFs) and Lambert's generating functions (LGFs) of Number theory fascinating.
The idea of this post nothing innovative or original but began when I noticed something in the OGFs and wondered how to do the same for EGFs. Let's move on to that 'something'...
The Ordinary generating function of a sequence $a_n$ is $G(a_n;x)=f(x)=\sum_{n=0}^{\infty} a_n x^n$.
Therefore, we find $[x^n]f(x)=a_n$.
Let's define a new sequence, $b_n=\sum_{r=0}^na_r$. Let's denote the OFG of this new sequence by $G(b_n;x)=g(x)$. How would one find $g(x)$ given $f(x)$?
$\begin{align}
g(x)&=b_0+b_1x+b_2x^2+\cdots\\
&=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots\\
&=(a_0+a_1x+a_2x^2+\cdots)+(a_0+a_1x+a_2x^2+\cdots)x+(a_0+a_1x+a_2x^2+\cdots)x^2+\cdots\\
\end{align}$
Recognizing $a_0+a_1x+a_2x^2+\cdots$ as the OGF of $f(x)$, we get
$\begin{align}
g(x)&=f(x)+xf(x)+x^2f(x)+\cdots\\
&=(1+x+x^2+\cdots)f(x)\\
&=\frac{f(x)}{1-x}
\end{align}$
Hence $g(x)$, whose OGF coefficients are the sums of $f$'s OGF coefficients, can be found by simply diving $f(x)$ by $1-x$. Let's apply it in an example..
$x(1-x)^{-2}=x+2x^2+3x^3+\cdots=\sum_{n=0}^{\infty}nx^n$, and
$x(1-x)^{-3}=\binom{2}{2}x+\binom{3}{2}x^2+\binom{4}{2}x^3=\sum_{n=0}^{\infty}\binom{n+1}{2}x^n$ which is indeed true.
In short, $\displaystyle\sum_{r=0}^n[x^r]f(x)=[x^n](\frac{f(x)}{1-x})$.
Many would have known of this result. There's absolutely nothing new about it and any material you find on the internet would give you this one. But the question that led me to this post is how would this 'translate' to the EGFs?
Let $ f = \sum_{i=0}^\infty a_i \dfrac{x^i}{i!}$
Then $D^k f = \sum_{i=k}^\infty a_i \dfrac{x^i}{i!}$ where $D \equiv \dfrac{d}{dx}$
Summing for all $k \geq 0$,
$f + Df + D^2f + D^3f + ... = \sum_{i=0}^\infty a_i^{\infty} \dfrac{x^i}{i!}$ where $a_n^\infty = \sum_{j=n}^\infty a_j$
Denoting the RHS by $y$, we can write the above as,
$(1-D)^{-1}f=y$ (ie) $(1-D)y=f$
Solving it with Mathematica gives,
$y(x)= c e^x - e^x\int e^{-x}f(x)dx$ (c being an arbitrary constant)
Hence $y$, whose EGF coefficients are the partial sums of $f's$ EGF coefficients, has an integral expression of the above form.
Unlike the OGF version, we have
$\sum_{r=0}^nr![x^r]f(x)=a_0+a_1+a_2+\cdots+a_n=a_0^{\infty}-a_{n+1}^{\infty}=0![x^0]y(x)-(n+1)![x^{n+1}]y(x)$
In light of the above formulae, we can just set $c$ to be $0$ in the expression for $y$. That is we can re-write the formulae as,
$y(x)= -e^x\int e^{-x}f(x)dx$
In my opinion, this formulae is more subtle than the one we saw for the OGFs and is not at all obvious at first sight. Let's see what the formula gives for some functions..
$xe^x=1.\dfrac{x}{1!}+2.\dfrac{x^2}{2!}+3.\dfrac{x^3}{3!}+\cdots=\sum_{n=0}^{\infty}n \dfrac{x^n}{n!}$
$\sum_{r=0}^nr![x^r]xe^x=1+2+3+\cdots+n$
Using the formulae above, $y(x)=-e^x\int e^{-x}xe^xdx=-e^x\int xdx=\dfrac{-x^2e^x}{2}=-\dfrac{x^2}{2}-\dfrac{x^3}{2.1!}-\dfrac{x^4}{2.2!}-\cdots$
It is also easy to note that, $n![x^n]\dfrac{-x^2e^x}{2}=-\dbinom{n}{2}$
Hence,$0![x^0]\dfrac{-x^2e^x}{2}-(n+1)![x^{n+1}]\dfrac{-x^2e^x}{2}=-\dbinom{0}{2}+\dbinom{n+1}{2}=\dbinom{n+1}{2}$ as expected.
Though these results produce compact expressions for the partial sums, we have to note that they do not always give closed form solutions. For example, one may be tempted to use EGF of $(1-x)^{-1}$ to find a formulae for sum of the first $n$ factorials. But soon we find that the resulting integral in the formula above is not that easy to evaluate to give a close from solution. Nevertheless, these expressions come in handy at situations unexpected and as such would prove to surprisingly useful.
As always, I've enjoyed blogging and the joy has only doubled when it is about Mathematics. Hope you did not feel that you've wasted your time. I'll try to keep blogging at my present pace and see ya soon.
Until then
Yours Aye,
Me
Well, Generating functions are ubiquitous in Mathematics. There are many forms of generating functions available at a mathematician's arsenal depending on which area of mathematics he's working. If I have to give my favorites, I would go for the Ordinary generating functions (OGFs) and the Exponential generating functions (EGFs) mostly because of their versatility in Combinatorics. Apart from these two, I find Dirichlet's generating functions (DGFs) and Lambert's generating functions (LGFs) of Number theory fascinating.
The idea of this post nothing innovative or original but began when I noticed something in the OGFs and wondered how to do the same for EGFs. Let's move on to that 'something'...
The Ordinary generating function of a sequence $a_n$ is $G(a_n;x)=f(x)=\sum_{n=0}^{\infty} a_n x^n$.
Therefore, we find $[x^n]f(x)=a_n$.
Let's define a new sequence, $b_n=\sum_{r=0}^na_r$. Let's denote the OFG of this new sequence by $G(b_n;x)=g(x)$. How would one find $g(x)$ given $f(x)$?
$\begin{align}
g(x)&=b_0+b_1x+b_2x^2+\cdots\\
&=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots\\
&=(a_0+a_1x+a_2x^2+\cdots)+(a_0+a_1x+a_2x^2+\cdots)x+(a_0+a_1x+a_2x^2+\cdots)x^2+\cdots\\
\end{align}$
Recognizing $a_0+a_1x+a_2x^2+\cdots$ as the OGF of $f(x)$, we get
$\begin{align}
g(x)&=f(x)+xf(x)+x^2f(x)+\cdots\\
&=(1+x+x^2+\cdots)f(x)\\
&=\frac{f(x)}{1-x}
\end{align}$
Hence $g(x)$, whose OGF coefficients are the sums of $f$'s OGF coefficients, can be found by simply diving $f(x)$ by $1-x$. Let's apply it in an example..
$x(1-x)^{-2}=x+2x^2+3x^3+\cdots=\sum_{n=0}^{\infty}nx^n$, and
$x(1-x)^{-3}=\binom{2}{2}x+\binom{3}{2}x^2+\binom{4}{2}x^3=\sum_{n=0}^{\infty}\binom{n+1}{2}x^n$ which is indeed true.
In short, $\displaystyle\sum_{r=0}^n[x^r]f(x)=[x^n](\frac{f(x)}{1-x})$.
Many would have known of this result. There's absolutely nothing new about it and any material you find on the internet would give you this one. But the question that led me to this post is how would this 'translate' to the EGFs?
Let $ f = \sum_{i=0}^\infty a_i \dfrac{x^i}{i!}$
Then $D^k f = \sum_{i=k}^\infty a_i \dfrac{x^i}{i!}$ where $D \equiv \dfrac{d}{dx}$
Summing for all $k \geq 0$,
$f + Df + D^2f + D^3f + ... = \sum_{i=0}^\infty a_i^{\infty} \dfrac{x^i}{i!}$ where $a_n^\infty = \sum_{j=n}^\infty a_j$
Denoting the RHS by $y$, we can write the above as,
$(1-D)^{-1}f=y$ (ie) $(1-D)y=f$
Solving it with Mathematica gives,
$y(x)= c e^x - e^x\int e^{-x}f(x)dx$ (c being an arbitrary constant)
Hence $y$, whose EGF coefficients are the partial sums of $f's$ EGF coefficients, has an integral expression of the above form.
Unlike the OGF version, we have
$\sum_{r=0}^nr![x^r]f(x)=a_0+a_1+a_2+\cdots+a_n=a_0^{\infty}-a_{n+1}^{\infty}=0![x^0]y(x)-(n+1)![x^{n+1}]y(x)$
In light of the above formulae, we can just set $c$ to be $0$ in the expression for $y$. That is we can re-write the formulae as,
$y(x)= -e^x\int e^{-x}f(x)dx$
In my opinion, this formulae is more subtle than the one we saw for the OGFs and is not at all obvious at first sight. Let's see what the formula gives for some functions..
$xe^x=1.\dfrac{x}{1!}+2.\dfrac{x^2}{2!}+3.\dfrac{x^3}{3!}+\cdots=\sum_{n=0}^{\infty}n \dfrac{x^n}{n!}$
$\sum_{r=0}^nr![x^r]xe^x=1+2+3+\cdots+n$
Using the formulae above, $y(x)=-e^x\int e^{-x}xe^xdx=-e^x\int xdx=\dfrac{-x^2e^x}{2}=-\dfrac{x^2}{2}-\dfrac{x^3}{2.1!}-\dfrac{x^4}{2.2!}-\cdots$
It is also easy to note that, $n![x^n]\dfrac{-x^2e^x}{2}=-\dbinom{n}{2}$
Hence,$0![x^0]\dfrac{-x^2e^x}{2}-(n+1)![x^{n+1}]\dfrac{-x^2e^x}{2}=-\dbinom{0}{2}+\dbinom{n+1}{2}=\dbinom{n+1}{2}$ as expected.
Though these results produce compact expressions for the partial sums, we have to note that they do not always give closed form solutions. For example, one may be tempted to use EGF of $(1-x)^{-1}$ to find a formulae for sum of the first $n$ factorials. But soon we find that the resulting integral in the formula above is not that easy to evaluate to give a close from solution. Nevertheless, these expressions come in handy at situations unexpected and as such would prove to surprisingly useful.
As always, I've enjoyed blogging and the joy has only doubled when it is about Mathematics. Hope you did not feel that you've wasted your time. I'll try to keep blogging at my present pace and see ya soon.
Until then
Yours Aye,
Me
No comments:
Post a Comment