TITLE: Induction Proof - Number Sequence
QUESTION [1 upvotes]: I tried this proof and my work was a bit different from how the solution solved it. I'd appreciate any feedback on my attempt:
Base case: n = 3, $a_3 ≤ 3^3$ = 25 ≤ 27, holds true
Induction Hypothesis: Assume S(k) holds for each number 3...k.
Proof of k+1:
$a_{k+1}$ = $2a_k$ + $a_{k-1}$
$< 2(3^k)+3^{k-1}$
$=3^{k+1}(\frac23+\frac19)$
$<3^{k+1}$

REPLY [1 votes]: Your proof is not correct.
You have $n=3$ as your only base case, but you should have $n=4$ as another base case. Indeed, note that your step cannot establish $S(4)$, because it can only do that if $S(2)$ holds ... which it does not.


TITLE: Extraction of coefficient from Generating Function
QUESTION [1 upvotes]: Determine the coefficient of $~x ^ {12}~$ in:
$(1+^2+^4+^6+^8+^{10}+^{12})(1+^4+^8+^{12})(1+^6+^{12})(1+^8)(1+^{10})(1+^{12})$
How to proceed with the resolution of this type of question when there is the product of more than two functions?

REPLY [2 votes]: The coefficient of $x^{12}$ is equal to the  number of partitions of $12$ in which all summands are even.
Given a partition of $12$ in which all summands are even we can divide each summand by $2$ to get a partition of $6$. And given a partition of $6$ we can find a partition of $12$ with even summands by doubling each summand. So there is a one-to-one correspondence between the partitions of $12$ in which all summands are even and the partitions of $6$.
Therefore the coefficient of $x^{12}$ is equal to the  number of partitions of $6$.


text:
\begin{document}

\begin{abstract}

Let $\Sigma=(X,\mathcal B)$ a $4$-cycle system of order $v=1+8k$. A $c$-colouring of type $s$ is a map $\phi\colon \mathcal B\rightarrow \mathcal C$,
with $C$ set of colours,  such that  exactly $c$ colours are used and for every vertex $x$ all the blocks containing $x$ are coloured exactly with $s$ colours. Let $4k=qs+r$, with $q,r\ge 0$. $\phi$ is \emph{equitable} if for every vertex $x$  the set of the $4k$ blocks containing $x$ is parted in $r$ colour classes of cardinality $q+1$ and $s-r$ colour classes of cardinality $q$. In this paper we study colourings for which $s|k$, giving a description of equitable block colourings for $c\in  \{s,s+1,\dots,\lfloor\tfrac{2s^2+s}{3}\rfloor \}$.
\end{abstract}

\maketitle

\section{Introduction}

Block colourings of $4$-cycle systems have been introduced and studied in \cite{GGR,GR}. For any vertex $x$ these colourings require particular conditions on the colours of the blocks containing $x$.

Let $K_v$ be the complete simple graph on $v$ vertices. The graph having vertices $a_1,a_2,\dots,a_k$, with $k\ge 3$, and having edges $\{a_k,a_1\}$ and  $\{a_i,a_{i+1}\}$ for $i=1,\dots,k-1$ is a $k$-cycle and it will be denoted by $(a_1,a_2,\dots,a_k)$. A $4$-cycle system of order $v$, briefly $4CS(v)$, is a pair $\Sigma=(X,\mathcal B)$, where $X$ is the set of vertices and $\mathcal B$ is a set of $4$-cycles, called \emph{blocks}, that partitions the edges of $K_v$. It is known that a $4CS(v)$ exists if and only if $v=1+8k$, for some $k\ge 0$.

A colouring of a $4CS(v)$ $\Sigma=(X,\mathcal B)$ is a mapping $\phi\colon \mathcal B\rightarrow \mathcal C$, where $\mathcal C$ is a set of colours. A $c$-colouring is a colouring in which exactly $c$ colours are used. The set of blocks coloured with a colour of $\mathcal C$ is a \emph{colour class}. A $c$-colouring of type $s$ is a colourings in which, for every vertex $x$, all the blocks containing $x$ are coloured exactly with $s$ colours.

Let $\Sigma=(X,\mathcal B)$ a $4CS(v)$, with $v=1+8k$, let $\phi\colon \mathcal B\rightarrow \mathcal C$ be a $c$-colouring of type $s$ and let $4k=qs+r$, with $q,r\ge 0$. Note that each vertex of a $4CS(v)$, with $v=1+8k$, is contained in exactly $\tfrac{v-1}{2}=4k$ blocks. $\phi$ is \emph{equitable} if for every vertex $x$  the set of the $4k$ blocks containing $x$ is parted in $r$ colour classes of cardinality $q+1$ and $s-r$ colour classes of cardinality $q$. A bicolouring, tricolouring or quadricolouring is an equitable colouring with $s=2$, $s=3$ or $s=4$.

The colour spectrum of a $4CS(v)$ $\Sigma=(X,\mathcal B)$ is the set:
\[
\Omega_s(\Sigma)=\{c\mid \text{ there exists a an $c$-block-colouring of type $s$ of $\Sigma$}\}.
\]
It is also considered the set $\Omega_s(v)=\bigcup \Omega_s(\Sigma)$, where $\Sigma$ varies in the set of all the $4CS(v)$.

Let us recall that the \emph{lower $s$-chromatic index} is $\chi'_s(\Sigma)=\min \Omega_s(\Sigma)$ and the \emph{upper $s$-chromatic index} is $\overline{\chi}'_s(\Sigma)=\max \Omega_s(\Sigma)$. If $\Omega_s(\Sigma)=\emptyset$, then we say that $\Sigma$ is uncolourable.

In the same way we consider $\chi'_s(v)=\min \Omega_s(v)$ and $\overline{\chi}'_s(v)=\max \Omega_s(v)$.

Block colourings for $s=2$, $s=3$ and $s=4$ have been studied in \cite{BM,GGR,GR}. The problem arose as a consequence of colourings of Steiner systems studied in \cite{CR,GHMR,GQ,V}.

In this paper we study colourings for which $s | k$, giving a description of equitable block colourings for $c\in  \{s,s+1,\dots,\lfloor\tfrac{2s^2+s}{3}\rfloor\}$.

\section{Main result}

In this section we prove the main result of the paper, giving in each case the construction of the desired colouring. In these constructions we will use the following symbolism. Let $A=\{a_1,a_2,\dots,a_{2p}\}$ and $B=\{b_1,b_2,\dots,b_{2q}\}$  be two sets such that $A\cap B=\emptyset$. We denote by $[A,B]$ the following family of $4$-cycles:
\[
[A,B]=\{(a_i,b_j,a_{i+p},b_{j+p})\mid 1\le i\le p,\, 1\le j \le q\}.
\]
Note that $|[A,B]|=pq$.

\begin{thm}
If $s\mid k$, then  $s,s+1,\dots,\lfloor\tfrac{2s^2+s}{3}\rfloor\in \Omega_s(v)$.
\end{thm}
\begin{proof}
Let $k=hs$, with $h\in \mathbb N$. Let $c\in\{s,s+1,\dots,\lfloor\binom{2s^2+s}{3}\rfloor\}$.

\textbf{Case $\mathbf{c=s}$}. $\Sigma=(\mathbb Z_v,\mathcal B)$ with
starter blocks $\{(0,i,4k+1,k+i)\mid 1\le i\le k\}$ is a $4$CS$(v)$. If we
assign the colour $j$ to the blocks obtined for $i=(j-1)h+1,\dots,jh$ and all
their translated forms, we get an $s$-block-colouring of type $s$ of $\Sigma$.

\textbf{Case $\mathbf{c=s+1}$}. Consider the sets $A_i=\{a_{1}^{(i)},\dots,a_{8h}^{(i)}\}$ for $i=1,\dots,s$
with $A_i\cap A_j=\emptyset$ for $i\ne j$. Take $\infty \notin A_1\cup \dots
\cup A_s$ and consider the following $4$-cycle systems of order $1+8h$:
\[
\Sigma_i=(A_i\cup \{\infty\},\mathcal B_{i})
\]
for $i=1,\dots,s$. We define the following $4$-cycle system $\Sigma=(X,\mathcal
B)$ of order $v=1+s\cdot 8h=1+8k$, with:
\[
X=\bigcup_{i=1}^s A_i\cup \{\infty\}
\]
and
\[
	\mathcal B=\bigcup_{i=1}^s \mathcal B_i\cup \bigcup_{p<q}[A_p,A_q].
\]

We define a block-colouring $f\colon \mathcal B\rightarrow \{1,\dots,s+1\}$ as
follows:
\begin{align*}
f(\medsquare)&=i\quad \forall \medsquare \in \mathcal B_i\\
f([A_p,A_q])&=i\quad  \forall p,q \mbox{ such that } p+q\equiv i \mod s+1.
\end{align*}
In this way we get a $s+1$-block-colouring of type $s$ of $\Sigma$.

\textbf{Case $\mathbf{s+2\le c\le \frac{s^2+s}{2}}$}. Take
$p_1,\dots,p_{c-s-1},q_1,\dots,q_{c-s-1}\in \{1,\dots,s\}$ such that
$(p_l,q_l)\ne (p_m,q_m)$ for $l\ne m$. We define a block-colouring
\[
g\colon
\mathcal B\rightarrow \{1,\dots,c\}
\]
as follows:
\begin{align*}
g(\medsquare)&=f(\medsquare)\quad \forall \medsquare \in \mathcal
B\setminus\{[A_{p_1},A_{q_1}],\dots,[A_{p_{c-s-1}},A_{q_{c-s-1}}]\}\\
g([A_{p_i},A_{q_i}])&=s+1+i\quad  \forall i=1,\dots,c-s-1.
\end{align*}
In this way we get a $c$-block-colouring of type $s$ of $\Sigma$.

\textbf{Case $\mathbf{\tfrac{s^2+s}{2}+1\le c \le \lfloor\tfrac{2s^2+s}{3}\rfloor}$}.
Consider the sets $A_1,\dots,A_{2s}$ defined in the following way:
\begin{itemize}
	\item $A_i=\{a_{1}^{(i)},\dots,a_{4h}^{(i)}\}$ for $i=1,3,\dots,2s-1$
	\item $A_{i+1}=\{a_{4h+1}^{(i)},\dots,a_{8h}^{(i)}\}$ for
$i=1,3,\dots,2s-1$
	\item $A_i\cap A_j=\emptyset$ for $i\ne j$.
\end{itemize}
Take $\infty \notin A_1\cup \dots \cup A_{2s}$ and consider the following
$4$-cycle systems of order $1+8h$:
\[
\Sigma_i=(A_i\cup  A_{i+1}\cup\{\infty\},\mathcal B_{i})
\]
for $i=1,3,\dots,2s-1$. Let us consider also the set:
\[
F= \{(p,q)\mid p,q=1,\dots,2s,\, p<q\}\setminus \{(1,2),(3,4),\dots,(2s-1,2s)\}.
\]
We define the following $4$-cycle system
$\Sigma=(X,\mathcal B)$ of order $v=1+2s\cdot 4h=1+8k$, with:
\[
X=\bigcup_{j=1}^{2s} A_j\cup \{\infty\}
\]
and
\[
	\mathcal B=\bigcup_{j=0}^{s-1} \mathcal B_{2j+1}\cup \bigcup_{(p,q)\in F}[A_p,A_q].
\]
Let $c=\tfrac{s^2+s}{2}+t$, with $1\le t\le \tfrac{s^2-s}{6}$. Then:
\begin{equation} \label{eq:1}
2s^2-2s=4t\cdot 3+\left(\tfrac{s^2-s}{2}-3t\right)\cdot 4.
\end{equation}
Let us consider the complete graph $K_{2s}$ and the $1$-factor
\[I= \{(1,2),(3,4),\dots,(2s-1,2s)\}.\]
By \eqref{eq:1} and by \cite[Theorem 2.4]{HHR} it is possible to divide $K_{2s}-I$ in $3$-cycles
$C_1,\dots,C_{4t}$ and in $4$-cycles $C_{4t+1},\dots,C_{\tfrac{s^2-s}{2}+t}$.

If $C_m=(i,j,k)$ is one of the $3$-cycles,
let us consider
\[\mathcal  C_m=\{[A_i,A_j],[A_j,A_k],[A_i,A_k]\};\]
if $C_m=(i,j,k,l)$ is one of the $4$-cycles, let us consider
\[\mathcal  C_m=\{[A_i,A_j],[A_j,A_k],[A_k,A_l],[A_l,A_i]\}.\]
We define a
block-colouring $f\colon
\mathcal B\rightarrow \{1,\dots,c\}$ as follows:
\begin{align*}
f(\medsquare)&=\frac{i+1}{2}\quad \forall \medsquare \in \mathcal
B_i\\
f([A_{p},A_{q}])&=s+i\quad  \forall [A_p,A_q]\in \mathcal C_i.
\end{align*}
In this way we get a $c$-block-colouring of type $s$ of $\Sigma$.
\end{proof}

\begin{cor}
If $s|k$, then $\chi'_s(v)=s$.
\end{cor}

\begin{thm}
Let us suppose that $s\mid k$. Then $\overline{\chi}'_s(v)\le
\tfrac{s^2v}{v+s-1}.$
\end{thm}
\begin{proof}
Let $\Sigma=(V,\mathcal B)$ be a 4CS$(1+8k)$ and let $\varphi\colon \mathcal
B\rightarrow \mathcal C$ be a $c$-colouring of type $s$ of $\Sigma$ and let $k=hs$. Let
$x\in \mathcal C$ and take element $v\in V$ incident with blocks of colour $x$.
$v$ is contained in $4h$ blocks colour $x$ and so in $V$ there are at least
$1+8h$ elements incident with blocks of colour $x$. Then $c(1+8h)\le sv$.
\end{proof}

config: arxiv


text:
\subsection{Stochastic Conditional Gradient Sliding}
In this section, we analyze the complexity of the stochastic gradient sliding (SCGS) algorithm under the weak growth condition. The SCGS was first proposed and thoroughly analyzed in \cite{lan2016conditional}.  It is a fundamental modification of the conditional gradient algorithm that achieved improved oracle complexities without relying on any variance reduction techniques. Below, we show that under the interpolation-like assumptions in Section~\ref{sec:assumptions}, the oracle complexity of the SCGS could be further improved compared in both the first-order and zeroth-order methods.

\begin{minipage}{.45\textwidth}
\begin{algorithm}[H]
\caption{SCGS:\\Stochastic Conditional Gradient Sliding}
\begin{algorithmic}
    \STATE \textbf{Input:} $x_0\in \Omega$,  $T$,   $\beta_t\in\reals_+$, $\gamma_t\in [0,1]$,  $b_t$, $y_0=x_0$
    \FOR{$t = 1, 2, \dots, T$}
    	\STATE Set $z_t = (1-\gamma_t)x_{t-1}  + \gamma_t y_{t-1} $
    \STATE Compute the gradient $g_t$ as follows:
        \begin{itemize}[topsep=1pt, partopsep=1pt, itemsep=1pt,parsep=1pt]
        \item[]  Set $g_t = \Tilde{\nabla}_t$ (first-order).
        \item[] Set $g_t = \bar{G}_{\nu}^{t}$ (zeroth-order).
        \end{itemize}
       \STATE Solve
       \begin{itemize}[topsep=1pt, partopsep=1pt, itemsep=1pt,parsep=1pt]
        \item[]  $y_t = \text{ICG}(g_t, y_{t-1}, \beta_t, \eta_t)$
        \end{itemize}
        by Algorithm~\ref{alg:ICG}
        \STATE Set $x_{t} = (1-\gamma_t)x_{t-1} + \gamma_t y_{t}$
    \ENDFOR
    \STATE \textbf{Output:} $x_T$
\end{algorithmic}
\label{alg:SFWSlideFandZ}
\end{algorithm}
\end{minipage}
\hfill
\begin{minipage}{.5\textwidth}
\begin{algorithm}[H]
\caption{ICG: \\Inexact Conditional Gradient Method}
\begin{algorithmic}
	  \STATE \textbf{Input:} $g, u, \beta, \eta,  u_1=u,  k=1$
      \STATE 1. Let $v_k$ be an optimal solution for the subproblem
      \begin{equation}\label{eq:acc_subprob}
      \max_{v\in\Omega} \{ h_k(v)=\inner{g+\beta(u_k-u), u_k-v} \}.
      \end{equation}
      \STATE 2. If $h_k(v_k) \leq \eta$, terminate and output $u_k$.
      \STATE 3. $u_{k+1} = (1-\alpha_k) u_k + \alpha_k v_k$ with
      $$\alpha_k = \min\bigg\{ 1, \frac{\inner{\beta(u-u_k) -g, v_t-u_t}}{\beta\norm{v_k - u_k}^2} \bigg\}.$$
      \STATE 4. Set $k\leftarrow k+1$ and go to step 1.
\end{algorithmic}
\label{alg:ICG}
\end{algorithm}
\end{minipage}

\begin{theorem}\label{thm:scgs-convex-wgc}
Consider solving problem~\eqref{eq:sopt}, by Algorithm~\ref{alg:SFWSlideFandZ}, under Assumption~\ref{ass:constrained} with $f$ being convex.
\begin{itemize}[leftmargin=0.2cm,align=left, topsep=1pt, partopsep=1pt, itemsep=1pt,parsep=1pt]
\item [(a)]  Assuming access to stochastic first-order oracle, under Assumption~ \ref{ass:WGC-variance},  setting
\begin{equation*}
	\beta_t = \frac{4L}{t+2}, \quad \gamma_t = \frac{3}{t+2}, \quad \eta_t = \frac{LD^2}{t(t+1)},\quad b_t = \big\lceil 3\rho t(t+1)\big \rceil
\end{equation*}
we have
\begin{equation*}\label{eq:scgs}
	\E[f(x_t) - f(x^*)] \leq \frac{6LD^2}{(t+2)^2} + \frac{15LD^2+3\| \nabla f(x^*) \| D}{(t+1)(t+2)}.
\end{equation*}
Hence, the total number of calls to the stochastic first-order oracle and linear minimization oracle required to be
solved to find an $\epsilon$-optimal point of problem \eqref{eq:sopt} are, respectively, bounded by
\begin{equation*}
	\mathcal{O}\left(\epsilon^{-1.5}\right), \quad \mathcal{O}\left(\epsilon^{-1}\right).
\end{equation*}
\item [(b)]
Assuming access to stochastic zeroth-order oracle, in addition, with Assumption~\ref{ass:WGC-moment}, \ref{ass:smooth-F}, setting
$$ \beta_t = \frac{4L}{t+2}, \quad \gamma_t = \frac{3}{t+2}, \quad \eta_t = \frac{LD^2}{t(t+1)}, \quad b_t = \big\lceil 6\rho(d+4) t(t+1)\big \rceil, \quad \nu = \frac{D}{(T+2)^2(d+6)^{3/2}},$$
we have
\begin{equation*}\label{eq:zscgs}
	\E[f(x_t) - f(x^*)] \leq \frac{8LD^2}{(t+2)^2} + \frac{32LD^2}{(t+1)(t+2)}.
\end{equation*}
Hence, the total number of calls to the stochastic zeroth-order oracle and linear minimization oracle required to be
solved to find an $\epsilon$-optimal point of problem \eqref{eq:sopt} are, respectively, bounded by
\begin{equation*}
	\mathcal{O}\left(d\epsilon^{-1.5}\right), \quad \mathcal{O}\left(\epsilon^{-1}\right).
\end{equation*}
\end{itemize}
\end{theorem}
To the best of our knowledge, the above complexity of $\mathcal{O}(\epsilon^{-1.5})$ is not achieved for any variance reduced versions of stochastic Frank-Wolfe methods. This improvement is solely obtained by the SCGS algorithm of~\cite{lan2016conditional} under the interpolation-like assumptions which are natural in modern machine learning problems, without any variance reduction methods. We also highlight that, in the unconstrained setting,  the stochastic gradient method performs as well as its deterministic counterpart. However, the above result still falls short of the corresponding deterministic complexity of conditional gradient sliding, which is of the order $\mathcal{O}(\epsilon^{-0.5})$~\cite{lan2016conditional}. This highlights the intrinsic difficulty associated with projection-free methods for constrained stochastic optimization problems.

\iffalse

\begin{proof}
[Proof of Theorem \ref{thm:scgs-convex-wgc}]
For convenience, let $g_t$ be the gradient estimator at $t$ step. Thus, $g_t = \tilde{\grad}_t$ for the first order method while in the zeroth order setting $g_t = \bar{G}_{\nu}^t$. First note that by \eqref{eq:acc1}, \eqref{eq:acc3}, and the convexity and the smoothness of $f$, we have
\begin{align}
	f(x_{t}) & \leq f(z_t) + \inner{\nabla f(z_t), x_t-z_t} +\frac{L}{2}\norm{x_t-z_t}^2\nonumber\\
	&= (1-\gamma_t) [f(z_{t})  +\inner{\nabla f(z_t), x_{t-1} - z_t }]+\gamma_t [f(z_{t}) + \inner{\nabla f(z_t), y_t-z_{t}}] +\frac{L\gamma_t^2}{2}\norm{y_t-y_{t-1}}^2\nonumber \\
	&\leq (1-\gamma_t) f(x_{t-1}) +\gamma_t [f(z_{t}) + \inner{\nabla f(z_t), y_t-z_{t}}] +\frac{L\gamma_t^2}{2}\norm{y_t-y_{t-1}}^2 \nonumber \\
	&= (1-\gamma_t) f(x_{t-1}) +\gamma_t [f(z_{t}) + \inner{\nabla f(z_t), y_t-z_{t}}] +\frac{\beta_t\gamma_t}{2}\norm{y_t-y_{t-1}}^2 - \frac{\gamma_t(\beta_t - L\gamma_t)}{2}\norm{y_t-y_{t-1}}^2. \label{eq:scgs-proof-1}
\end{align}
And by \eqref{eq:acc2} and \eqref{eq:acc_subprob}, we have
\begin{equation*}
\inner{g_t + \beta_t(y_t-y_{t-1}), y_t -x }\leq \eta_t, \quad \forall x\in\Omega.
\end{equation*}
Let $x=x^*$ in the above inequality. Then we have
\begin{align}
\frac{1}{2}\norm{y_t- y_{t-1}}^2 & = \frac{1}{2}\norm{y_{t-1}-x^*}^2 - \inner{y_{t-1}-y_{t}, y_t-x^*} - \frac{1}{2}\norm{y_t-x^*}^2 \nonumber\\
&\leq \frac{1}{2}\norm{y_{t-1}-x^*}^2 + \frac{1}{\beta_t}\inner{g_t, x^*-y_t} - \frac{1}{2}\norm{y_t-x^*}^2 + \frac{\eta_t}{\beta_t}. \label{eq:scgs-proof-2}
\end{align}

Denoting $\delta_t = g_t- \nabla f(z_t)$ and combining \eqref{eq:scgs-proof-1} and \eqref{eq:scgs-proof-2}, we obtain
\begin{align*}
	f(x_t)	 \leq & (1-\gamma_t) f(x_{t-1}) + \gamma_t f(x^*) + \gamma_t \inner{\delta_t, x^*-y_t}  \\
	&+ \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2) +  \eta_t\gamma_t -\frac{\gamma_t}{2} (\beta_t - L\gamma_t) \norm{y_t - y_{t-1}}^2\\
	 = & (1-\gamma_t) f(x_{t-1}) + \gamma_t f(x^*)  + \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2)+\eta_t\gamma_t\\
	 &+\gamma_t \inner{\delta_t, x^*-y_{t-1}} + \gamma_t \inner{\delta_t, y_{t-1}-y_t}  - \frac{\gamma_t}{2}(\beta_t - L\gamma_t)\norm{y_{t}-y_{t-1}}^2\\
	 \leq &(1-\gamma_t) f(x_{t-1}) + \gamma_t f(x^*)  + \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2)+\eta_t\gamma_t\\
	 &+\gamma_t \inner{\delta_t, x^*-y_{t-1}} + \frac{\gamma_t\norm{\delta_t}^2}{2(\beta_t-L\gamma_{t})},
\end{align*}
where the last inequality comes from the fact that
\begin{equation*}
	\gamma_t \inner{ \delta_t, y_{t-1} - y_t }  \leq   \frac{\gamma_t}{2(\beta_t - L\gamma_t)} \norm{ \delta_t}^2 + \frac{\gamma_t(\beta_t - L\gamma_t)}{2}  \norm{y_t - y_{t-1}}^2.
\end{equation*}

Defining
\begin{align*}
\Gamma_t &= \prod_{k=1}^{t} (1-\gamma_k), \quad \Gamma_1 = 1,\\
B_t &= \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2)+\eta_t\gamma_t +\gamma_t \inner{\delta_t, x^*-y_{t-1}} + \frac{\gamma_t\norm{\delta_t}^2}{2(\beta_t-L\gamma_{t})},
\end{align*}
substracting $f(x^*)$ from both sides of the above inequality, dividing them by $\Gamma_t$, and denoting $\phi_t = f(x_t) - f(x^*)$, we have
\begin{align*}
	\frac{\phi_1}{\Gamma_1} &\leq \frac{1-\gamma_1}{\Gamma_1} \phi_0 + \frac{B_1}{\Gamma_1},\\
	\frac{\phi_t}{\Gamma_t} &\leq \frac{\phi_{t-1}}{\Gamma_{t-1}} + \frac{B_t}{\Gamma_t}, \quad \forall t\geq 2.
\end{align*}
Summing them up for $1, \dots, t$, we obtain
\begin{equation}\label{eq:scgs-proof-basic-ineq}
	\phi_t \leq \Gamma_t\frac{1-\gamma_1}{\Gamma_1} \phi_0 +\Gamma_t \sum_{k=1}^{t} \frac{B_k}{\Gamma_k}.
\end{equation}
Let $\beta_t = \frac{4L}{t+2}, \gamma_t = \frac{3}{t+2}, \eta_t = \frac{LD^2}{t(t+1)}$. Then we have $\Gamma_t = \frac{6}{t(t+1)(t+2)}, \sum_{k=1}^{t} \frac{\eta_k\gamma_k}{\Gamma_k}\leq \frac{tLD^2}{2}$ and
\begin{align*}
	& \sum_{k=1}^{t} \frac{\beta_k\gamma_k}{\Gamma_k} (\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2) \nonumber \\
	& \leq \frac{\beta_1\gamma_1}{\Gamma_i} \norm{y_0 - x^*}^2 + \sum_{k=2}^{t} \bigg( \frac{\beta_k\gamma_k}{\Gamma_k} - \frac{\beta_{k-1}\gamma_{k-1}}{\Gamma_{k-1}} \bigg) \norm{y_{t-1}-x^*}^2\\
	&\leq \frac{\beta_1\gamma_1}{\Gamma_i} D^2 + \sum_{k=2}^{t} \bigg( \frac{\beta_k\gamma_k}{\Gamma_k} - \frac{\beta_{k-1}\gamma_{k-1}}{\Gamma_{k-1}} \bigg) D^2 = \frac{\beta_t\gamma_t D^2}{\Gamma_t} = \frac{2LD^2t(t+1)}{t+2},
\end{align*}
where the last inequality comes from the fact $\frac{\beta_k\gamma_k}{\Gamma_k} > \frac{\beta_{k-1}\gamma_{k-1}}{\Gamma_{k-1}}$.\\

We now prove part (a). Let $g_t = \tilde{\nabla}_t$. Taking expectation for both sides of \eqref{eq:scgs-proof-basic-ineq}, and noting that $	\E [\inner{\delta_t, x^*-y_{t-1}}]  = 0$ and
\begin{flalign*}
&&\E[\norm{\delta_t}^2|\mathcal{F}_{t-1}] & \leq \frac{2\rho L}{b_t} (f(z_t) - f(x^*)) & \rhd \text{ by Assumption \ref{ass:WGC-variance}}\\
&& & \leq \frac{2\rho L}{b_t} \bigg( (1-\gamma_t) \phi_{t-1} + \gamma_t (f(y_{t-1})  - f(x^*) )  \bigg)  &\rhd \text{ by the convexity and \eqref{eq:acc1}}\\
&& & \leq \frac{2\rho L}{b_t} \bigg( (1-\gamma_t) \phi_{t-1} + \frac{LD^2\gamma_t}{2}  \bigg), &\rhd \text{ by the smoothness}
\end{flalign*}
we can obtain
\begin{equation*}
	\E [\phi_t] \leq \frac{6LD^2}{(t+2)^2} + \frac{3LD^2}{(t+1)(t+2)} + \frac{3}{t(t+1)(t+2)} \sum_{k=1}^{t}\frac{\rho k(k+1)\bigg( (k-1)\E [\phi_{k-1}]  + \frac{3LD^2}{2}\bigg)}{b_k}
\end{equation*}

Set $b_k = \big\lceil 3\rho k(k+1)\big \rceil$. It is straightforward to check $\E[\phi_1] \leq \frac{LD^2}{2} $ which satisfies \eqref{eq:scgs}. By induction, if \eqref{eq:scgs} holds for all $k\leq t-1$, then with the above inequality we can obtain
\begin{align*}
	\E [\phi_t] &\leq \frac{6LD^2}{(t+2)^2} + \frac{9LD^2}{2(t+1)(t+2)} + \frac{1}{t(t+1)(t+2)} \sum_{k=1}^{t}(k-1)\E [\phi_{k-1}]\\
	&\leq \frac{6LD^2}{(t+2)^2} + \frac{9LD^2}{2(t+1)(t+2)} + \frac{1}{t(t+1)(t+2)} \sum_{k=1}^{t}\bigg( \frac{6LD^2(k-1)}{(k+1)^2} + \frac{15LD^2(k-1)}{k(k+1)} \bigg)\\
	&\leq \frac{6LD^2}{(t+2)^2} + \frac{9LD^2}{2(t+1)(t+2)} + \frac{21 LD^2}{t(t+1)(t+2)} \sum_{k=1}^{t} \frac{1}{k+1} \\
	&\leq \frac{6LD^2}{(t+2)^2} + \frac{15LD^2}{(t+1)(t+2)},
\end{align*}
i.e., \eqref{eq:scgs} holds for $k=t$. Therefore, to achieve an $\epsilon$-stationary point, the number of outer iterations $T$ can be bounded by $\mathcal{O}(1/\sqrt{\epsilon})$. Hence, the number of calls to the first order oracles can be bounded by
\begin{equation*}
	\sum_{t=1}^T b_t \leq 3\rho\sum_{t=1}^T t(t+1) = \rho T(T+1)(T+2) =\mathcal{O}(T^3).
\end{equation*}
Due to the fact that the inner iterations indeed solves a convex constrained optimization problem by the classical Frank-Wolfe method with the exact line search, one can show that the number of inner iterations $N_t$ performed at the $t$-th out iteration can be bounded by
\begin{equation*}
	N_t \leq \left\lceil \frac{6\beta_tD^2}{\eta_t} \right\rceil = \mathcal{O}(t).
\end{equation*}
Thus, the number of \blue{linear minimization problem} can be bounded by
\begin{equation*}
	\sum_{t=1}^T N_t \leq \mathcal{O}(T^2).
\end{equation*}

We now prove part (b). Let $g_t = \bar{G}_\nu^t$. Notice that $\bar{G}_\nu^t$ is a biased estimator of $\nabla f(z_t)$. We can obtain the following results by \eqref{eq:nestrov-bias}:
\begin{align*}
	\E[ \inner{\delta_t, x^* - y_{t-1}} ] &= \E[ \inner{\nabla f_{\nu}(z_t) - \nabla f(z_t), x^*- y_{t-1}}] + \E[ \inner{\bar{G}_\nu^t - \nabla f_{\nu}(z_t), x^*- y_{t-1}}]\\
	& =  \E[ \inner{\nabla f_{\nu}(z_t) - \nabla f(z_t), x^*- y_{t-1}}]\leq \frac{\nu LD(d+3)^{3/2}}{2}.
\end{align*}
Besides, we can obtain a similar bound for $\E[\norm{\delta_t}^2]$ by Lemma \ref{lem:zero_grad}.
\begin{align*}
	\E[\norm{\delta_t}^2|\mathcal{F}_{t-1}] &\leq  \frac{ 4\rho L(d+4)(f(z_{t}) - f(x^*)) }{b_t} + \nu^2 L^2 (d+6)^3\\
	&\leq  \frac{ 4\rho L(d+4)\big( (1-\gamma_t) \phi_{t-1} + \frac{LD^2\gamma_t}{2}  \big) }{b_t} + \nu^2 L^2 (d+6)^3.
\end{align*}
By \eqref{eq:scgs-proof-basic-ineq}, we have the following simplified inequality:
\begin{align*}
	\E[\phi_t] \leq & \frac{6LD^2}{(t+2)^2} + \frac{3LD^2}{(t+1)(t+2)} + \frac{\nu LD(d+3)^{3/2}}{2} + \frac{3\nu^2L(d+6)^3}{2} \\&~~+ \frac{6}{t(t+1)(t+2)} \sum_{k=1}^{t}\frac{\rho(d+4) k(k+1)\bigg( (k-1)\E [\phi_{k-1}]  + \frac{3LD^2}{2}\bigg)}{b_k}.
\end{align*}
Set $b_k = \lceil 6\rho k(k+1)(d+4) \rceil, \nu =\frac{D}{(T+2)^2(d+6)^{3/2}}\leq \frac{D}{(t+2)^2(d+6)^{3/2}}$. Then we have
\begin{equation*}
	\E[\phi_t] \leq \frac{8LD^2}{(t+2)^2} + \frac{12LD^2}{(t+1)(t+2)} + \frac{1}{t(t+1)(t+2)} \sum_{k=1}^{t} (k-1)\E [\phi_{k-1}].
\end{equation*}
Similar to the proof for part (a), we can finish the proof by induction and obtain the bounds for complexity.
\end{proof}

\fi


TITLE: A problem of decidability (predicate metalogic)
QUESTION [2 upvotes]: I have been stumped by the following and would greatly appreciate any hints or advice as to how to proceed:
For some first-order predicate logic system:
Let Γ be a decidable set of wffs such that for any closed wff σ, either Γ|= σ or Γ|= ¬σ (but not both). Prove that the set of all closed wffs deducible from Γ is decidable.
Here '|=' is taken to mean the consequent is deducible from the antecedent, and wff=well-formed formula.
Thanks to anyone who takes a stab - it is much appreciated!

REPLY [1 votes]: We give a very informal argument. Let $\Delta$ be the set of all closed formulas deducible from $\Gamma$.
We can list all proofs from $\Gamma$ as a sequence $\pi_1,\pi_2,\pi_3,\dots$. (Proofs are certain sequences of sentences.) For each proof $\pi_i$, check whether $\alpha$ or $\lnot\alpha$ is the last sentence in $\pi_i$. Since one of $\alpha$ or $\lnot\alpha$ is provable from $\Gamma$, this process will terminate, and give us a (very inefficient) decision procedure for membership in $\Delta$.


TITLE: Without axiom of choice, why can't we choose a random element for each set in an infinite collection of sets
QUESTION [1 upvotes]: If we have an infinite collection of sets, where each set contains two elements, 0 and 1, without using axioms of choice, we can define a choice function that will always pick the element 0 from each set. However, it seems that if we only assume the set contains two elements, without specifying them in detail, we can not show the existence of a choice function without using the axiom of choice.
Since all the sets has a cardinality of two, we can define bijections between the two elements in each set and {0,1}. So regardless of how the bijection is defined, we can always choose the element that maps to 0.

I don't understand the difference between this operation compares to always choosing 0 in each set, but one requires the axiom of choice, while the other doesn't.

I have read many answers on stack exchange about axioms of choice. Like this one. And I saw answers that used the word "uniform" selection. I'm really confused about what "uniform" means in this case, and no questions seem to answer my confusion.
EDIT:
The comment section is getting too long. So I posted a new question.

REPLY [6 votes]: Since all the sets has a cardinality of two, we can define bijections between the two elements in each set and {0,1}.

This actually does not help at all, although it's a little subtle to see why: it's true that for each such set, such a bijection exists, but in order to write down a choice function you need to choose a collection of such bijections for each set simultaneously. This means you need a choice function for the collection of bijections! And there are two for each set! So you're in exactly as bad a position as you were before.
To say this more explicitly, suppose $I$ is an index set and $X_i, i \in I$ is a collection of $2$-element sets indexed by $I$. You are saying: well, since by hypothesis each $X_i$ has cardinality $2$, for each $i$ there exists a bijection $X_i \cong \{ 0, 1 \}$. And yes, that's true. But to write down the choice function you want using these bijections, you need to choose one such bijection for each $i \in I$, and there are two. In other words, you need a choice function for the collection of sets $Y_i = \text{Iso}(X_i, \{ 0, 1 \})$, each of which also has two elements!

Coming at this from another direction, here is a more-or-less explicit example of a collection of sets of cardinality two where I challenge you to write down an actual choice function: consider the collection of all fields of characteristic $\neq 2$ in which $-1$ has a square root (if you want to cut this down to a set then take isomorphism classes and place some restriction on the cardinality). There are always exactly two such square roots, one of which is the negative of the other, which in the complex numbers are $i$ and $-i$. Can you tell me how to choose, for each such field, one of the two square roots of $-1$? Note that there are "surprising" examples of such fields, such as the field of $p$-adic numbers $\mathbb{Q}_p$ for $p \equiv 1 \bmod 4$ a prime.
Another example in a similar vein: consider the collection of all connected orientable manifolds. Any such manifold has exactly two orientations, one of which is the negative of the other. Can you tell me how to choose, for each such manifold, one of its two orientations?


TITLE: Integrating $ \int\frac{5}{\ 16 + 9\cos^2(x)}\,dx $
QUESTION [3 upvotes]: I am trying to integrate the following:
$$
\int\frac{5}{\ 16 + 9\cos^2(x)}\,dx
$$
I have applied the following substitution:
$$
x = \tan^{-1}u
$$
I have simplified the denominator through using the following trig identity:
$$
\cos^{2}x = 1/(1 + \tan^{2}x)
$$
$$
16  + 9(1/(1 + \tan^{2}x))
$$
$$
\frac{16(1 + tan^{2}x) + 9}{\ 1 + \tan^{2}x}\
$$
$$
= \frac{25 + 16\tan^{2}x}{\ 1 + \tan^{2}x}\
$$
Substituting the above into the denominator I get:
$$
5\int\frac{1 + \tan^{2}x}{\ 25 + 16\tan^2(x)}\,dx
$$
However, I know that the result of the above substitution should be:
$$
5\int\frac{1}{\ 16u^{2} + 25}\,du
$$
I am very close to this result except for the fact that the numerator in my integral is $1 + \tan^{2}x$ instead of 1.
I am not sure how I can get rid of the $\tan^{2}x$ in my numerator. Any insights are appreciated.

REPLY [0 votes]: Note that when you got to
$$5\int{1+\tan^2x\over25+16\tan^2x}dx$$
you haven't yet used the substitution $x=\arctan u$. If you notice $x=\arctan u$ implies $dx={du\over1+u^2}$, you see immediately that
$${1+\tan^2x\over25+16\tan^2x}dx={1+u^2\over25+16u^2}\cdot{du\over1+u^2}={1\over25+16u^2}du$$
so the result of the subsitution is indeed
$$5\int{1\over25+16u^2}du$$


TITLE: My question arises in spherical coordinate system
QUESTION [0 upvotes]: In the spherical coordinate system, we have 2 angles, namely the azimuthal angle and polar angle. My question is:

Why does the azimuthal angle have the limit of $0<\phi<2\pi$ and why does the polar angle have the limit of $0<\theta<\pi$?

I would really love a graphical representation of the reason. I have taken $\phi$ as the azimuthal angle and $\theta$ as the polar angle.

REPLY [0 votes]: First of all to simplify I  will  use the followig, let  $\theta= \text{polar angle}$ and $\phi=\text{azimuthal angle}$. Then to expalin why usually  $\theta $ is taken in $[0;\pi]$, and  $\phi$ is taken in $[0,2\pi]$, we may consider the following:
In order to cover the whole sphere we may do the following:
Consider this circle, if we rotate it horizantaly fom $0$ to $\pi$ we will cover a whole sphere, because when rotating  from $0$ to $\pi $ the  right half of the circle will cover  the right hemishere, at the same time the left half of the circle will cover the left hemishpere. Thus your sphere is cover by one circle (i.e. varying angle between  $0$ and $2\pi$), then rotating just by an angle  $\pi$.


text:
\begin{document}

\title{\bf The Topological Trees with Extreme Matula Numbers}

\author{\Large Audace A. V. Dossou-Olory\\  Department of Mathematical Sciences \\ Stellenbosch University \\ Private Bag X1, Matieland 7602 \\ South Africa\\ {\tt audace@aims.ac.za}}

\date{}

\maketitle

\begin{abstract}
Denote by $p_m$ the $m$-th prime number ($p_1=2,~p_2=3,~p_3=5,~ p_4=7,~\ldots$). Let $T$ be a rooted tree with branches $T_1,T_2,\ldots,T_r$. The Matula number $M(T)$ of $T$ is $p_{M(T_1)}\cdot p_{M(T_2)}\cdot \ldots \cdot p_{M(T_r)}$, starting with $M(K_1)=1$. This number was put forward half a century ago by the American mathematician David Matula. In this paper, we prove that the star (consisting of a root and leaves attached to it) and the binary caterpillar (a binary tree whose internal vertices form a path starting at the root) have the smallest and greatest Matula number, respectively, over all topological trees (rooted trees without vertices of outdegree $1$) with a prescribed number of leaves -- the extreme values are also derived.
\end{abstract}

\maketitle

\section{Introduction}

Fifty years ago, the American mathematician David Matula gave an explicit bijection between the set of all rooted trees and the set of all positive integers~\cite{matula1968natural}. The bijection is described by means of prime numbers. Throughout, $p_m$ always means the $m$-th prime number (in ascending order); for example,
$$
p_1=2,~p_2=3,~p_3=5,~p_4=7,~p_5=11,~p_6=13, \ldots
$$
The Matula number of the tree $K_1$ that has only one vertex is defined to be $1$, and if $T$ is a rooted tree with branches (the components that remain after deleting the root and all edges incident to it) $T_1,T_2,\ldots,T_r$, then the Matula number of $T$ -- henceforth denoted by $M(T)$ -- is given by
\begin{align*}
M(T)=p_{M(T_1)}\cdot p_{M(T_2)}\cdot \ldots \cdot p_{M(T_r)}\,.
\end{align*}
For example, consider the rooted tree $T$ shown in Figure~\ref{rootedTree}; $T$ has three branches $T_1,T_2,T_3$. We have
\begin{align*}
M(T_1)&=p_{M(K_1)}=p_1=2,~M(T_2)=p_{M(K_1)}\cdot p_{M(K_1)}=p_1^2=4,\\
M(T_3)&=M(K_1)=1\,,
\end{align*}
from which
\begin{align*}
M(T)=p_{M(T_1)}\cdot p_{M(T_2)} \cdot p_{M(T_3)}=p_2\cdot p_4 \cdot p_1=42
\end{align*}
is obtained.
\begin{figure}[htbp]\centering
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm, scale=1.2]
\draw [line width=1.pt] (7.,10.)-- (4.,8.);
\draw [line width=1.pt] (4.,8.)-- (4.,6.);
\draw [line width=1.pt] (7.,10.)-- (7.,8.);
\draw [line width=1.pt] (7.,8.)-- (6.,7.);
\draw [line width=1.pt] (7.,8.)-- (8.,7.);
\draw [line width=1.pt] (7.,10.)-- (9.926,6.996);
\draw [rotate around={-89.3969088056204:(4.011,6.955)},dash pattern=on 5pt off 5pt] (4.011,6.955) ellipse (1.262574606562399cm and 0.7084833358210949cm);
\draw [rotate around={-88.69804732740158:(6.967,7.128)},dash pattern=on 5pt off 5pt] (6.967,7.128) ellipse (1.3821850905018496cm and 1.2946268282426416cm);
\draw [rotate around={90.:(9.904,6.765)},dash pattern=on 5pt off 5pt] (9.904,6.765) ellipse (0.7069289531052008cm and 0.4574139752329399cm);
\draw (3.282,7.414) node[anchor=north west] {$T_1$};
\draw (6.626,7.172) node[anchor=north west] {$T_2$};
\draw (9.618,6.93) node[anchor=north west] {$T_3$};
\begin{scriptsize}
\draw [fill=black] (4.,8.) circle (2.0pt);
\draw [fill=black] (4.,6.) circle (2.0pt);
\draw [fill=black] (7.,8.) circle (2.0pt);
\draw [fill=black] (6.,7.) circle (2.0pt);
\draw [fill=black] (8.,7.) circle (2.0pt);
\draw [fill=black] (9.926,6.996) circle (2.0pt);
\draw [fill=black] (7.,10.) circle (3.0pt);
\end{scriptsize}
\end{tikzpicture}
\caption{A rooted tree $T$ with three branches $T_1,T_2,T_3$.}\label{rootedTree}
\end{figure}

The definition of Matula numbers also suggests that for every positive integer $n$, there is a unique rooted tree $T$ whose Matula number is $n$. This observation follows by induction on $n$. Indeed, if $n>1$, then write $n$ in its (unique) prime decomposition, say $n=t_1\cdot t_2\cdot \ldots \cdot t_l$, where $t_1,t_2,\ldots,t_l$ are all primes (not necessarily distinct!). Let $m_i$ be the unique positive integer such that $t_i=p_{m_i}$; form a rooted tree $T$ by joining the roots of the trees with Matula numbers $m_1,m_2,\ldots,m_l$ to a new common vertex (the root of $T$). The Matula number of this tree is $n$. Hence, there is a bijection between the set of all rooted trees and the set of all positive integers.

\medskip
As mentioned by Ivan Gutman and Aleksandar Ivi{\'c} in their 1994 paper~\cite{gutman1994graphs}, at the time when the bijection was found by Matula, the mathematics community had considered this discovery as `just' a curiosity driven observation. One had to wait until two decades later when the American chemist Seymour Elk proved in subsequent papers~\cite{elk1995expansion,elk1994further,elk1990problem,elk1989problem} that Matula numbers can be useful for canonical nomenclatures of alkanes and all potential combinations of polybenzene or polymantane modules. In 1992, Gutman, Ivi{\'c} and Elk~\cite{IvanElk1192} obtained further results on how the molecular structures of certain organic compounds can be encoded by means of Matula numbers.

Since the Matula number also appears to be a natural (rooted) tree invariant, Gutman and Yeh listed in their 1993 paper~\cite{gutman1993deducing} ten different parameters (such as the number of vertices, number of leaves, minimum vertex degree, maximum vertex degree, diameter, etc.) of a rooted tree that can be obtained directly from the associated Matula number. Three years later, Gutman and Ivi{\'c}~\cite{gutman1996matula} proved that for $n\geq 5$, the rooted tree obtained by taking a root path (rooted at one of its endvertices) on $n-3$ vertices and attaching three leaves to the other endvertex of the path, is the one that has the maximum Matula number over the set of all rooted trees with $n$ vertices. For the minimum, they showed that for $n\geq 3$ and depending on the residue of $n$ modulo $3$, the rooted tree depicted in Figure~\ref{minVert} is minimal among all $n$-vertex rooted trees.
\begin{figure}[htbp]\centering
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm, scale=0.45]
\draw [line width=1.pt] (4.,10.)-- (3.,9.);
\draw [line width=1.pt] (3.,9.)-- (2.,8.);
\draw [line width=1.pt] (2.,8.)-- (1.,7.);
\draw [line width=1.pt] (4.,10.)-- (5.,9.);
\draw [line width=1.pt] (5.,9.)-- (6.,8.);
\draw [line width=1.pt] (6.,8.)-- (7.,7.);
\draw (0.4498945454545462,6.571049090909086) node[anchor=north west] {$1$};
\draw (5.495349090909093,6.4255945454545405) node[anchor=north west] {$\frac{n}{3} -1$};
\draw [line width=1.pt] (12.,10.)-- (11.,9.);
\draw [line width=1.pt] (11.,9.)-- (10.,8.);
\draw [line width=1.pt] (10.,8.)-- (9.,7.);
\draw [line width=1.pt] (12.,10.)-- (13.,9.);
\draw [line width=1.pt] (13.,9.)-- (14.,8.);
\draw [line width=1.pt] (14.,8.)-- (15.,7.);
\draw (8.54080363636364,6.352867272727267) node[anchor=north west] {$1$};
\draw (13.913530909090915,6.398321818181813) node[anchor=north west] {$\frac{n-1}{3}$};
\draw [line width=1.pt] (4.,10.)-- (3.,10.);
\draw [line width=1.pt] (3.,10.)-- (2.,10.);
\draw [line width=1.pt] (20.,10.)-- (19.,9.);
\draw [line width=1.pt] (19.,9.)-- (18.,8.);
\draw [line width=1.pt] (18.,8.)-- (17.,7.);
\draw [line width=1.pt] (20.,10.)-- (21.,9.);
\draw [line width=1.pt] (21.,9.)-- (22.,8.);
\draw [line width=1.pt] (22.,8.)-- (23.,7.);
\draw (20.958985454545464,6.343776363636359) node[anchor=north west] {$\frac{n-2}{3}-1$};
\draw [line width=1.pt] (20.,10.)-- (19.,10.);
\draw [line width=1.pt] (19.,10.)-- (18.,10.);
\draw [line width=1.pt] (20.,10.)-- (21.,10.);
\draw (16.66807636363637,6.33468545454545) node[anchor=north west] {$1$};
\draw [line width=1.pt] (21.,10.)-- (22.,10.);

\draw [fill=black] (4.,10.) ++(-4.5pt,0 pt) -- ++(4.5pt,4.5pt)--++(4.5pt,-4.5pt)--++(-4.5pt,-4.5pt)--++(-4.5pt,4.5pt);
\draw [fill=black] (3.,9.) circle (2.5pt);
\draw [fill=black] (2.,8.) circle (2.5pt);
\draw [fill=black] (1.,7.) circle (2.5pt);
\draw [fill=black] (5.,9.) circle (2.5pt);
\draw [fill=black] (6.,8.) circle (2.5pt);
\draw [fill=black] (7.,7.) circle (2.5pt);
\draw [fill=black] (4.,7.) circle (1.pt);
\draw [fill=black] (3.42,7.) circle (1.pt);
\draw [fill=black] (4.52,7.02) circle (1.pt);
\draw [fill=black] (12.,10.) ++(-4.5pt,0 pt) -- ++(4.5pt,4.5pt)--++(4.5pt,-4.5pt)--++(-4.5pt,-4.5pt)--++(-4.5pt,4.5pt);
\draw [fill=black] (11.,9.) circle (2.5pt);
\draw [fill=black] (10.,8.) circle (2.5pt);
\draw [fill=black] (9.,7.) circle (2.5pt);
\draw [fill=black] (13.,9.) circle (2.5pt);
\draw [fill=black] (14.,8.) circle (2.5pt);
\draw [fill=black] (15.,7.) circle (2.5pt);
\draw [fill=black] (12.,7.) circle (1.pt);
\draw [fill=black] (11.42,7.) circle (1.pt);
\draw [fill=black] (12.52,7.02) circle (1.pt);
\draw [fill=black] (3.,10.) circle (2.5pt);
\draw [fill=black] (2.,10.) circle (2.5pt);
\draw [fill=black] (20.,10.) ++(-4.5pt,0 pt) -- ++(4.5pt,4.5pt)--++(4.5pt,-4.5pt)--++(-4.5pt,-4.5pt)--++(-4.5pt,4.5pt);
\draw [fill=black] (19.,9.) circle (2.5pt);
\draw [fill=black] (18.,8.) circle (2.5pt);
\draw [fill=black] (17.,7.) circle (2.5pt);
\draw [fill=black] (21.,9.) circle (2.5pt);
\draw [fill=black] (22.,8.) circle (2.5pt);
\draw [fill=black] (23.,7.) circle (2.5pt);
\draw [fill=black] (20.,7.) circle (1.pt);
\draw [fill=black] (19.42,7.) circle (1.pt);
\draw [fill=black] (20.52,7.02) circle (1.pt);
\draw [fill=black] (19.,10.) circle (2.5pt);
\draw [fill=black] (18.,10.) circle (2.5pt);
\draw [fill=black] (21.,10.) circle (2.5pt);
\draw [fill=black] (22.,10.) circle (2.5pt);
\end{tikzpicture}
\caption{The minimal trees among all $n$-vertex rooted trees according to the residue of $n$ modulo $3$ (the root is the square vertex on top)~\cite{gutman1996matula}.}\label{minVert}
\end{figure}

In 2012, Deutsch~\cite{deutsch2012rooted} showed how to determine further properties (mostly distance- and degree-based) of a rooted tree directly from the corresponding Matula number. As such, we have the path length, number of subtrees, Wiener index, terminal Wiener index, Wiener polynomial, first Zagreb index, second Zagreb index, just to mention a few.

In this short note, we are concerned with the Matula extremal trees (and thus the Matula extreme numbers) among the so-called topological trees, given the number of leaves.

In~\cite{bergeron1998combinatorial} a topological tree is defined as a tree without vertices of degree $2$. In this note (see also~\cite{DossouOloryWagnerPaper2}), a rooted tree will be called a \textit{topological} tree if it does not have a vertex of outdegree $1$. The purpose of avoiding vertices of outdegree $1$ in the tree is rather natural: we are collecting trees according to the number of leaves, and there are infinitely many trees with the same number of leaves (e.g. all paths; more generally, one can subdivide any set of edges in a given tree).

We mention that trees without vertices of degree $2$ (also known as \emph{series-reduced} or \emph{homeomorphically irreducible} trees) have already been object of study in the past by mathematicians and theoretical biologists; see e.g. Jamison~\cite{jamison1983average}, Bergeron et al.~\cite{bergeron1998combinatorial}, Allman and Rhodes~\cite{allman2004mathematical}, or the sequence~\url{A000669} in~\cite{oeis}.

\section{Getting to the extremal trees}\label{Towards}
Let us first give more definitions.
\begin{itemize}
\item A \textit{binary} tree is a rooted tree in which every vertex has outdegree exactly $0$ or $2$;
\item A \textit{star} is a rooted tree in which all leaves are adjacent to the root (see Figure~\ref{binaAndStars});
\item A binary \textit{caterpillar} is a binary tree whose internal vertices lie on a single path starting at the root (see Figure~\ref{binaAndStars}).
\end{itemize}
We denote the star with $n$ leaves by $K_{1,n}$ and the $n$-leaf binary caterpillar by $F_n$. We shall prove that the star $K_{1,n}$ minimises the Matula number and the binary caterpillar $F_n$ maximises the Matula number over all topological trees with $n$ leaves. We also derive the extreme values, i.e. an expression for both $M(K_{1,n})$ and $M(F_n)$.

\begin{figure}[htbp]\centering

\begin{tikzpicture}
\draw [fill=black] (6,0) circle (2.5 pt);

\draw [fill=black] (5.5,-0.5) circle (1.5 pt);
\draw [fill=black] (6.5,-0.5) circle (1.5 pt);

\draw [fill=black] (6,-1) circle (1.5 pt);
\draw [fill=black] (7,-1) circle (1.5 pt);

\draw [fill=black] (6.5,-1.5) circle (1.5 pt);
\draw [fill=black] (7.5,-1.5) circle (1.5 pt);

\draw [fill=black] (7,-2) circle (1.5 pt);
\draw [fill=black] (8,-2) circle (1.5 pt);

\draw [line width=1pt] (6,0) -- (5.5,-0.5);
\draw [line width=1pt] (6,0) -- (6.5,-0.5);

\draw [line width=1pt] (6.5,-0.5)  -- (6,-1);
\draw [line width=1pt] (6.5,-0.5)  -- (7,-1);

\draw [line width=1pt] (7,-1)  -- (6.5,-1.5);
\draw [line width=1pt] (7,-1)  -- (7.5,-1.5);

\draw [line width=1pt] (7.5,-1.5)  -- (7,-2);
\draw [line width=1pt] (7.5,-1.5)  -- (8,-2);

\draw [fill=black] (12,0) circle (2.5 pt);

\draw [fill=black] (11.5,-2) circle (1.5 pt);
\draw [fill=black] (11,-2) circle (1.5 pt);
\draw [fill=black] (10.5,-2) circle (1.5 pt);

\draw [fill=black] (12.5,-2) circle (1.5 pt);
\draw [fill=black] (13,-2) circle (1.5 pt);
\draw [fill=black] (13.5,-2) circle (1.5 pt);

\draw [line width=1pt] (12,0) -- (11.5,-2);
\draw [line width=1pt] (12,0) -- (11.,-2);
\draw [line width=1pt] (12,0) -- (10.5,-2);

\draw [line width=1pt] (12,0) -- (12.5,-2);
\draw [line width=1pt] (12,0) -- (13.,-2);
\draw [line width=1pt] (12,0) -- (13.5,-2);
\end{tikzpicture}
\caption{The binary caterpillar $F_5$ with five leaves (left), and the star $K_{1,6}$ with six leaves (right).} \label{binaAndStars}

\end{figure}

Note the following observation, which is analogous to a transformation used by the authors of~\cite{gutman1996matula} in their context of trees with a given number of vertices. Let us be given two arbitrary topological trees $T_1$ and $T_2$. Denote by $S_{1,2}$ the topological tree with the two branches $T_1$ and $T_2$. Then we have
\begin{align*}
p_{M(T_1)} \cdot p_{M(T_2)} < p_{M(S_{1,2})}\,.
\end{align*}
To see this, simply note that $M(S_{1,2})=p_{M(T_1)} \cdot p_{M(T_2)}$ by definition, and thus
\begin{align*}
p_{M(S_{1,2})}=p_{p_{M(T_1)} \cdot p_{M(T_2)}} > p_{M(T_1)} \cdot p_{M(T_2)}
\end{align*}
as $p_m$ (the $m$-th prime number) is greater than $m$ for all $m$.

Let $T$ be a topological tree with branches $T_1,T_2,\ldots,T_r$ such that $r\geq 3$. Again, denote by $S_{1,2}$ the topological tree whose branches are $T_1$ and $T_2$. Further, denote by $F(T)$ the rooted tree whose branches are $S_{1,2},T_3,\ldots,T_r$; see Figure~\ref{FAndFT} for a picture. Obviously, $T$ and $F(T)$ have the same number of leaves.

\begin{figure}[htbp]\centering
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm, scale=0.7]
	\draw (4.4,3.32) node[anchor=north west] {$S_{1,2}$};
	\draw [line width=1.2pt] (5,11)-- (8.98,14.02);
	\draw [line width=1.2pt] (8.98,14.02)-- (6.98,11.02);
	\draw [line width=1.2pt] (8.98,14.02)-- (9.48,11.06);
	\draw [line width=1.2pt] (8.98,14.02)-- (14.42,11.04);
	\draw (3.76,10.36) node[anchor=north west] {$T_1$};
	\draw (5.77,10.34) node[anchor=north west] {$T_2$};
	\draw (8.35,10.32) node[anchor=north west] {$T_3$};
	\draw (13.3,10.28) node[anchor=north west] {$T_r$};
	\draw [rotate around={89.2:(4.99,10.28)},fill=black,fill opacity=0.25] (4.99,10.28) ellipse (0.8cm and 0.35cm);
	\draw [rotate around={89.22:(6.97,10.29)},fill=black,fill opacity=0.25] (6.97,10.29) ellipse (0.8cm and 0.32cm);
	\draw [rotate around={88.53:(9.46,10.28)},fill=black,fill opacity=0.25] (9.46,10.28) ellipse (0.85cm and 0.33cm);
	\draw [rotate around={87.61:(14.39,10.32)},fill=black,fill opacity=0.25] (14.39,10.32) ellipse (0.78cm and 0.31cm);
	\draw [line width=1.2pt] (5,4)-- (9,6);
	\draw [line width=1.2pt] (9,6)-- (9,3);
	\draw [line width=1.2pt] (9,6)-- (13,3);

	\draw (2.86,2.18) node[anchor=north west] {$T_1$};
	\draw (4.96,2.08) node[anchor=north west] {$T_2$};
	\draw (7.9,2.1) node[anchor=north west] {$T_3$};
	\draw (11.85,2.14) node[anchor=north west] {$T_r$};
	\draw [rotate around={87.74:(3.97,2.24)},fill=black,fill opacity=0.25] (3.97,2.24) ellipse (0.84cm and 0.35cm);
	\draw [rotate around={89.24:(5.99,2.25)},fill=black,fill opacity=0.25] (5.99,2.25) ellipse (0.82cm and 0.34cm);
	\draw [line width=1.2pt] (4,3)-- (5,4);
	\draw [line width=1.2pt] (5,4)-- (6,3);
	\draw [rotate around={89.27:(8.99,2.21)},fill=black,fill opacity=0.25] (8.99,2.21) ellipse (0.86cm and 0.35cm);
	\draw [rotate around={89.23:(12.99,2.26)},fill=black,fill opacity=0.25] (12.99,2.26) ellipse (0.83cm and 0.37cm);
	\draw [rotate around={0:(5,2.52)},line width=1.pt,dash pattern=on 5pt off 5pt] (5,2.52) ellipse (2.68cm and 1.77cm);

	\fill [color=black] (5,11) circle (1.5pt);
	\fill [color=black] (6.98,11.02) circle (1.5pt);
	\fill [color=black] (9.48,11.06) circle (1.5pt);
	\fill [color=black] (14.42,11.04) circle (1.5pt);
	\fill [color=black] (8.98,14.02) circle (3.0pt);
	\fill [color=black] (11.48,11.04) circle (1pt);
	\fill [color=black] (11.98,11.02) circle (1pt);
	\fill [color=black] (12.42,11.04) circle (1pt);
	\fill [color=black] (5,4) circle (1.5pt);
	\fill [color=black] (4,3) circle (1.5pt);
	\fill [color=black] (9,3) circle (1.5pt);
	\fill [color=black] (13,3) circle (1.5pt);
	\fill [color=black] (9,6) circle (3.0pt);
	\fill [color=black] (10.56,3) circle (1pt);
	\fill [color=black] (11,3) circle (1pt);
	\fill [color=black] (11.42,3.02) circle (1pt);
	\fill [color=black] (6,3) circle (1.5pt);
	\end{tikzpicture}
\caption{Illustration of the tree transformation $F$: A topological tree $T$ (top figure) and the corresponding tree $F(T)$ (bottom figure).}\label{FAndFT}
\end{figure}

Then it follows immediately from the previous observation and the definition of the Matula number that
\begin{align*}
M(F(T)) > M(T)\,.
\end{align*}
Consequently, by repeatedly applying the tree transformation $F$, we then obtain from $T$ a new topological tree, say $T^{\prime}$ with exactly two branches and having the property that $M(T^{\prime}) > M(T)$. In the same way, repeated application of the same tree transformation $F$ to the branches of $T^{\prime}$ yields a binary tree.

Hence, the tree that has the maximum Matula number among all topological trees with a prescribed number of leaves must be a binary tree. On the other hand, it also follows from our discussion that the tree that minimises the Matula number among all topological trees with $n\geq 2$ leaves must have $n$ branches. We have then proved the following theorem:

\begin{theorem}
The star $K_{1,n}$ (consisting of a root with $n$ leaves attached to it) is the topological tree that has the smallest Matula number among all $n$-leaf topological trees. Moreover, $M(K_{1,n})=2^n$ for all $n>1$.
\end{theorem}

\section{Finding the maximal topological tree}

We begin with a lemma:

\begin{lemma}\label{lemforqk}
Let the sequence $(q_k)_{k\geq 1}$ of positive integers be defined recursively by
\begin{align*}
q_1=1~\text{and}~ q_k=2 p_{q_{k-1}}~\text{for}~k>1\,.
\end{align*}
Then we have
\begin{align*}
p_{q_{k_1}} \cdot p_{q_{k_2}} \leq q_{k_1+k_2}
\end{align*}
for all pairs $(k_1,k_2)$ of positive integers.
\end{lemma}

The first few values of the sequence $(q_k)_{k\geq 1}$ are
\begin{align*}
&q_1=1,~q_2=2p_1=4,~q_3=2p_4=14,~q_4=2p_{14}=86,~q_5=2p_{86}=886,\\
&q_6=2p_{886}=13766
\end{align*}
since $p_{14}=43,~p_{86}=443$ and $p_{886}=6883$.

\medskip
To prove the lemma, we shall need the following two theorems concerning primes:

\begin{theorem}[Robin~\cite{robin1983estimation}]\label{Robin}
For any integer $m\geq 2$, we have
\begin{align*}
p_m \geq m \big(\ln(m)+\ln(\ln(m)) -1.0072629\big)\,.
\end{align*}
\end{theorem}

\begin{theorem}[Rosser-Schoenfeld~\cite{rosser1962approximate}]\label{RosSchoen}
For any integer $m\geq 20$, we have
\begin{align*}
p_m \leq m \big(\ln(m)+\ln(\ln(m)) -0.5\big)\,.
\end{align*}
\end{theorem}

\begin{proof}[Proof of Lemma~\ref{lemforqk}]
We may assume that $k_1 \leq k_2$. Set $k=k_1+k_2$. For $k=2$, we have $k_1=k_2=1$ and $p_{q_{k_1}} \cdot p_{q_{k_2}}=p_{q_1}^2=p_1^2=4=2p_1=2p_{q_1}=q_2=q_{k_1+k_2}$. For $k=3$, we have $k_1=1,~k_2=2$ and $p_{q_{k_1}} \cdot p_{q_{k_2}}=p_{q_1} \cdot p_{q_2}=p_1\cdot p_4=14=2p_4=2p_{q_2}=q_3=q_{k_1+k_2}$. So the inequality holds for $k\in\{2,3\}$. In fact, for $k\leq 6$, the inequality is easily verified; see Table~\ref{valk6} and the values of $q_1,\ldots,q_6$ given above. We then assume that $k>6$ and continue the proof of the inequality by induction on $k$.
\begin{table}[htbp]\centering
\caption{$k_1+k_2\in \{4,5, 6\}$}\label{valk6}
\begin{tabular}{c|c|c||c|c||c|c|c}
$(k_1,k_2)$                     & (1,3) & (2,2) & (1,4) & (2,3) & (1,5) & (2,4) & (3,3) \\ \hline
$p_{q_{k_1}} \cdot p_{q_{k_2}}$ & 86    & 49    & 886   & 301   & 13766 & 3101  & 1849 \\ \hline
\end{tabular}
\end{table}

Let $k_1,k_2$ be two arbitrary positive integers such that $k_1\leq k_2$ and $k_1+k_2=k$. We may assume that $k_1\geq 2$ because for $k_1=1$, the lemma clearly holds with equality. We may also assume that $k_2\geq 4$ because $k>6$ by assumption.

Now note that $p_{q_{k_1}}\geq 4$ (since $k_1\geq 2$ implies that $q_{k_1}\geq 4$) and thus
\begin{align*}
\ln (p_{q_{k_1}}\cdot p_{q_{k_2-1}})&+\ln(\ln (p_{q_{k_1}}\cdot p_{q_{k_2-1}}))-1.0072629\\
&\geq \ln(2)+\ln (2 p_{q_{k_2-1}})+\ln(\ln (2 p_{q_{k_2-1}}))-1.0072629\\
& \geq \ln (2 p_{q_{k_2-1}})+\ln(\ln (2 p_{q_{k_2-1}}))-0.5\\
&=\ln (q_{k_2})+\ln(\ln (q_{k_2}))-0.5
\end{align*}
since $\ln(2)- 1.0072629=-0.314116\ldots$. Thus, we have
\begin{align*}
2p_{q_{k_2-1}}&\Big( \ln (p_{q_{k_1}}\cdot p_{q_{k_2-1}})+\ln(\ln (p_{q_{k_1}}\cdot p_{q_{k_2-1}}))-1.0072629\Big)\\
&\geq q_{k_2} \Big( \ln (q_{k_2})+\ln(\ln (q_{k_2}))-0.5\Big)\\
& \geq p_{q_{k_2}}\,,
\end{align*}
where the inequality in the last step follows from Theorem~\ref{RosSchoen} since $k_2\geq 4$ implies that $q_{k_2}\geq 20$.

It follows that
\begin{align*}
2p_{q_{k_1}} \cdot p_{q_{k_2-1}} \Big( \ln (p_{q_{k_1}}\cdot p_{q_{k_2-1}})&+\ln(\ln (p_{q_{k_1}}\cdot p_{q_{k_2-1}}))-1.0072629\Big)\\
& \geq p_{q_{k_1}} \cdot p_{q_{k_2}}\,,
\end{align*}
so that Theorem~\ref{Robin} together with the induction hypothesis gives us
\begin{align*}
q_k=2p_{q_{k-1}}&\geq 2 q_{k-1} \Big( \ln (q_{k-1})+\ln(\ln (q_{k-1}))-1.0072629\Big)\\
&\geq 2 p_{q_{k_1}} \cdot p_{q_{k_2-1}} \\
& \hspace*{1cm} \Big( \ln (p_{q_{k_1}} \cdot p_{q_{k_2-1}})+\ln(\ln (p_{q_{k_1}} \cdot p_{q_{k_2-1}}))-1.0072629\Big)\\
&\geq  p_{q_{k_1}} \cdot p_{q_{k_2}}
\end{align*}
since $k_1+k_2=k$ and $k> 6$ implies that $q_{k-1} \geq 2$. Therefore, we obtain
\begin{align*}
q_k=q_{k_1+k_2}\geq p_{q_{k_1}} \cdot p_{q_{k_2}}
\end{align*}
for all pairs $(k_1,k_2)$ of positive integers. This completes the induction step as well as the proof of the lemma.
\end{proof}

We can now state and prove our next theorem:

\begin{theorem}
Among all topological trees with $n$ leaves, the binary caterpillar $F_n$ has the greatest Matula number. Furthermore, $M(F_n)=q_n$, where $q_n$ is the positive integer defined in Lemma~\ref{lemforqk}.
\end{theorem}

\begin{proof}
First of all, note that for $k>1$, we have $M(F_k)=p_1 \cdot p_{M(F_{k-1})}$ and by iteration on $k$, we obtain $M(F_k)=q_k$ for every $k$.

It is shown in Section~\ref{Towards} that the tree that maximises the Matula number among all topological trees with a prescribed number of leaves must be a binary tree. Now, let us use induction on $k$ to prove that $M(B)\leq M(F_k)$ for every binary tree $B$ with $k$ leaves.

The statement of the theorem is trivial for $k\leq 3$ since in this case, there is only one possibility for the shape of the binary tree. Assume that the statement holds for all binary trees with at most $k-1 \geq 3$ leaves and consider a binary tree $B$ with $k$ leaves. Denote by $B_1$ and $B_2$ the two branches of $B$. Since $M(B)=p_{M(B_1)}\cdot p_{M(B_2)}$, we obtain $M(B)\leq p_{M(F_{|B_1|})}\cdot p_{M(F_{|B_2|})}$ by the induction hypothesis. Consequently, invoking Lemma~\ref{lemforqk}, one obtains
\begin{align*}
M(B)\leq p_{M(F_{|B_1|})}\cdot p_{M(F_{|B_2|})} \leq M(F_{|B|})
\end{align*}
since $M(F_k)=q_k$. The theorem follows.
\end{proof}

\section{Conclusion}
The fact that the binary caterpillar $F_n$ is maximal in the set of all $n$-leaf topological trees with respect to the Matula number, also shows that $F_n$ is maximal in the set of all $n$-leaf binary trees with respect to the Matula number. Probably, the next natural problem for a future study will be to characterise the tree that minimises the Matula number over all binary trees (rooted trees in which every vertex has outdegree exactly $0$ or $2$) with a given number of leaves.

Given a positive integer $k>1$, let $s$ be the unique nonnegative integer satisfying $2^{s+1}\leq k < 2^{s+2}$. Then write $k=r+2^{1+s}$ with $r$ the residue of $k$ modulo $2^{1+s}$. Define the sequence $(l_k)_{k\geq 1}$ of positive integers recursively by
\begin{align*}
l_k=l_{r+2^{1+s}}=\left\{
\begin{array}{rcl}
p_{l_{2^s}}\cdot p_{l_{r+2^s}}& \mbox{if} & r\leq 2^s \\
p_{l_r}\cdot p_{l_{2^{1+s}}} & \mbox{if} & r > 2^s\,,
\end{array}\right.
\end{align*}
starting with $l_1=1$. The sequence begins
\begin{align*}
1,4,14,49,301,1589,9761,51529,452411,3041573, 23140153,\ldots\,.
\end{align*}

Calculations suggest that $M(B)\geq l_k$ for every binary tree $B$ with $k\leq 18$ leaves. The $k$-leaf minimal binary tree $S_k$ in this case is also obtained in the same recursive way: the branches of $S_k=S_{r+2^{1+s}}$ are the binary trees $S_{2^s}$ and $S_{r+2^s}$ if $r\leq 2^s$, and the binary trees $S_r$ and $S_{2^{1+s}}$ if $ r > 2^s$, the starting tree being the tree $K_1$. For example, we show in Figure~\ref{MinBin} the minimal binary trees $S_6$ and $S_{13}$.
\begin{figure}[!h]\centering
\begin{subfigure}[b]{0.5\textwidth} \centering
	\begin{tikzpicture}
	\draw [fill=black] (0,0) circle (2.5 pt);
	\draw [fill=black] (-1,-1) circle (1.5 pt);
	\draw [fill=black] (1,-1) circle (1.5 pt);

    \draw [fill=black] (-1.5,-2) circle (1.5 pt);
    \draw [fill=black] (-0.5,-2) circle (1.5 pt);

	\draw [fill=black] (0.5,-2) circle (1.5 pt);
	\draw [fill=black] (1.5,-2) circle (1.5 pt);

	\draw [fill=black] (0.2,-2.5) circle (1.5 pt);
	\draw [fill=black] (0.8,-2.5) circle (1.5 pt);

	\draw [fill=black] (1.2,-2.5) circle (1.5 pt);
	\draw [fill=black] (1.8,-2.5) circle (1.5 pt);

	\draw [line width=1pt] (0,0) -- (-1,-1);
	\draw [line width=1pt] (0,0) -- (1,-1);

	\draw [line width=1pt] (-1,-1) -- (-1.5,-2);
	\draw [line width=1pt] (-1,-1)-- (-0.5,-2);

	\draw [line width=1pt] (1,-1) -- (0.5,-2);
	\draw [line width=1pt] (1,-1)-- (1.5,-2);

	\draw [line width=1pt] (0.5,-2) -- (0.2,-2.5);
	\draw [line width=1pt] (0.5,-2)-- (0.8,-2.5);

	\draw [line width=1pt] (1.5,-2) -- (1.2,-2.5);
	\draw [line width=1pt] (1.5,-2)-- (1.8,-2.5);
\end{tikzpicture}
\caption{$S_6$}
\end{subfigure} \vspace*{1cm}

\begin{subfigure}[b]{1\textwidth} \centering
\begin{tikzpicture}[scale=0.85]
\draw [fill=black] (0,0) circle (2.5 pt);
\draw [fill=black] (-3,-1) circle (1.5 pt);
\draw [fill=black] (3,-1) circle (1.5 pt);
\draw [line width=1pt] (0,0) -- (-3,-1);
\draw [line width=1pt] (0,0) -- (3,-1);

\draw [fill=black] (-5,-2) circle (1.5 pt);
\draw [fill=black] (-1,-2) circle (1.5 pt);
\draw [line width=1pt] (-3,-1) -- (-5,-2);
\draw [line width=1pt] (-3,-1) -- (-1,-2);

\draw [fill=black] (1,-2) circle (1.5 pt);
\draw [fill=black] (5,-2) circle (1.5 pt);
\draw [line width=1pt] (3,-1) -- (1,-2);
\draw [line width=1pt] (3,-1) -- (5,-2);

\draw [fill=black] (-5.8,-3) circle (1.5 pt);
\draw [fill=black] (-4.2,-3) circle (1.5 pt);
\draw [line width=1pt] (-5,-2) -- (-5.8,-3);
\draw [line width=1pt] (-5,-2) -- (-4.2,-3);

\draw [fill=black] (-1.8,-3) circle (1.5 pt);
\draw [fill=black] (-0.2,-3) circle (1.5 pt);
\draw [line width=1pt] (-1,-2) -- (-1.8,-3);
\draw [line width=1pt] (-1,-2) -- (-0.2,-3);

\draw [fill=black] (0.2,-3) circle (1.5 pt);
\draw [fill=black] (1.8,-3) circle (1.5 pt);
\draw [line width=1pt] (1,-2) -- (0.2,-3);
\draw [line width=1pt] (1,-2) -- (1.8,-3);

\draw [fill=black] (4.2,-3) circle (1.5 pt);
\draw [fill=black] (5.8,-3) circle (1.5 pt);
\draw [line width=1pt] (5,-2) -- (4.2,-3);
\draw [line width=1pt] (5,-2) -- (5.8,-3);

\draw [fill=black] (-6.3,-4) circle (1.5 pt);
\draw [fill=black] (-5.3,-4) circle (1.5 pt);
\draw [line width=1pt] (-5.8,-3) -- (-6.3,-4);
\draw [line width=1pt] (-5.8,-3) -- (-5.3,-4);

\draw [fill=black] (-4.7,-4) circle (1.5 pt);
\draw [fill=black] (-3.7,-4) circle (1.5 pt);
\draw [line width=1pt] (-4.2,-3) -- (-4.7,-4);
\draw [line width=1pt] (-4.2,-3) -- (-3.7,-4);

\draw [fill=black] (-2.3,-4) circle (1.5 pt);
\draw [fill=black] (-1.3,-4) circle (1.5 pt);
\draw [line width=1pt] (-1.8,-3) -- (-2.3,-4);
\draw [line width=1pt] (-1.8,-3) -- (-1.3,-4);

\draw [fill=black] (-0.7,-4) circle (1.5 pt);
\draw [fill=black] (0.3,-4) circle (1.5 pt);
\draw [line width=1pt] (-0.2,-3) -- (-0.7,-4);
\draw [line width=1pt] (-0.2,-3) -- (0.3,-4);

\draw [fill=black] (1.3,-4) circle (1.5 pt);
\draw [fill=black] (2.3,-4) circle (1.5 pt);
\draw [line width=1pt] (1.8,-3) -- (1.3,-4);
\draw [line width=1pt] (1.8,-3) -- (2.3,-4);
\end{tikzpicture}
\caption{$S_{13}$}
\end{subfigure}

\caption{The minimal binary trees $S_6$ and $S_{13}$.}\label{MinBin}
\end{figure}

Note that the numbers $l_k$ soon get really large; for instance, the Matula number of $S_{18}$ is $32078140605053$. So it is difficult to check our evidence for more values of $k$; although
\begin{align*}
1.07555\times 10^{15} \leq p_{32078140605053} \leq 1.09182\times 10^{15}\,,
\end{align*}
a `standard' computer already fails to produce the prime number $$p_{32078140605053}.$$

On the other hand, since ``weak'' binary trees (every vertex has degree at most $3$) are more realistic molecular graphs, the problem of finding the extremal tree structures among these trees, given the number of vertices, may also be of interest. Recall that for the more general case of rooted trees, the problem has already been solved by Gutman and Ivi{\'c}~\cite{gutman1996matula}.

\section{Acknowledgements}
The author was supported by Stellenbosch University in association with the African Institute for Mathematical Sciences (AIMS) South Africa.


TITLE: Help me understand the tensor product
QUESTION [8 upvotes]: I have several books and other literature that define the tensor product, but I understand none of them. Since this really concerns one topic, namely understanding the construction of and arithmetic of (with?) tensor products, I'll pose a few questions here instead of asking them separately. I don't feel that the specific case of tensoring vector spaces helps with understanding the general construction, so my questions will deal with tensoring a right $R$-module with a left $R$-module over the ring $R$, which we do not assume to be commutative.
1) Now then, the first step is to form the free abelian group $F(M \times N)$. I've never stumbled upon free abelian groups prior to reading about the tensor product, but it seems simple enough. Correct me if I'm wrong, but $F(M \times N) = \{ \sum a_{ij}(m,n) \mid a_{ij} \in \mathbb{Z} \}$, the sums ranging over all $(m,n) \in M \times N$. But some authors say something else, which I trust is the same thing but nevertheless confuses me. Keith Conrad (assuming $R$ is commutative) says $$R=\bigoplus_{(m,n) \in M \times N} R \delta_{(m,n)}$$ without any mention of what $\delta_{(m,n)}$ is, but it's probably similar to what I have in a compendium (which also assumes the ring is commutative), "notation tagging the component that corresponds to the element $(m,n) \in M \times N$". What does that even mean, and why is that particular notation only used when $R$ is assumed commutative?
2) Next define the subgroup $S \subset F(M \times N)$ generated by "all elements of the following three types" $(a,b+b') - (a,b) - (a,b')$ etc. Well, what does $-$ mean? Is an equivalence relation meant? If so, when are they considered equivalent? I've only seen this along the lines of "define $x,y$ to be equivalent if property $P(x,y)$ holds".
3) $M \otimes N$ is an abelian group. Fine, so how are elements "added"? No mention of this is made in any of my literature, except that $a \otimes (b+b') = a \otimes b + a \otimes b'$, but how about $a \otimes b + c \otimes d$?
4) So-called elementary or pure tensors. Conrad writes "Tensors in $M \otimes_R N$ that have the form $m \otimes n$ are called elementary tensors". The elementary tensors span the tensor product (right?), but what elements of $F(M \times N)$ wind up as elementary tensors? While my compendium (which, as Conrad, assumes the ring to be commutative) also makes note of elementary tensors, Rotman ("Introduction to Homological Algebra"), not assuming commutativity, makes no mention of them, but says: "Since $A \otimes_R B$ is generated by the elements of the form $a \otimes b$, every $u \in A \otimes_R B$ has the form $u = \sum_i a_i \otimes b_i$. This expression is not unique..." The other names for "elementary tensor" which Conrad lists are not in the index to Rotman's book, so are elementary tensors only relevant to tensoring over a commutative ring?
Thanks in advance for any help. I've had some homework regarding tensors and I'm unable to take even a first step in answering the questions, so I have to learn tensor products somehow.
Conrad: http://www.math.uconn.edu/~kconrad/blurbs/linmultialg/tensorprod.pdf

REPLY [3 votes]: I'll try to answer your questions as best I can:

You are right about your definition of free abelian group, just use your definition.
The subgroup generated by those elements is precisely the set that consists of sums and inverses of elements of the form $(a,b+b')-(a,b)-(a,b')$, etc. The $-$ that goes with the element $(a,b)$, for example, means the additive inverse of $(a,b)$ in $F(M\times N)$. Since $F(M\times N)$ is abelian, and we take the subgroup generated by the elements above, then said subgroup is normal and so if we break up $F(M\times N)$ into cosets, this gives an equivalence relation on $F(M\times N)$. Explicitly, if $H$ is the subgroup $H=\langle (a,b+b')-(a,b)-(a,b'),\mbox{ etc...}:a,b,b'\in M\times N\rangle$ (the smallest subgroup that contains the elements you defined), then if $x,y\in F(M\times N)$, $x\sim y$ if $x-y\in H$. When we mod out by this equivalence relation (which is the same as taking the quotient $F(M\times N)/H$) we basically declare the elements you defined to be 0.
If there is no obvious relation between $a,b,c,d$, then there is no obvious way to add $a\otimes b+c\otimes d$. It's just left like that, and we see it as an element of the tensor product anyways.
The elementary tensors come from elements of the form $(a,b)\in M\times N\subseteq F(M\times N)$. In the quotient these turn into $a\times b$. The term elementary tensor just means that these are basically the "building blocks" for the tensor product. You are right to say that these generate the tensor product.

A bit of motivation for the tensor product:
If we have the product $M\times N$, we would somehow like a module $T$ such that a bilinear map $\phi:M\times N\to P$ turns into an $R$-module morphism $T\to P$. The problem with $M\times N$ is that if $(m,n),(m',n')\in M\times N$ then
$$\phi((m,n)+(m',n'))=\phi(m+m',n+n')=\phi(m,n+n')+\phi(m',n+n')=\phi(m,n)+\phi(m',n)+\phi(m,n')+\phi(m',n'),$$ which isn't the same as $\phi(m,n)+\phi(m',n')$. The way to fix this is by adding the elements of $M\times N$ a different way and modding out by others. For example, instead of $(m,n)+(m',n')=(m+m',n+n')$, we want $(m,n)+(m',n)"="(m+m',n)$, etc. If we had this then $\phi$ would be a morphism of $R$-modules. The way to get this relation is to declare that $(m,n)+(m',n)-(m+m',n)"="0$, that is, we mod out by the relations you put above. This is how we obtain the tensor product.
Remark The motivation to define tensor product I put above basically characterizes the tensor product (this is the universal property that defines the tensor product).

REPLY [1 votes]: 1) What he means when he writes $F_R(M\times N) = \bigoplus R \delta_{(m,n)}$ is that you're taking a direct sum of as many copies of $R$ as there are elements $(m,n) \in M \times N$. By definition, an element in the direct sum of an infinity of modules is a finite $R$-linear combination of the modules involved (here, they are all copies of $R$), so a generic element in $F_R(M\times N)$ would look like $r_1 \delta_{(m_1,n_1)} + \cdots + r_k \delta_{(m_k,n_k)}$. If you want, you can view such an element as an $R$-valued sequence indexed by $M \times N$ with finitely many non-zero elements.
2) The $-$ is the symbol for the additive inverse in the free module. Thinking in terms of sequences above, the addition is componentwise addition. So what you do is construct the submodule generated by elements of the given form so that you get exactly the bilinearity relations that you want in the quotient module.
3) The tensor product is constructed as a quotient module $F_R(M\times N)/D$, so the operation is the usual coset addition: $(a + D) + (b + D) := (a + b) + D$. If we want to be explicit, like above, we can write $$(r_1 \delta_{(m_1,n_1)} + \cdots + r_k \delta_{(m_k,n_k)} + D) + (r'_1 \delta_{(m'_1,n'_1)} + \cdots + r'_l \delta_{(m'_l,n'_l)} + D) = (r_1 \delta_{(m_1,n_1)} + \cdots + r_k \delta_{(m_k,n_k)} + r'_1 \delta_{(m'_1,n'_1)} + \cdots + r'_l \delta_{(m'_l,n'_l)}) + D.$$
4) The elementary tensors are those which come from the generators $\delta_{(m,n)} \in F_R(M\times N)$. Elements of the form $r \delta_{(m,n)}$ also reduce to elementary tensors in the quotient, because the identifications give $r(m \otimes n) = (rm) \otimes n = m' \otimes n$.

It is okay to struggle with the construction of the tensor product at first, but keep in mind that the construction is not very important; what really matters is the universal property of the tensor product, which in essence states that bilinear mappings $M\times N \rightarrow L$ (or, equivalently, linear mappings $M \rightarrow \operatorname{Hom}(N,L)$) are naturally the same thing as linear mappings $M \otimes N \rightarrow L$.
See also: tensor-hom adjunction.


TITLE: Confused about relating spring force to maximum distance
QUESTION [1 upvotes]: I keep working through this problem and getting the wrong answer:

A spring with spring constant k is positioned vertically and then
  compressed from its equilibrium length by a distance Δy. A ball of
  mass m is placed on top of the spring, and is launched into the air
  when the spring is released. The ball travels to a maximum height
  hmax. Using the Work-Kinetic Energy theorem, determine hmax in terms
  of the given variables and any other constants you deem necessary.

The thought process was ∆K = $K_f - K_i$ = W --> $\frac{mv^2}{2}-\frac{mv_0^2}{2}$ = W
$W$ = $W_s - W_g$ where $W_s$ is a spring and $w_g$ is gravity
The final velocity is also zero so $K_f$ = 0. Which gives us
$\frac{mv_0^2}{2} = -k∆y^2 - mgh_m$ (solve for $h_m$)
$h_m = \frac{-k∆y^2}{2mg}+\frac{v_0^2}{2g}$
I might be completely off but I can't figure out what else to do. I would be very grateful is someone walked me through it

REPLY [4 votes]: We are going to use the fact that the change in an object's kinetic energy is equal to the work done on it by external forces. Initially, the ball is at rest, so its kinetic energy is zero. In the final state, the ball has reached its maximum height so the kinetic energy is zero there as well. Thus the net work done on the ball by external forces must be zero.
There are two forces acting on the object: gravity and the spring force. The spring force acts in the direction of motion, so that it speeds up the object and does work. The amount of work that it does is $W_s = \frac{1}{2} k (\Delta y)^2$. On the other hand gravity acts in the direction opposite to velocity, and so it contributes a negative work. The work due to gravity is $W_g=-mg(h_{max} + \Delta y)$.
For the total work to be zero we must have $W_s = -W_g$ or $\frac{1}{2} k (\Delta y)^2 = mg(h_{max} + \Delta y)$. Solving for $h_{max}$, we find $h_{max} = \frac{k}{2mg}  (\Delta y)^2 - \Delta y = \Delta y (\frac{k \Delta y}{2 m g} -1)$.


TITLE: Show a certain sequence converges
QUESTION [0 upvotes]: Let sequence $(x_n)$ be recursively defined as: $x_1=0, x_2=1, x_{n+2}=\frac{1}{2}(x_{n+1}+x_n)$
What I need to do is show that $ (x_n) $ converges, not necessarily to show that it converges to $\frac{2}{3}$, just prove that it is convergent. I don't quite know how to start this prove, can the convergence tests for series also be used for sequences?

REPLY [0 votes]: You have that
$$|x_{n+2}-x_{n+1}|=\left|\frac{x_{n+1}}{2}+\frac{x_n}{2}-x_{n+1}\right|=\frac{1}{2}|x_{n+1}-x_n|.$$
Using induct|x_{n+k}-x_{n+1}|ion, we get
$$|x_{n+2}-x_{n+1}|=\frac{1}{2^{n+1}}|x_1-x_0|=\frac{1}{2^{n+1}}.$$
Now, for any $k\ge 2,$ it is
$$|x_{n+k}-x_{n+1}|\le \sum_{i=1}^{k-1}|x_{n+i+1}-x_{n+i}|=\sum_{i=1}^{k-1}\frac{1}{2^{n+i}}=\frac{1}{2^n}-\frac{1}{2^{n+k-1}}.$$ This shows that it is a Cauchy sequence and so it must be convergent.


TITLE: What's the value of $x$ in the following equation?
QUESTION [3 upvotes]: So this is how I approached this question, the above equations could be simplified to :
$$a = \frac{4(b+c)}{b+c+4}\tag{1!}$$
$$b = \frac{10(a+c)}{a+c+10}\tag{2}$$
$$c=\frac{56(a+b)}{a+b+56}\tag{3}$$
From above, we can deduce that $4 > a$ since $\frac{(b+c)}{b+c+4} < 1$ similarly $10 > b, 56 > c$  so  $a + b + c < 70$
Let, $$(a + b + c)k = 70\tag4$$
Now let, $$\alpha(b+c) = b+c+4\tag{1'}$$
$$\beta(a+c) = a+c+10\tag{2'}$$
$$\gamma( a+b ) = a+b+56\tag{3'}$$
Now adding the above 3 equations we get :
$$2(a+b+c) + 70 = a(\gamma + \beta) + c(\beta + \alpha) + b(\alpha + \gamma) \rightarrow (2 + k)(a+b+c) = a(\gamma + \beta) + c(\beta + \alpha) + b(\alpha + \gamma)$$
Now from above we see that coefficient of $a,b,c$ must be equal on both sides so, $$(2 + k) = (\alpha + \beta) = (\beta + \gamma) = (\alpha + \gamma)$$
Which implies $\beta = \gamma = \alpha = 1+ \frac{k}{2} = \frac{2 + k}{2}$,
Now from $(1)$ and $(1')$ we get $a = \frac{4}{\alpha} = \frac{8}{2+k}$ similarly from $(2),(2')$ and $(3),(3')$ we find, $b = \frac{20}{2+k}, c = \frac{112}{2+k}$
Thus from above we get $a+b+c = \frac{140}{2+k}$ and from $(4)$ we get: $\frac{140}{2+k} = \frac{70}{k}$ from which we can derive $k = 2$
Thus we could derive $a = 2, b = 5, c = 28$ but, the problem now is $a, b, c$ values don't satisfy equation $(4)$ above for $k =2$
Well so, where do I err ? And did I take the right approach ? Do post the solution about how you solved for $x$.

REPLY [2 votes]: Your deductions are wrong and that is what is misleading you. Integers can be both positive and negative.
If you solve equations (1), (2) and (3) simultaneously you can find a, b and c.
I did this to find $$a=3$$
$$b=5$$
$$c=7$$
You can then plug this into the forth equation given in the problem to solve for x.
$$x = \frac{abc}{ a + b + c} $$
which solves to give $$x=\frac{105}{15}=7$$


TITLE: Reference request for a type III action of a group on a manifold
QUESTION [2 upvotes]: Let an action of a group $\Gamma$ on a manifold $M$ such that $L^{∞}(M)⋊Γ$ is a type $III$ factor.
André Henriques posted here the following comment :

I don't know the literature, so I can't point to a reference, but
here's how things go:
Given an (let's say a.e. smooth) action of a
group $Γ$ on a manifold $M$, you can form the bundle of densities
$Ω^{top}_{>0}M$, which is a principal bundle with structure group
$\mathbb{R}_{>0}$.
The action of $Γ$ on $M$ induces an action on
$Ω^{top}_{>0}M$, and the von Neumann algebra $L^{∞}(M)⋊Γ$ is a type
$III_{1}$ factor iff the action of $Γ$ on $Ω^{top}_{>0}M$ is ergodic.
If that action is not ergodic, the von Neumann algebra
$L^{∞}(Ω^{top}_{>0}M)^{Γ}$ is equipped with an action of
$\mathbb{R}_{>0}$ (coming from the action on $Ω^{top}_{>0}M$). This
corresponds to a action of $\mathbb{R}_{>0}$ on some measure space
$X$. If that action is transitive, it is equivalent to
$\mathbb{R}_{>0}$ acting on $\mathbb{R}_{>0}/\mathbb{Z}^{λ}$ for some
$λ∈(0,1)$, and the factor $L^{∞}(M)⋊Γ$ is of type $III_{λ}$. Otherwise, $L^{∞}(M)⋊Γ$ is of type $III_{0}$.

Is there a reference for this result (or something close to it) ?

REPLY [2 votes]: This question has nothing to do with manifolds - you are just talking about the classification of type III actions with quasi-invariant measure in terms of their Radon-Nikodym cocycles. It should be contained, for instance, in the old "Indian" book of Klaus Schmidt.


TITLE: In the definition of linear map, is the symbol $+$ overloaded?
QUESTION [4 upvotes]: On Wikipedia, the following definition of linear map is given:

Let $V$ and $W$ be vector spaces over the same field $K$. A function $f:V\to W$ is said to be a linear map if for any two vectors $\mathbf{u},\mathbf{v}\in V$ and any scalar $c\in K$, the following conditions are satisfied:
\begin{align}
f(\mathbf{u}+\mathbf{v})&=f(\mathbf{u})+f(\mathbf{v}) \tag{*}\label{*}\\[5pt]
f(c\mathbf{u})&=cf(\mathbf u)
\end{align}

My question is: does the $+$ sign on the LHS of $\eqref{*}$ mean something different to the $+$ sign on the RHS? As far as I understand, on the LHS it denotes the vector addition operation of $V$, whereas on the RHS it denotes the vector addition operation of $W$, and these are not necessarily the same operation. Similarly, does $c\mathbf{u}$ refer to scalar multiplication in $V$, whereas $cf(\mathbf{u})$ refers to scalar multiplication in $W$?

REPLY [4 votes]: You're right. There is a lecturer named Frederic Schuller who has done a mathematical treatment of GR in a set of publicly available Youtube lecture, and in it, he removed the ambiguity by adding subscripts under the addition symbol:
$$ f(u+_V v) = f(u) +_W f(W)$$


TITLE: How to write this integral in terms of Gamma functions
QUESTION [0 upvotes]: $\int_0^1 dx \ x^{\alpha n}(1-x)^{\beta n} = \frac{\Gamma(\alpha n +1)\Gamma(\beta n +1)}{\Gamma(\alpha n + \beta n + 2)}$ for Re($\alpha$n) > -$1$ and Re($\beta$n) > -$1$.
I want to manipulate the left side in order to arrive at the result on the right but I fail to make it work. Reparametrizations to write an integral in form of a Gamma function are clear to me but how do I end up with three different ones? Thanks in advance for any help!

REPLY [1 votes]: The Beta function is defined
$$
B(x,y)=\int_0^1 t^{x-1} (1-t)^{y-1}dt=\frac{\Gamma (x)\Gamma (y)}{\Gamma (x+y)}
$$
In your case $x=1+\alpha m$ and $y=1+\beta n$ which gives the result you are seeking.


TITLE: Show that $\lim_{x\to\infty} \int_0^x f(x-y) g(y) dy = 0$
QUESTION [1 upvotes]: I have came up with a proof but now sure if the last part is correct/the best way to do it.

Let $f(x),g(x)$ be real-valued continuous functions defined on $[0,\infty)$ satisfying the followings:
(a). $\lim_{x\to\infty} f(x) = 0$
(b). $\int_0^\infty \left| g(x) \right| dx < +\infty$
Prove that if $h(x)$ is defined as
\begin{equation}
h(x) = \int_0^x f(x-y) g(y) dy
\end{equation}
then $\lim_{x\to\infty} h(x) = 0$.

For convenience, let $\int_0^\infty \left| g(x) \right| dx = M$.
Since $\lim_{x\to\infty} f(x) = 0$, for any $\epsilon > 0$, we can find $K_\epsilon > 0 $ such that whenever $x > K_\epsilon$, $\left| f(x) \right| < \epsilon $ holds. If we want $ x - y > K_\epsilon $, then we need $y < x - K_\epsilon$. This gives us
\begin{align}
\left| h(x) \right| &= \left| \int_0^x f(x-y) g(y) dy \right| < \int_0^x \left| f(x-y) \right| \left| g(y) \right| dy\\
& = \int_0^{x - K_\epsilon} \left| f(x-y) \right| \left| g(y) \right| dy + \int_{x - K_\epsilon}^x \left| f(x-y) \right| \left| g(y) \right| dy \\
&< M\epsilon + \int_{x - K_\epsilon}^x \left| f(x-y) \right| \left| g(y) \right| dy
\end{align}
When $y\in [x-K_\epsilon ,x]$, we get can a uniform bound for $f(x-y)$ since $f$ is continuous. Let $f(x-y) \le M'$ for all $y\in [x-K_\epsilon, x]$. Then we now have
\begin{equation}
\left| h(x) \right| \le M \epsilon + M' \int_{x-K_\epsilon}^x \left| g(y) \right| dy
\end{equation}
We claim that as $x\to \infty$, the integral on the right hand side goes to zero. This is because
\begin{align}
\left| \int_{x-K_\epsilon}^x \left| g(y) \right| dy \right| &= \left| \int_0^x \left| g(y) \right| dy - \int_0^{x - K_\epsilon} \left| g(y) \right| dy \right|\\
& = \left| \int_0^x g(y) dy - M + M - \int_0^{x - K_\epsilon} g(y) dy \right|\\
&\le \left| \int_0^x g(y) dy - M\right| + \left| \int_0^{x - K_\epsilon} g(y) dy - M\right| \\
& \le \frac{\epsilon}{2} + \frac{\epsilon}{2}=\epsilon
\end{align}
and since $\int_0^\infty \left| g(x) \right| dx = M$, we can find $P$ such that when $x > P$, both $\int_0^x \left| g(y) \right| dy $ and $\int_0^{x - K_\epsilon} \left| g(y) \right| dy $ are small.
As a result, $\lim_{x\to\infty} \left| h(x) \right| = 0$.
Any feedback is appreciated!

REPLY [0 votes]: Another solution using Lebesgue's dominated convergence.
$$|h(x)|\le \int_0^x |f(x-y)g(y)|~dy=\int_0^{\infty}1_{(0,x)}|f(x-y)g(y)|~dy$$
Then note that since $f\to 0$ as $x\to\infty$ and $f$ is continuous, we have that $f$ is bounded by some $M$. So $1_{(0,x)}|f(x-y)g(y)|\le M|g(y)|$ and by assumption $g$ is absolutely integrable. So we may apply dominated convergence. Note for any $y$, $\lim_{x\to\infty} 1_{(0,x)}|f(x-y)g(y)|=0$. The result follows.


TITLE: Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.
QUESTION [1 upvotes]: First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k  \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up into two parts; proving that the $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $9$, and that it's divisible by $11$. Unfortunately, I factor it out and get $10(4\cdot10^{2n} + 9\cdot10^{2n-1} + 5)-45$, which is equal to $10(99k)-45$, but of $99$'s divisors, only $3$ divides $45$.
Is there a more ingenious way to factor this equation so that all of my problems are solved?

REPLY [2 votes]: Let $f_{n}\equiv4\cdot10^{2n}+9\cdot10^{2n-1}+5$. Then $f_{1}=4\cdot100+9\cdot10+5=495$,
and $99\mid495$ so $99\mid f_{1}$. Now, suppose that for some $n\in\mathbb{N}$,
$99\mid f_{n}$. Now, since $100\equiv1\text{ mod }99$,
\begin{align*}
f_{n+1} & \equiv 4\cdot10^{2\left(n+1\right)}+9\cdot10^{2\left(n+1\right)-1}+5\text{ (mod) }99\\
 & \equiv 4\cdot10^{2n+2}+9\cdot10^{2n+1}+5\text{ (mod) }99\\
 & \equiv 4\cdot10^{2n}\cdot10^{2}+9\cdot10^{2n-1}\cdot10^{2}+5\text{ (mod) }99\\
 & \equiv4\cdot10^{2n}+9\cdot10^{2n-1}+5\text{ (mod) }99\\
 & \equiv f_n \text{ (mod) } 99 \\
 & \equiv 0 \text{ (mod) } 99
\end{align*}

REPLY [2 votes]: Assuming that $4\times10^{2n}+9\times10^{2n-1}+5=99k$,
$$
4\times10^{2(n+1)}+9\times10^{2(n+1)-1}+5=4\times10^{2n+2}+9\times10^{2n+1}+5=100\times(4\times10^{2n})+100\times(9\times10^{2n-1})+5=100\times(4\times10^{2n}+9\times10^{2n-1})+5=100\times(4\times10^{2n}+9\times10^{2n-1}+5-5)+5=100\times(4\times10^{2n}+9\times10^{2n-1}+5)-500+5=100\times99k-495=100\times99k-5\times99=(100k-5)\times99.
$$

REPLY [1 votes]: A number is a multiple of $9$ iff the sum of its decimal digits is a multiple of $9$. Your numbers satisfy this: $4+9+5=18$.
A number is a multiple of $11$ iff the alternating sum of its decimal digits is a multiple of $11$. Your numbers satify this: $4-9+5=0$.
Explicitly, we have $4900\cdots05=9\cdot 544\cdots45$ and $4900\cdots05=11\cdot 4454\cdots5455$.
Or directly, $4900\cdots05=99\cdot 4949\cdots495$, which is the formula given by Martin.

REPLY [1 votes]: Base case: $n=1$: $4 \cdot 10^2 + 9 \cdot 10^{1}+5 = 495$, and $ 99|495 $.
Induction step: $n=k$: Suppose $99|4 \cdot 10^{2k} + 9 \cdot 10^{2k-1}+5$.
Then you need to show it is also true for $n=k+1$.