How to prove that the exponential function is the inverse of the natural logarithm by power series definition alone The exponential function has the well-known power series representation/definition:

$e^x = \sum_{n=0}^\infty \frac{x^n}{n!}$

And the natural logarithm has the less well-known power series representation/definition:

$\ln(x) = \sum_{k=1}^\infty \frac{(x - 1)^k}{k}(-1)^{k + 1}$

Let's for the purpose of this question pretend we have no previous concept of exponentials and logarithms: all we have are two power series called $e^x$ and $\ln(x)$ and, just for the fun of it, we want to see if they are the inverse of one another. So we put one power series into the other:

$\ln(e^x) = \sum_{k=1}^\infty \frac{(\sum_{n=0}^\infty \frac{x^n}{n!} - 1)^k}{k}(-1)^{k + 1}$

How does one prove, using only the above power series, any algebraic manipulation of the expression and any theorems pertaining to power series that do not require the anterior knowledge of $e^x$ or $\ln(x)$, that this is x?
I enjoyed Christian's answer, and if you want the shortest proof starting from the series definitions, then that is the way to go.  But, like you, I was curious about this question because I like to manipulate power series, and because this problem ended up being harder than I thought it would be.
Here is a solution that meets your requirements.  The only thing I have omitted is proving that exchanging the order of summation is valid when I do it below, which is probably not the part of the proof you are interested in.
A few lemmas are needed, which I will list first.  The first two are well-known combinatorial identities, and I will omit the proofs.  I'll follow your approach, but I'll delay the expansion of $e^x$ a little bit longer than you did, because otherwise you get sums over an arbitrarily large number of variables, which end up being difficult to handle.
Lemma 1: For $m,n \in \mathbb{Z}$ with $0 \le m &lt; n$,
$$ \sum_{k=0}^n (-1)^k \binom{n}{k} k^m = 0 $$
The easiest way to prove this is with calculus, but it can be proven by induction on $m$ from the result that for $n \ge 1$,
$$ \sum_{k=0}^n (-1)^k \binom{n}{k} = 0 $$
which itself can be proven by induction on $n$.  So, no calculus required.
Lemma 2:
$$ \sum_{n=k}^m \binom{n}{k} = \binom{m+1}{k+1} $$
This can also be proven by induction.
Lemma 3: $ e^x e^y = e^{x+y} $
Proof: This one is a lot easier than the main result.  Expand the right hand side using the series definition and the binomial theorem to get
$$ e^{x+y} = \sum_{m=0}^\infty \frac{(x + y)^m}{m!} = \sum_{m=0}^\infty \sum_{i=0}^m \frac{1}{m!} \binom{m}{i} x^i y^{m-i} = \sum_{i=0}^\infty \sum_{m=i}^\infty \frac{x^i y^{m-i}}{i! (m-i)!} $$
Let $j=m-i$ and the sums become independent:
$$ \sum_{i=0}^\infty \sum_{m=i}^\infty \frac{x^i y^{m-i}}{i! (m-i)!} = \sum_{i=0}^\infty \sum_{j=0}^\infty \frac{x^i y^j}{i!j!} = \left( \sum_{i=0}^\infty \frac{x^i}{i!} \right) \left( \sum_{j=0}^\infty \frac{x^j}{j!} \right) = e^x e^y $$
Lemma 4: $ (e^x)^y = e^{xy} $ when $y$ is a nonnegative integer.
Proof: This is obvious using Lemma 3.
Main result: $ \log(e^x) = x $
Proof: Apply the power series for the logarithm, then a binomial expansion, and then the power series for the exponential.
$$ \begin{align}
\log(e^x) &amp;= \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} ( e^x - 1 )^n \\
&amp;= \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} e^{kx} \\
&amp;= \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} \sum_{m=0}^\infty \frac{k^m x^m}{m!} \\
&amp;= -\sum_{m=0}^\infty \frac{x^m}{m!} \sum_{n=1}^\infty \frac{1}{n} \sum_{k=0}^n \binom{n}{k} (-1)^k k^m \\
&amp;= -\sum_{m=0}^\infty \frac{x^m}{m!} a_m \tag{1} \label{1}
\end{align} $$
where $a_m$ has been defined as
$$ a_m = \sum_{n=1}^\infty \frac{1}{n} \sum_{k=0}^n \binom{n}{k} (-1)^k k^m $$
Split the sum over $n$ into two parts, from $1$ to $m$ and from $m+1$ to $\infty$.
$$ a_m = \sum_{n=1}^m \frac{1}{n} \sum_{k=0}^n \binom{n}{k} (-1)^k k^m + \sum_{n=m+1}^\infty \frac{1}{n} \sum_{k=0}^n \binom{n}{k} (-1)^k k^m $$
On the right, the summation over $k$ is zero by Lemma 1 because $n &gt; m$.  This gives us
$$ a_m = \sum_{n=1}^m \frac{1}{n} \sum_{k=0}^n \binom{n}{k} (-1)^k k^m \label{2} \tag{2} $$
In this expression, when $k \ge 1$, we can apply the identity
$$ \frac{1}{n} \binom{n}{k} = \frac{1}{k} \binom{n-1}{k-1} \label{3} \tag{3} $$
Fortunately, the $k=0$ terms in \eqref{2} are all zero because of the $k^m$ term (since we are only considering $a_m$ where $m \ge 1$).  Dropping the $k=0$ terms, moving the summation over $n$ to the right, and applying \eqref{3} in \eqref{2}, we get
$$ \begin{align}
a_m &amp;= \sum_{k=1}^m (-1)^k k^m \sum_{n=k}^m \frac{1}{k} \binom{n-1}{k-1} \\
&amp;= \sum_{k=1}^m (-1)^k k^{m-1} \sum_{n=k}^m \binom{n-1}{k-1}
\end{align} $$
Applying Lemma 2 to the summation over $n$ gives
$$ a_m = \sum_{k=1}^m (-1)^k k^{m-1} \binom{m}{k} $$
This can be simplified by again applying Lemma 1.  However, note that Lemma 1 requires the $k=0$ terms, which we dropped earlier so that we could apply \eqref{3}.  Now the $k=0$ term in the sum must be replaced by including $k=0$ in the sum and subtracting it outside the sum.
$$ a_m = \left( \sum_{k=0}^m (-1)^k k^{m-1} \binom{m}{k} \right) - 0^{m-1} $$
Obviously this term on the right is zero when $m&gt;1$, but the $m=1$ case results in $0^0$.  Here the appropriate convention is that $0^0=1$.  (For example, when we expanded the exponential as $e^{kx} = \sum_m k^m x^m/m!$, the $m=0$ term is interpreted as $1$ even when $k=0$.)  Since the $0^{m-1}$ term yields 0 for $m \ne 1$ and 1 for $m=1$, we can write this using the Kronecker delta as $\delta_{m,1}$.
$$ a_m = \left( \sum_{k=0}^m \binom{m}{k} (-1)^k k^{m-1} \right) - \delta_{m,1}  $$
Now Lemma 1 can be applied again.  (Note that the conditions of the lemma are satisfied because $m-1 &lt; m$.)  This gives $ a_m = -\delta_{m,1} $.  Inserting this into $\eqref{1}$ gives the final result,
$$ \log(e^x) = x $$
I like the series approaches above, quite interesting.

I had a much more mundane approach that involves using the chain rule and inverse functions.  Suppose that g(x) is the inverse of f(x), whereby

g(f(x))=x

Take the derivative of both sides (remember the chain rule):

(dg/df)(df/dx)=1

Take the special case that f(x)=exp(x).

(dg/df)exp(x)= (dg/df)f = 1
or 
dg/df = 1/f

Integrating both sides, you'll get that g(f) is whatever the integral of 1/f comes to.  Calling that the logarithm,

g(f)=ln(f)

That works with x too:  g(x)=ln(x) which is the inverse of f(x)=exp(x)