TITLE: power series of function
QUESTION [3 upvotes]: I am studying on summation theory on power series of functions.
My question is to find the sum of power series  $$e^{-n} \sum_{k=0}^{\infty} \frac{n^k}{k!}\frac{k}{k+1}.$$ I tried apply differentiation and integration but could not find anything useful. Thanks in advance from now.

REPLY [3 votes]: You are starting with
$$ e^{-x} \sum_{k = 1}^\infty \frac{kx^k}{(k+1)!} = e^{-x}F(x),$$
which is almost very easy. Let's ignore the $e^{-x}$ piece, because it's not interesting. So we just consider $F(x)$.
Notice that $\dfrac{F(x)}{x} = \displaystyle\sum_{k = 1}^\infty \frac{kx^{k-1}}{(k+1)!}.$ If we integrate this, we see that
$$\begin{align} \int_0^x \frac{F(t)}{t} dt &= C + \sum_{k = 1}^\infty \frac{x^k}{(k+1)!} = C + \frac{1}{x}\sum_{k = 2}^\infty \frac{x^k}{k!} \\
&= C - \frac{1}{x} - 1 + \frac{1}{x} \sum_{k = 0}^\infty \frac{x^k}{k!} \\
&= \frac{e^x}{x} - \frac{1}{x} - 1 + C.
\end{align}$$
We are interested in $F(x)$, which we recover from the fundamental theorem of calculus.
$$\begin{align}
\frac{d}{dx} \int_0^x \frac{F(t)}{t} dt &= \frac{F(x)}{x} \\
&= \frac{d}{dx} \left( \frac{e^x}{x} - \frac{1}{x} - 1 + C \right) \\
&= \frac{e^x}{x} - \frac{e^x}{x^2} + \frac{1}{x^2}
\end{align}$$
Thus
$$ F(x) = e^x - \frac{e^x}{x} + \frac{1}{x},$$
so that
$$e^{-x}F(x) = 1 - \frac{1}{x} + \frac{e^{-x}}{x},$$
which is your answer. $\diamondsuit$


TITLE: Matrix Chain Multiplication?
QUESTION [6 upvotes]: The following are questions about using dynamic programming for matrix chain multiplication. Pseudocode can be found in the Wikipedia article on matrix chain multiplication.
1) Why is the time complexity for trying all bracket permutations $\mathcal{O}(2^n)$, where $n$ is the number of matrices??
2) Why are there $\frac{n^2}{2}$ unique subsequences? (This question is refering to memoization where all unique subproblems are stored. A rephrasing of this question would be: Why are there $\frac{n^2}{2}$ unique subproblems to be stored?)
3) Why does using memoization reduce the time to $O(n^3)$?
I don't have made any progress on the above questions, therefore there is no work for me to show.

REPLY [1 votes]: The combinatorial background related to bracket permutations (plus loads of other things) can be found on the wikipedia page on Catalan numbers: http://en.wikipedia.org/wiki/Catalan_number . This may be overkill for your applications, I'm sure there is a nice and quick way to give your desired $\mathcal{O}(2^n)$ bound along the lines that Belgi was considering in his answer. I will update this if I can think of anything.
The number of subsequences can be estimated as such: There are $n-1$ subsequences starting with the first matrix (1 of length 2, ..., 1 of length $n$), $n-2$ subsequences starting with the second matrix, etc, which gives a total of $(n-1)+(n-2)+...+1=\frac{n(n-1)}{2} = \mathcal{O}(n^2)$ such subsequences.


TITLE: When does $\sum_{n=0}^\infty \frac{a_n x_n}{n!}f(b_nx)$ converge for given $f\in C_c^\infty(\Bbb{R})$ and $(a_n)_{n=0}^\infty$?
QUESTION [2 upvotes]: Let $f\in C_c^\infty(\Bbb{R})$ be such that $f(x)=1$ for $x\in (-1,1)$. Given a real sequence $(a_n)$, define
  $$
g(x):=\sum_{n=0}^\infty \frac{a_n x^n}{n!}f(b_nx), \quad x\in\Bbb{R}
$$
  where $(b_n)$ is another real sequence.
  When (i.e. for what $(b_n)$) is $g\in C_c^\infty(\Bbb{R})$?

If there are only finitely many nonzero terms in $(a_n)$, any $(b_n)$ would work. I don't see how one should approach the general case.

By the property of $f$, one has
$$
\left|\frac{a_nx^n}{n!}f(b_nx)\right|\leq \frac{|a_n|}{|b_n|^n\cdot n!}.
$$
Hence if $|b_n|^n\geq |a_n|$, then one has the uniform convergence. But still, I don't see how to get $g\in C^\infty$.

REPLY [0 votes]: I can put some constraints on the series:
1) If $inf |b_n| = 0$ then there can be only finitely many nonzero terms in $(a_n)$, otherwise $g$ does not have compact support.
2) If $b_n = B$ then $\sum_{n=0}^\infty \frac{a_n x^n}{n!}$ must converge on the support of $f(Bx)$.
3) If $b_n \to \infty $ and $a_n = n! b_n^n$ then $\frac{a_n x^n}{n!}f(b_nx) =1 $ for $x = 1/b_n$ (and zero for $x=0$ ). I think the sum cannot converge to a $C^\infty $ function.