TITLE: Fourier series to a function
QUESTION [3 upvotes]: Assume that $f(x)$ is periodically extended outside the original interval.
Find the Fourier series of the extended function.
$f(x)=2(1-x^2), -1\leq x<1$
So I find that $a_0 =\frac{4}{3}$ and to find $a_n$ I need to compute this:
$$\int_{-1}^{1} 2 (1-x^2) \cos(n \pi x) dx$$
which is
$$\frac{8 \sin(\pi n)-8 \pi n \cos(\pi n)}{\pi^3 n^3}$$
or simply
$$\frac{-8\cos(\pi n)}{\pi^2 n^2}$$
Now I have two misunderstandings:

Looking at the answer to this exercise:
$$f(x)=\frac{4}{3}+\frac{8}{\pi^2} \Sigma _{n=1}^\infty \frac{(-1)^{n+1} \cos(n \pi x)}{n^2}$$
I conclude that I did wrong with my $a_n$ calculation.
Where is the minus sign to my $a_n$?

REPLY [2 votes]: The minus sign is absorbed by $(-1)^{n+1}$: you have your original $-1$, and then $\cos(\pi n) = (-1)^n$, so $a_n = \dfrac{8 (-1)^{n+1}}{\pi^2 n^2}$, and the constant (not depending on $n$) parts of the term are brought out front of the sum.


TITLE: Simple series convergence/divergence: $\sum_{k=1}^{\infty}\frac{2^{k}k!}{k^{k}}$
QUESTION [5 upvotes]: I have the following problem:
$$\sum_{k=1}^{\infty}\frac{2^{k}k!}{k^{k}}$$
I only need to find whether the series converges or diverges. My initial thinking was to use the ratio test. I hit a stump after simplifying my limit, though:
$$\lim_{k}\frac{2k^{k}(k+1)}{(k+1)^{k+1}}$$
Normally I'd just derive by L'Hopital's Rule, but the derivative is pretty long and complicated. I doubt that's the correct route.

REPLY [0 votes]: I thought it might be instructive to present an approach that relies on the root test and elementary tools only.  To that end, we now proceed.

Rather than use the ratio test, we use the root test.  Hence we need to evaluate the limit
$$\lim_{k\to \infty}\sqrt[k]{\frac{2^k\,k!}{k^k}}=\lim_{k\to \infty}\frac{2\sqrt[k]{k!}}{k}$$
Note that we can write
$$\begin{align}
\log\left(\frac{\sqrt[k]{k!}}{k}\right)&=\frac1k\log(k!)-\log(k)\\\\
&=\frac1k\sum_{j=1}^k\log(j)-\log(k)\\\\
&=\underbrace{\frac1k\sum_{j=1}^k\log(j/k)}_{\text{Riemann Sum for}\,\,\int_0^1 \log(x)\,dx=1}\\\\
\end{align}$$
Hence, we have
$$\lim_{k\to \infty}\sqrt[k]{\frac{2^k\,k!}{k^k}}=2e^{-1}$$
And we are done!

Tools Used.  Straightforward arithmetic and Riemann sums.


TITLE: Properties of space $X = T \cup \bigcup_{n=1}^{\infty} S_n \cup \{ (0,q) : q \in \mathbb Q \wedge q \in [0,1] \} $
QUESTION [10 upvotes]: Let $S_n$ be closed interval in euclidean plane $\mathbb R^2$ with ends in $(\frac{-1}{n}, \frac{1}{n})$ and $(\frac{-1}{n}, 1)$. Moreover let $T$ be boundary of triangle with vertices $(1,1),(0,0),(-1,1)$.

A.
  Prove that subspace of plane
  $$ X = T \cup \bigcup_{n=1}^{\infty} S_n \cup \{ (0,q) : q \in \mathbb Q \wedge q \in [0,1] \} $$ is connected space but not arc connectedness

B. Let $Y = \bar{X}$ - closure of the set $X$ in euclidean plane. Prove that $Y$ is not contractible space.

My attempt:
A.
Let $U,V$ be open sets such that $U,V  \subset \mathbb R^2$ and $X \subset U \cup V$. Assume that $(U \cap X) \cap (V \cap X)= \emptyset$. Now we want to prove that
$$(U \cap X) = \emptyset \mbox{ or } (V \cap X)= \emptyset $$
If $ X \subset U \cup V$  then $T \subset U \cup V$. So $T \cap V \neq \emptyset $ or $T \cap U \neq \emptyset$. Without lost of generality assume that $T\cap U \neq \emptyset$. Then $T \cap V = \emptyset$ because $T$ jest connected ($T$ is sum of three intervals and they create triangle and interval is connected). So $T \subset U $.
And that's why
$\forall_{n} S_n \cap U \neq \emptyset $ because boundarie of triangle $T$ are ends of intervals from $\bigcup _{n=1}^{\infty} S_n$. Each interval is connected.
Let $(\frac{-1}{n}, 1) \in \bigcup _{n=1}^{\infty} S_n$ and $J= I ((\frac{-1}{n}, \frac{1}{n}), (\frac{-1}{n}, 1))$. We know that $J \subset U \cup V$ and $J \cap U \neq \emptyset$ . That's why $J \cap V = \emptyset$ because $J$ is connected, so $J \subset U $. So we have that $T \cup \bigcup_{n=1}^{\infty} S_n \subset U$.
My problems:
Firstly, I want somebody to check my solution.
Secondly, I am not sure how can I prove that:
$$ \{ (0,q) | q \in \mathbb Q \wedge q \in [0,1] \} \subset U$$
If it comes to B. I didn't find any idea how to solve that.

REPLY [1 votes]: Notation:  $<x,y>$ denotes an ordered pair. Other brackets do not.
Exercise: In any space, if $F$ is a family of connected subspaces  and $\cap F$ is not empty then $\cup F$ is connected.
So each $T\cup S_n=\cup \{T,S_n\}$ is connected because $T$ and $S_n$ are connected and $T\cap S_n$ is not empty.
So $T\cup (\cup_{n\in \Bbb N}S_n)=\cup \{T\cup S_n: n\in \Bbb N\}$ is connected because $\cap \{T\cup  S_n: n\in \Bbb N\}=T$ is not empty.
For brevity let $W=T\cup (\cup_{n\in \Bbb N}S_n).$
Let $A,B$ be disjoint open subsets of $X$ with $A\cup B=X.$  Since $W$ is a connected subspace of $X,$ we have $W\subset A$ or $W\subset B$.... WLOG let $W\subset A.$
We have $<0,0>\in T\subset A.$ We now show that $\{0\}\times [(0,1]\cap \Bbb Q]\subset A.$
Suppose by contradiction that $q\in \Bbb Q\cap (0,1]$ and $<0,q>\in B.$ There must exist $r\in \Bbb R$ with $0<r<q/2$ such that $B\supset X\cap [(-r,r)\times (q-r,q+r)].$ But if $n\in \Bbb N$ is large enough that $1/n<r$  then, since we also have $1/n<q-r,$ we obtain $$B\cap A\supseteq B\cap S_n\supseteq$$ $$\supseteq [(-r,r)\times (q-r,q+r)]\cap S_n\supseteq$$ $$ \supseteq\{-1/n\}\times (q-r,q)\ne \emptyset$$ which is absurd.
Therefore $X$ is connected.
Addendum. Exercise: A space with a dense connected subspace is a connected space..... Now in the Q, $W$ is a dense connected subspace of $X$.


TITLE: low level math, about probability
QUESTION [0 upvotes]: let say we have $2$ boxes, box A and box B
probability of getting a blue ball from box A is 1/3
probability of getting a red ball from box B is 1/20
and 3 blue balls = 1 red ball
so which box has higher rate of getting a red ball?
the answer provided is box B
and here is the explanation
"probability of getting a blue ball is 1/3 and since we need 3 blue balls for one red ball so the chance is 1/3*1/3*1/3 = 1/27 and 1/27 is lower than 1/20"
but why 1/27 and not 1/9, i mean averagely we can get 3 blue balls every 9 try right??

REPLY [0 votes]: The probability of 3 independent events to occur after each other is the product of their probabilities.
In your case, let say that getting a blue ball is event A. So P(A,A,A)=P(A)P(A)P(A)=1/3 1/3 1/3=1/27.
Here is a well explained link where you can learn more about the probability of multiple events.
==EDIT==
The rate of blue balls is:
RateBlueBalls=#BlueBallsInTrials/#Trials , but #BlueBallsInTrials=#Trials*Pr(BlueBall)
Hence: RateBlueBalls=(#BlueBallsInTrials*Pr(BlueBall)/#Trials = Pr(BlueBall)


TITLE: asymptotic approximation when $a\to 0^+$ of $I(a):=\int_0^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$
QUESTION [2 upvotes]: I want to find an asymptotic approximation when $a\to 0^+$ for the integral
$$I(a):=\int_0^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$$
I found the following approximation:
$$C_1\, a\, \mathrm{ln}(1/a) < I(a)< C_2 \sqrt{a},$$
where $C_1$ and $C_2$ are constant terms.
I would like to have a better approximation, something of the type $I(a)=\Theta(\sqrt{a})$ or $I(a)=\Theta(a\, \mathrm{ln}(1/a))$ when $a\to 0^+$.
In the folowing I explain how I found those bounds.
First we split our integral:
$$I(a):=\int_0^\sqrt{a} \int_0^\sqrt{a} e^{-x-y}\ dy\ dx + \int_0^\sqrt{a} \int_\sqrt{a}^{a/x}e^{-x-y}\ dy\ dx +\int_\sqrt{a}^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$$
But the two last integral are equal (clear if you draw the picture of the domain of integration and observe the symmetry), so we have: $I(a)=I_1(a)+2\, I_2(a)$ with
$$I_1(a):=\int_0^\sqrt{a} \int_0^\sqrt{a} e^{-x-y}\ dy\ dx\quad  \text{ and }\quad I_2(a):=\int_\sqrt{a}^\infty \int_0^{a/x}e^{-x-y}\ dy\ dx.$$
We consider that $a$ is small, so we have $0<a<1$ and in the domain of integration of $I_1(a)$, we have $e^{-2}<e^{-x-y}<1$. Hence
$e^{-2} a <I_1(a)< a$. That is
$$I_1(a)=\Theta(a).$$
This first integral will not play any role for our bounds, because the second integral will be much bigger (for small values of $a$).
Now we observe that if $x>\sqrt(a)$, then $a/x<a/\sqrt{a}=\sqrt{a}$. Hence
$$I_2(a)<\int_\sqrt{a}^\infty \int_0^\sqrt{a}e^{-x-y}\ dy\ dx
<\int_\sqrt{a}^\infty e^{-x} \int_0^\sqrt{a}1\ dy\ dx
=\sqrt{a}\,e^{-\sqrt{a}}<\sqrt{a}.$$
So we have proved the upper bound, and will show the above bound now.
We have for $x>\sqrt{a}>a$ and $a<1$,
$$\int_0^{a/x}e^{-y}\ dy> \frac{a}{x} e^{-a/x} >\frac{a}{x} e^{-1}.$$
So
$$I_2(a)> a\,e^{-1} \int_\sqrt{a}^\infty \frac{e^{-x}}{x}\ dx
>a\,e^{-1} \int_\sqrt{a}^1 \frac{e^{-x}}{x}\ dx
>a\,e^{-2} \int_\sqrt{a}^1 \frac{1}{x}\ dx
=\frac{e^{-2}}{2}\,a\,\textrm{ln}(1/a).$$
This gives us the lower bound.

REPLY [1 votes]: Your method will definitely work, we just need to keep track of the errors along the way.
You showed that
$$
\begin{align}
I(a) &= 2I_2(a) + \Theta(a) \\
&= 2\int_{\sqrt{a}}^\infty e^{-x} - e^{-a/x-x}\,dx + \Theta(a). \tag{1}
\end{align}
$$
As you observed, the tail of the integral is insignificant.  In fact we have
$$
\begin{align}
0 &\leq \int_{1}^\infty e^{-x} - e^{-a/x-x}\,dx \\
&\leq \int_{1}^\infty e^{-x} - e^{-a/1-x}\,dx \\
&= (1-e^{-a}) \int_1^\infty e^{-x}\,dx,
\end{align}
$$
so that
$$
\int_{1}^\infty e^{-x} - e^{-a/x-x}\,dx = O(a). \tag{2}
$$
In the remaining interval $x \in [\sqrt{a},1]$ we have $e^{-a/x} = 1 - a/x + O(a/x)^2$.  Substituting this into the integral yields
$$
\begin{align}
\int_\sqrt{a}^1 e^{-x} - e^{-a/x-x}\,dx &= \int_{\sqrt{a}}^1 e^{-x} - e^{-x}\Bigl[1 - a/x + O(a/x)^2\Bigr]\,dx \\
&= a \int_\sqrt{a}^1 \frac{e^{-x}}{x}\,dx + O\left(a^2\int_\sqrt{a}^1 \frac{e^{-x}}{x^2}\,dx\right). \tag{3}
\end{align}
$$
In the integrals we substitute $e^{-x} = 1 + O(x)$ to get
$$
\int_\sqrt{a}^1 \frac{e^{-x}}{x}\,dx = \int_\sqrt{a}^1 \frac{dx}{x} + O(1) = \frac{\log(1/a)}{2} + O(1)
$$
and
$$
\int_\sqrt{a}^1 \frac{e^{-x}}{x^2}\,dx = \frac{1}{\sqrt{a}} + O(\log a).
$$
Thus $(3)$ becomes
$$
\int_\sqrt{a}^1 e^{-x} - e^{-a/x-x}\,dx = \frac{a\log(1/a)}{2} + O(a).
$$
Combining this with $(1)$ and $(2)$, we conclude that
$$
I(a) = a\log\left(\frac{1}{a}\right) + O(a)
$$
as $a \to 0^+$.


TITLE: Defining the derivative without limits
QUESTION [25 upvotes]: These days, the standard way to present differential calculus is by introducing the Cauchy-Weierstrass definition of the limit. One then defines the derivative as a limit, proves results like the Leibniz and chain rules, and uses this machinery to differentiate some simple functions such as polynomials. The purpose of my question is to see what creative alternatives people can describe to this approach. The nature of the question is that there is not going to be a single best answer. I have several methods that I've collected which I'll put in as answers to my own question.
It's not reasonable to expect answers to include an entire introductory textbook treatment of differentiation, nor would anyone want to read answers that were that lengthy. A sketch is fine. Lack of rigor is fine. Well known notation and terminology can be assumed. It would be nice to develop things to the point where one can differentiate a polynomial, since that would help to illustrate how your method works and demonstrate that it's usable. For this purpose, it suffices to prove that if $n>0$ is an integer, the derivative of $x^n$ equals $0$ at $0$ and equals $n$ at $1$; the result at other nonzero values of $x$ follows by scaling. Doing this for $n=2$ is fine if the generalization to $n>2$ is obvious.

REPLY [0 votes]: Let $q$ be the "ultimate" independent variable (not defined in the equation), such that each variable in the equation ultimately depends on $q$.  Therefore $y = x^2$ is actually $y(q) = x(q)^2$.  Let us then take $\epsilon$ to indicate a hyperreal infinitesimal.  We can define $\mathrm{d}(u)$ to be the differential of the expression $u$.  The differential is found by evaluating the expression at $q = q$ and $q = q + \epsilon$ and finding the difference.  So, $\mathrm{d}(u(q)) = u(q + \epsilon) - u(q)$, and, correspondingly, $u(q + \epsilon) = \mathrm{d}(u(q)) + u(q)$.  Also, notationally, for an expression which is just a single variable, $\mathrm{d}(x(q)) = \mathrm{d}x(q) = \mathrm{d}x$.
So, if we have the expression $x^2$, the differential of this is:
$$ \mathrm{d}(x^2) = (x(q + \epsilon))^2 - x(q)^2 \\
 = (\mathrm{d}x(q) + x(q))^2 - x(q)^2 \\
 = (\mathrm{d}x(q)^2 + 2x\,\mathrm{d}x(q) + x(q)^2) - x(q)^2 \\
 = \mathrm{d}x(q)^2 + 2x\,\mathrm{d}x(q)
$$
Here, you have to invoke the "principal part" function, which rounds the infinitesimal to the highest order of infinity.
$$ \mathrm{pr}\left(\mathrm{d}x(q)^2 + 2x\,\mathrm{d}x(q)\right) = 2x\,\mathrm{d}x(q) = 2x\,\mathrm{d}x$$
More information about this can be found in a paper of mine, "Total and Partial Differentials as Algebraically Manipulable Entities".
A roughly equivalent (but simplified) approach is given in the book "Calculus Made Easy".  Essentially, given a full equation, you simply replace every occurrence of each variable $u$ with $u + \mathrm{d}u$.  Therefore, given the equation $y = x^2$, you would rewrite this as:
$$
(y + \mathrm{d}y) = (x + \mathrm{d}x)^2 \\
y + \mathrm{d}y = x^2 + 2x\,\mathrm{d}x + \mathrm{d}x^2 \\
\mathrm{d}y = x^2 + 2x\,\mathrm{d}x + \mathrm{d}x^2 - y \\
\mathrm{d}y = x^2 + 2x\,\mathrm{d}x + \mathrm{d}x^2 - x^2 \\
\mathrm{d}y = 2x\,\mathrm{d}x + \mathrm{d}x^2
$$
Again, making the same simplification to the highest order infinity, this becomes $\mathrm{d}y = 2x\,\mathrm{d}x$.
Both of these methods can be applied to higher order differentials by noting that $\mathrm{d}^2u = \mathrm{d}(\mathrm{d}(u(q)))$, which is a second-order infinitesimal (on the same level of infinity as $\mathrm{d}u^2$).  However, this creates a different notation for the second derivative as noted in the link above (the notation being the result of the quotient rule - for the derivative of $u$ with respect to $t$ it would be $\frac{\mathrm{d}^2u}{\mathrm{d}t^2} - \frac{\mathrm{d}u}{\mathrm{d}t} \frac{\mathrm{d}^2t}{\mathrm{d}t^2}$.


TITLE: Body Rotation in a Molecular Dynamics Simulation
QUESTION [0 upvotes]: I have been trying to simulate particles trapped in a parabolic potential in two dimensions. Due to the circular symmetry of the system, in the ground state at zero temperature, the particles are seen to arrange themselves in concentric rings. As I increase the temperature gradually, the expected result is to observe fluctuations about the mean position. However, due to the circular symmetry in the system, the particles are seen to undergo a body rotation. Can anyone please suggest a way to circumvent this self-rotation? It is imperative that the total energy remains constant during the simulation.

REPLY [1 votes]: It's hard to guess, as I said in my comment, but I'm offering this answer anyway. Most molecular dynamics thermostats do not respect angular momentum conservation. This is because most MD simulations use cubic periodic boundary conditions, in which angular momentum is not conserved (the boundary conditions break spherical symmetry). Therefore, I reckon that your thermostat imparts some angular momentum about the symmetry axis, which causes the system to rotate. Either that or your method for giving the particles an initial set of velocities results in nonzero angular momentum.
If that is the cause of the problem, it may be possible to apply a thermostat which avoids it. There are thermostats which are Galilean invariant, and preserve linear momentum. Some of them also preserve angular momentum. For example the Lowe-Andersen thermostat thermalizes randomly selected pairs of atoms $ij$: $\mathbf{v}_i \rightarrow \mathbf{v}_i+\Delta\mathbf{v}$ and $\mathbf{v}_j \rightarrow \mathbf{v}_j-\Delta\mathbf{v}$, choosing $\Delta\mathbf{v}$ to be parallel to the vector $\mathbf{r}_i-\mathbf{r}_j$. The magnitude $|\Delta\mathbf{v}|$ is chosen from the appropriate probability distribution. Then the change in angular momentum is $m(\mathbf{r}_i-\mathbf{r}_j)\times\Delta\mathbf{v}=0$. For simplicity I'm assuming equal-mass atoms.
Otherwise, my advice would simply be to choose initial velocities randomly, apply a global correction to cancel out the total angular momentum, and allow the system to equilibrate without adjusting the velocities, or at worst, simply scale them all up and down by a common factor to achieve the desired temperature.
[Edit following comment]
To remove the initial angular momentum: here is one scheme, but it is easy to devise other versions of it. I assume all masses are equal, $m$, and that the motion is in the $xy$-plane. For each particle $\mathbf{r}_i=(x_i,y_i)$ calculate the distance from the origin $r_i=|\mathbf{r}_i|=\sqrt{x_i^2+y_i^2}$, and construct the unit tangential vector $\mathbf{t}_i=(-y_i,x_i)/r_i$ (see diagram).

The idea is to adjust the velocity of every particle by $\Delta v \mathbf{t}_i$, in the tangential direction. The magnitude of the adjustment, $\Delta v$, is to be determined. By construction, the change in angular momentum about the origin will be $m\Delta v r_i$ for each particle, $m\Delta v \sum_i r_i$ in total, and we just need to choose $\Delta v$ to make this cancel the initial angular momentum.
The angular momentum ($z$-component) is given by the vector cross product formula, which we can easily rewrite in terms of the tangential vectors:
$$
L_z = \left(m \sum_i \mathbf{r}_i \times \mathbf{v}_i\right)_z
= m\sum_i ( x_i v_{i,y} - y_i v_{i,x} )
= m\sum_i r_i ( v_{i,x} t_{i,x} + v_{i,y}t_{i,y})
= m\sum_i r_i ( \mathbf{v}_i\cdot\mathbf{t}_i )
$$
From this we can calculate the necessary $\Delta v$ to cancel it out
$$
m\Delta v \sum_i r_i = -m\sum_i r_i ( \mathbf{v}_i\cdot\mathbf{t}_i )
\qquad\Rightarrow\qquad
\Delta v = -\frac{\sum_i r_i ( \mathbf{v}_i\cdot\mathbf{t}_i )}{\sum_i r_i}
$$
and then you simply replace each particle velocity by
$$
\mathbf{v}_i' = \mathbf{v}_i + \Delta v \mathbf{t}_i
$$
Do this once, at the start, after you have chosen random initial velocities. Double check that it worked, by printing out the new total angular momentum: it should be zero. Thereafter, provided your thermostat simply entails multiplying all velocities by the same common factor, the angular momentum should be conserved at zero. The only numerical problem that I can see will arise if you have placed a particle exactly at the origin (because then $\mathbf{t}_i$ is undefined). You should avoid doing that (or exclude such a particle from the calculation).


TITLE: Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size 2 are there? 2.How many subsets are there altogether?
QUESTION [4 upvotes]: Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$.
  1. How many subsets of size $2$ are there?
  2.How many subsets are there altogether?

Answer:
1) I think there are $7$ subsets of size two are there, since $14$ elements$/2=7$ and also by grouping them into pairs it shows there are $7$ groups of pairs as follows; $\{\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}, \{9,0\}, \{20,30\}, \{40,50\}\}$
2) I choose $15$, but I'm not sure.
However, are my answers valid?  Hints are much appreciated.

REPLY [1 votes]: How many subsets of size $2$ are there?

Set $A$ has $14$ elements.  In selecting a subset of size $2$, we have $14$ choices for the first element and $13$ choices for the second element.  Thus, at first glance, it appears we have $14 \cdot 13$ possible subsets.  However, the order in which the elements are selected does not matter.  Selecting the element $1$ and then the element $2$ results in the same subset as selecting the element $2$ and then the element $1$ since $\{1, 2\} = \{2, 1\}$.  Dividing by the $2! = 2$ orders in which two elements can be selected yields
$$\frac{14 \cdot 13}{2}$$
subsets with two elements.
In general, if we wish to form a subset of $k$ elements from a set of $n$ elements, we have $n$ choices for the first element, $n - 1$ choices for the second element, $n - 2$ choices for the third element, and so forth until we are left with $n - (k - 1) = n - k + 1$ choices for the $k$th element.  Hence, there are
$$n(n - 1)(n - 2) \cdots (n - k + 1)$$
ways to make an ordered selection of $k$ elements.  However, the same $k$ elements in the subset can be selected in
$$k(k - 1)(k - 2) \cdots 1 = k!$$
orders.  Thus, the number of subsets of size $k$ that we can select from a set with $n$ elements is
$$\frac{n(n - 1)(n - 2) \cdots (n - k + 1)}{k(k - 1)(k - 2) \cdots 1} = \frac{n(n - 1)(n - 2) \cdots (n - k + 1)}{k!}$$
Multiplying the numerator and denominator by $(n - k)!$ yields
$$\frac{n(n - 1)(n - 2) \cdots (n - k + 1)(n - k)!}{k!(n - k)!} = \frac{n!}{k!(n - k)!}$$
The number
$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$
is the number of subsets of $k$ elements that can be selected from a set with $n$ elements.
Hence, the number of subsets of set $A$ is
$$\binom{14}{2} = \frac{14!}{2!12!} = \frac{14 \cdot 13 \cdot 12!}{2 \cdot 1 \cdot 12!} = \frac{14 \cdot 13}{2} = 91$$
as Andre Nicolas and others have indicated.

How many subsets are there altogether?

A subset of a set $S$ with $n$ elements is determined by which elements it includes.  When forming a subset, we have two choices for each of the $n$ elements, to include the element in the subset or to not include it in the subset.  Hence, a set $S$ with $n$ elements has $2^n$ subsets.
Since set $A$ has $14$ elements, it has $2^{14}$ subsets.
While it would be impractical to list all $2^{14} = 16,384$ subsets of set $A$, we can verify that the set $\{1, 2, 3\}$ has $2^3 = 8$ subsets.  They are
$$\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}$$


TITLE: Evaluate $\sum_{n=1}^\infty \frac{(-1)^{[\sqrt{n}]}}{n^p}$ for $ 0 < p \leq 1$
QUESTION [2 upvotes]: How do you evaluate $$\sum_{n=1}^\infty \frac{(-1)^{[\sqrt{n}]}}{n^p}$$ for the case $0 < p \leq 1$?
Now I have successfully proved that the series converges for the case $p > 1$ and divergence of $p\leq 0$ is trivial, but I cannot deal with the case $0 < p \leq 1$. Wolfram Alpha tells me that it actually diverges but I completely have no idea on how to prove that.
Here $[\sqrt{n}]$ stands for the largest integer that is smaller than $\sqrt{n}$.

REPLY [5 votes]: $$S(N) = \sum_{n=1}^{N}(-1)^{\lfloor\sqrt{n}\rfloor}$$
is such that $S((2M)^2)=-2M$ and $S((2M+1)^2)=2M-1$.
In particular $|S(N)|\leq\sqrt{N}$ and this inequality is sharp for any square $N$, but the sign of $S(N)$ depends on the parity of $\lfloor\sqrt{N}\rfloor$. If we assume $p\in\left(\frac{1}{2},1\right]$ and apply summation by parts we have that the original series behaves like
$$ \sum_{n\geq 1}\frac{S(n)}{n^{p+1}}$$
which is absolutely convergent. Summation by parts also gives that the original series is not convergent for $p\in\left(0,\frac{1}{2}\right)$. It follows that the only non-trivial case to be discussed is $p=\frac{1}{2}$. In this case the partial sums of the original series keep oscillating between two finite values and the original series is not convergent. Summarizing, Kronecker's lemma or something equivalent gives that convergence happens for $p>\frac{1}{2}$.


text:
\section{Numerical results}
In this section we present the results from our numerical experiments. We will compare the performance of the proposed CGS-ls method with that of the conditional gradient (CG) method (described in \eqref{eq:cg} with weights $\lambda_i = 2i/(k(k+1))$) and the CGS method in \cite{lan2016conditional} (parameters follow Corollary 2.3 in the paper). We consider two quadratic optimization problems with different subsets; the first is over the standard spectrahedron and the second is over the convex hull of all Hamiltonian cycles. All numerical experiments are performed on a compute with Intel Core i5 2.7 GHz CPU.

In the first numerical experiment, we consider the optimization problem over the standard spectrahedron:
\begin{align}
	\min_{X\in \text{Spe}_n} f(X):=\frac{1}{2}\norm{\mathcal{A}X-B}_F^2\quad \text{where}\quad \text{Spe}_n:=\{X\in\R^{n\times n}: \text{Tr}(X)=1,\ X\succeq 0 \}.
\end{align}
Here $\mathcal{A}:\R^{n\times n}\to \R^{m}$ is a linear operator, $\|\cdot\|_F$ is the Frobenius norm, and the feasible set $\text{Spe}_{n}$ is a standard spectrahedron. Note that the linear objective optimization over the spectrahedron can be solved by computing a maximum eigenvalue problem (see, e.g., \cite{harchaoui2015conditional}). For each random instance in this numerical experiment, we generate $\mathcal{A}$ first by equivalently generating a $m\times n^2$ matrix with $20\%$, $60\%$ or $80\%$ nonzero entries that follow i.i.d. standard normal distribution. We then generate $B=\mathcal{A}U\Sigma U^\top$ where $U$ is a random orthogonal matrix and $\Sigma$ is a diagonal matrix with uniformly random entries between 0 and 1 (normalized afterwards so that they sum to $1$). Therefore, the optimal value of all generated instances are $0$.

In the second numerical experiment, we consider the optimization problem over the convex hull of Hamiltonian cycles in \cite{lan2017conditional}:
\begin{align}
	&\min_{x\in \mathcal{H}} f(x):=\frac{1}{2}\norm{Ax-b}_2^2\quad \text{where}\quad \mathcal{H}=\text{conv}\{x\in\R^{n(n-1)/2}: x\text{ is a Hamiltonian cycle} \}.
\end{align}
Here $A:\R^{m\times [n(n-1)/2]}$, $b \in \R^m$, and the feasible set $\mathcal{H}$ is the convex hull of all Hamiltonian cycles in a complete graph with $n$ nodes. We describe any Hamiltonian cycle through a vector of dimension $n(n-1)/2$ (the lower triagular part of the adjacency matrix). Note that the linear objective optimization over $\mathcal{H}$ can be solved by computing the solution to a traveling salesman problem (solved through Gurobi \cite{gurobi}). For each random instance, $A$ is randomly generated with $60\%$ nonzero entries that follow i.i.d. standard uniform distribution. We then generate $b=A(0.8v_1+0.2v_2)$ where $v_1$ and $v_2$ are two Hamiltonian cycles that are generated from random permutations of all nodes. The optimal value of all generated instances are $0$.

\begin{tiny}
	\begin{table}[!t]
		\centering
		\caption{\label{tab:SPE}Comparison of CG, CGS and CGS-ls on the first numerical experiment (minimization over standard spectrahedron).}

		\centering

		\begin{tabular}{|c|c|c||c c c||c c c c||c c c c|}
			\hline
			\multicolumn{3}{|c||}{Instance info.} & \multicolumn{3}{c||}{CG} & \multicolumn{4}{c||}{CGS} & \multicolumn{4}{c|}{CGS-ls}\\
			\hline
			m & n & density & iter. & time & obj. & outer & inner & time & obj. & outer & inner & time & obj. \\
			\hline
			1000 & 100 & .2 & 21908 &  543 & 3e-6 & 264 & 528 & 10 & 3e-6 & 148 &  919 & 13 & 6e-8 \\
			2000 & 100 & .2 & 38861 & 1427 & 3e-6 &  842 & 1871 &  38 & 4e-6 & 232 & 1961 & 26 & 8e-8 \\
			3000 & 100 & .2 & 36402 & 1800 & 5e-6 &  900 & 2368 &  53 & 8e-6 & 219 & 2175 & 26 & 2e-7 \\

			\hline
			1000 & 100 & .6 & 45170 & 1800 & 1e-6 & 379 & 758 & 18  & 1e-6 & 307 & 1540 & 24 & 2e-8 \\
			2000 & 100 & .6 & 26855 & 1800 & 1e-5 & 1309 & 2964 &  91 & 2e-6 & 343 & 2578 & 35 & 2e-8 \\
			3000 & 100 & .6 & 18830 & 1800 & 5e-5 & 1410 & 3811 & 138 & 3e-6 & 291 & 2797 & 38 & 1e-7 \\

			\hline
			1000 & 100 & .8 & 39448 & 1800 & 1e-6 & 393 & 786 & 21  & 1e-6 & 328 & 1625 & 27 & 1e-8 \\
			2000 & 100 & .8 & 22728 & 1800 & 1e-5 & 1475 & 3361 & 117 & 1e-6 & 446 & 2704 & 42 & 3e-8 \\
			3000 & 100 & .8 & 16055 & 1800 & 8e-5 & 1551 & 4223 & 170 & 3e-6 & 320 & 3360 & 45 & 5e-8 \\

			\hline
		\end{tabular}

		\ \\
		\vspace{1cm}

		\caption{\label{tab:TSP}Comparison of CG, CGS and CGS-ls on the second numerical experiment (minimization over the convex hull of Hamiltonian cycles).}

		\centering
		\begin{tabular}{|c|c|c||c c c||c c c c||c c c c|}
			\hline
			\multicolumn{3}{|c||}{Instance info.} & \multicolumn{3}{c||}{CG} & \multicolumn{4}{c||}{CGS} & \multicolumn{4}{c|}{CGS-ls}\\
			\hline
			m & n & density & iter. & time & obj. & outer & inner & time & obj. & outer & inner & time & obj. \\
			\hline
			1e3 & 20 & .6 & 37259 &  596 & 3e-6 &  6246 & 12492 &  197 & 4e-3 & 1108 & 2493 &  39 & 4e-4 \\
			1e3 & 25 & .6 & 48415 &  968 & 1e-5 &  9236 & 18472 &  502 & 4e-3 & 1526 & 3730 &  91 & 5e-4 \\
			1e3 & 30 & .6 & 56254 & 1800 & 1e-5 & 12542 & 25084 &  735 & 4e-3 & 1883 & 4734 & 142 & 4e-4 \\
			1e3 & 35 & .6 & 45355 & 1800 & 2e-5 & 15390 & 30780 & 1323 & 5e-3 & 2210 & 5636 & 233 & 4e-4 \\
			1e3 & 40 & .6 & 27638 & 1800 & 1e-4 & 14445 & 28890 & 1800 & 9e-3 & 2511 & 6335 & 374 & 4e-4 \\

			\hline
			1e4 & 15 & .6 & 92429 & 1800 & 4e-6 & 11927 & 23854 &  473 & 5e-3 & 2589 &  6711 & 117 & 7e-4 \\
			1e4 & 20 & .6 & 67756 & 1800 & 1e-5 & 19508 & 39016 &  841 & 5e-3 & 3535 &  8702 & 180 & 3e-4 \\
			1e4 & 25 & .6 & 52912 & 1800 & 8e-5 & 23044 & 46088 & 1800 & 7e-3 & 4529 & 11964 & 364 & 3e-4 \\
			1e4 & 30 & .6 & 31736 & 1800 & 2e-4 & 19272 & 38544 & 1800 & 2e-2 & 5564 & 15378 & 623 & 2e-4 \\
			1e4 & 35 & .6 & 24348 & 1800 & 6e-4 & 14771 & 29542 & 1800 & 5e-2 & 6480 & 17848 & 894 & 2e-4 \\

			\hline
			1e5 & 15 & .6 & 18433 & 1800 & 1e-3 & 14924 & 29848 & 1800 & 3e-2 & 8036 & 15825 &  774 & 1e-3 \\
			1e5 & 17 & .6 & 14281 & 1800 & 5e-3 & 12791 & 25582 & 1800 & 7e-2 & 8659 & 18406 &  943 & 5e-4 \\
			1e5 & 20 & .6 &  9715 & 1800 & 3e-3 &  9019 & 18038 & 1800 & 2e-1 & 9277 & 18801 & 1427 & 3e-4 \\

			\hline
		\end{tabular}
	\end{table}

\end{tiny}

We report the performance of CG, CGS, and CGS-ls in the above two numerical experiments in Table \ref{tab:SPE} and Table \ref{tab:TSP} respectively. For CG and CGS, we terminate when the Wolfe gap described in \eqref{eq:WolfeGap} is smaller than $0.01$; for CGS-ls, we terminate when the gap describe in \eqref{Alg:CGSLS:minep} is smaller than $0.01$. Consequently, all algorithms terminate either when an approximate solution is certified with $\varepsilon=0.01$ (or when the algorithm runs over 30 minutes). Note that CGS requires the Lipschitz constant of the objective function; we compute them through the maximum eigenvalue of the Hessian of the objective function (the time for computing maximum eigenvalue is not counted towards CGS' computation time). For CGS-ls, we set $L_0=10$ for all instances, and $D=0.005\sqrt{2}$ and $D=0.05\sqrt{n(n-1)/2}$ for the first and second numerical experiments, respectively. We report the running time (in seconds) and the objective value of the approximate solution at termination for all algorithms. For CG, we report its total number of iterations, which is the same as the number of gradient evaluations and linear optimization subproblems. For CGS and CGS-ls, we report the total number of gradient evaluations (denoted ``outer'') and linear optimization subproblems (denoted as ``inner'').

We make a few remarks from Tables \ref{tab:SPE} and \ref{tab:TSP}. First, among the three algorithms, CG is the simplest to implement but has the worst performance; in most of the instances it could not obtain an approximate solution with Wolfe gap smaller than $0.01$ within the required 30 minute computation time limit. Such behavior is consistent with its theoretical complexity $\MO(L/\varepsilon)$, which is the worst among the three algorithms. Second, CGS-ls has better practical performance than CGS-ls in most instances, although both algorithms have the same theoretical convergence properties. The better practical performance is most likely due to the adaptive estimate of Lipschitz constant, which avoids the potentially conservative Lipschitz constant that CGS may suffer throughout the computation. Finally, it is interesting to observe that most objective values of the approximate solutions computed by all algorithm at termination are much better than the accuracy setup $\varepsilon=0.01$. To the best of our knowledge, it is still unclear in the literature whether there exists termination criterion other than the ones we use in this paper (\eqref{Alg:CGSLS:minep} and \eqref{eq:WolfeGap}) that could guarantee that the approximate solution at termination is an $\varepsilon$-solution while achieving good practical performance. We leave the study of better termination criterion as a future work.

config: arxiv