# Computing coefficient of $x^n$

Find the coefficient of $x^n$ in the expansion of $$\left(1 + \frac{x}{1!} + \frac{x^2}{2!}+\cdots +\frac{x^n}{n!} \right)^2$$

How do you even start this problem? Do you use multinomial theorem or binomial theorem? Could anyone please help? I found this in a textbook of mine. What I feel hard is what to do with the factorials?

-
Start by writing out some of the terms in the square of that sum. What do they look like? –  abiessu Apr 21 '14 at 14:41

To do this, you need to look at every combination of terms that gives $x^n = x^j \cdot x^{n-j}$. We can do this using the multinomial theorem, or just multiply it out.

\begin{align*}\left(1+\frac{x}{1!} + \ldots + \frac{x^n}{n!}\right)^2 &= \left(1+\frac{x}{1!} + \ldots + \frac{x^n}{n!}\right)\left(1+\frac{x}{1!} + \ldots + \frac{x^n}{n!}\right)\\ &= 1\left(1+\frac{x}{1!} + \ldots + \frac{x^n}{n!}\right) + \frac{x}{1!}\left(1+\frac{x}{1!} + \ldots + \frac{x^n}{n!}\right) + \ldots\\ &+ \frac{x^n}{n!}\left(1+\frac{x}{1!} + \ldots + \frac{x^n}{n!}\right)\\ &= 1 + 2\frac{x}{1!} + \frac{x^2}{2!} + \left(\frac{x}{1!}\right)^2 + \frac{x^2}{2!} + \ldots \end{align*} So the $1$ coefficient is $1$, the $x$ term is $\frac{2}{1!}$, the $x^2$ term is $\frac{1}{2!} + \frac{1}{1!}\frac{1}{1!} + \frac{1}{2!}$, the $x^3$ term is $\frac{1}{3!} + \frac{1}{1!}\frac{1}{2!} + \frac{1}{2!}\frac{1}{1!} + \frac{1}{3!}$. Continuing in this manner, we get that the $x^n$ term is (using the first few terms to predict the pattern):

$$\frac{1}{n!} + \frac{1}{1!}\frac{1}{(n-1)!} + \frac{1}{2!}\frac{1}{(n-2)!} + \cdots + \frac{1}{(n-2)!}\frac{1}{2!} + \frac{1}{(n-1)!}\frac{1}{1!} + \frac{1}{n!}$$ or rewriting as a sum, we could rewrite this as \begin{align*}\sum_{j=0}^n \frac{1}{j!}\frac{1}{(n-j)!}&= \frac{1}{n!}\sum_{j=0}^n \frac{n!}{j!(n-j)!}\\ &= \frac{1}{n!}\sum_{j=0}^n \left(\begin{array}{c}n\\j\end{array}\right) 1^j 1^{n-j}\\ &= \frac{1}{n!}(1+1)^n\\ &= \frac{1}{n!}2^n \end{align*} (the second-to-last equality is the binomial theorem)

(To make sense of this when $j=0$ or $j=n$, we use the convention $0! = 1$)

-
+1. Delete the square in the RHS at the first line. –  Tunk-Fey Apr 21 '14 at 15:04
Thanks for the heads up. Fixed now. –  Nicholas Stull Apr 21 '14 at 15:06
Superb answer, really clever thinking!!!! –  user34304 Apr 21 '14 at 15:20

Hint From this expression $$\left( 1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^n}{n!}\right)\cdot\left( 1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^n}{n!}\right),$$ you can see, that you will get every element in the final sum by taking one element from the first bracket, lets say $\frac{x^i}{i!}$ and one element from the second bracket e.g. $\frac{x^j}{j!}$, where $0\leq i, j \leq n, i, j \in \mathbb{N}$. Now you can see, that $x^n$ will come from $$\frac{x^i}{i!} \cdot \frac{x^j}{j!} = \frac{1}{i!\cdot j!}x^{i+j},$$ where $i + j = n$.

Lets assume $n = 2k, k \in \mathbb{N}$. Then you get

$$2\cdot\frac{x^n}{n!} + 2\cdot\frac{x^{n-1}}{(n-1)!}\frac{x}{1}+ \cdots +2\cdot \frac{x^{n-\frac{n}{2}-1}}{\left(n-\frac{n}{2}-1\right)!}+ \frac{x^{n-\frac{n}{2}}}{\left(n-\frac{n}{2}\right)!}\frac{x^{n-\frac{n}{2}}}{\left(n-\frac{n}{2}\right)!}$$

The $2$'s comes from this fact: for $i\neq j$ we have two choices from which bracket we take $\frac{x^i}{i!}$ (and then $\frac{x^j}{j!}$ from the other). But for the last element - since we assume, that $n$ is even we have to take $\cfrac{x^{n-\frac{n}{2}}}{(n-\frac{n}{2})!}$ from both.

For $n= 2k+1, k \in \mathbb{N}$ it is quite similar.

-

Note that $$1+\frac x{1!}+\frac{x^2}{2!} +\ldots +\frac{x^n}{n!}=e^x+O(x^{n+1})$$ hence $$\left(1+\frac x{1!}+\frac{x^2}{2!} +\ldots +\frac{x^n}{n!}\right)^2=e^{2x}+O(x^{n+1})$$

-
I'm not sure I understand how the $O(x^{n+1})$ is preserved from the first line to the second... –  abiessu Apr 21 '14 at 14:43
What is O(x^n+1)? –  user34304 Apr 21 '14 at 14:48

Consider

$$\left(\sum_{i=0}^n \frac {x^i}{i!}\right)^2$$

The first $\dfrac{x^n}{n!}$ term comes from $1\cdot\dfrac{x^n}{n!}$. The second term is $\dfrac{x^1}{1!}\cdot\dfrac{x^{n-1}}{(n-1)!}=\dfrac{x^n}{(n-1)!}$, and the $k$th term is $\dfrac{x^k}{k!}\cdot\dfrac{x^{n-k}}{(n-k)!}=\dfrac{x^n}{k!(n-k)!}$ for a full sum of

$$S_n = x^n\sum_{i=0}^n{1\over i!(n-i)!}$$

This sum is very much like that of binomial sums, but it is missing the $n!$ term in the numerator to make it a simple binomial sum. Of course, this only means that it could be added like so:

$$S_n = \frac{x^n}{n!}\sum_{i=0}^n{n!\over i!(n-i)!}=\frac{x^n}{n!}\sum_{i=0}^n{n\choose i}$$

But the sum over all the terms of a binomial base $n$ is $2^n$, so we have

$$S_n = 2^n\frac{x^n}{n!}$$

-