The proof of the asymptotic formula
$$
\Phi(n) = \frac{3}{\pi^2} n^2 + O(n\log n)
$$
can be modified to give a simple upper bound that has the right asymptotic character (but is not very accurate). We'll follow the proof in Chandrasekharan's Introduction to Analytic Number Theory.
By interpreting $\Phi(n)$ as the number of lattice points with relatively prime coordinates in or on the triangle $0 < y \leq x \leq n$, Chandrasekharan obtains the formula
$$
\Phi(n) = \frac{\Psi(n)+1}{2},
$$
where
$$
\Psi(n) = \sum_{1 \leq d \leq n} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor^2.
$$
If we write
$$
\left\lfloor \frac{n}{d} \right\rfloor = \frac{n}{d} - \left\{\frac{n}{d}\right\},
$$
then
$$
\begin{align}
\Psi(n) &= \sum_{1 \leq d \leq n} \mu(d)\left(\frac{n}{d} - \left\{\frac{n}{d}\right\}\right)^2 \\
&= n^2 \sum_{1 \leq d \leq n} \frac{\mu(d)}{d^2} - 2n \sum_{1 \leq d \leq n} \frac{\mu(d)}{d}\left\{\frac{n}{d}\right\} + \sum_{1 \leq d \leq n} \mu(d) \left\{\frac{n}{d}\right\}^2.
\end{align}
$$
Now
$$
\begin{align}
-2n \sum_{1 \leq d \leq n} \frac{\mu(d)}{d}\left\{\frac{n}{d}\right\} &< 2n \sum_{1 \leq d \leq n} \frac{1}{d} \\
&< 2n \left(1+\int_1^n \frac{du}{u}\right) \\
&= 2n(1+\log n)
\end{align}
$$
and
$$
\sum_{1 \leq d \leq n} \mu(d) \left\{\frac{n}{d}\right\}^2 < \sum_{1 \leq d \leq n} 1 = n,
$$
giving us
$$
\Psi(n) < n^2 \sum_{1 \leq d \leq n} \frac{\mu(d)}{d^2} + 2n\log n + 3n.
$$
For the sum we get
$$
\begin{align}
\sum_{1 \leq d \leq n} \frac{\mu(d)}{d^2} &= \sum_{1 \leq d \leq
\infty} \frac{\mu(d)}{d^2} - \sum_{n+1 \leq d \leq \infty} \frac{\mu(d)}{d^2} \\
&= \frac{6}{\pi^2} - \sum_{n+1 \leq d \leq \infty} \frac{\mu(d)}{d^2} \\
&< \frac{6}{\pi^2} + \sum_{n+1 \leq d \leq \infty} \frac{1}{d^2} \\
&< \frac{6}{\pi^2} + \int_n^\infty \frac{du}{u^2} \\
&= \frac{6}{\pi^2} + \frac{1}{n},
\end{align}
$$
so that, in total,
$$
\Psi(n) < \frac{6}{\pi^2} n^2 + 2n\log n + 4n
$$
and hence
$$
\Phi(n) < \frac{3}{\pi^2} n^2 + n\log n + 2n + \frac{1}{2}.
$$
I don't know if we can use convolution to prove your statement, and it's the first time i see it so I don't know any reference , But I have a proof by induction.
The first terms $a_1,a_2$ coincide with Fibonacci numbers.
Let us suppose that:$a_1,a_2,\cdots,a_{x},a_{x+1}$ are the first Fibonacci numbers (this assumption is used in the proposition) and prove that $a_{x+2}$ is the next Fibonacci number.
we compute $a_{x+2}-a_{x+1}$:
$$a_{x+2}-a_{x+1}=\sum_{n:\alpha(n)=x} \varphi(n)+\sum_{n:\alpha(n)<x-1}\varphi(n) \left (\left \lfloor{ \frac{x}{\alpha(n)} }\right \rfloor - \left \lfloor{ \frac{x-1}{\alpha(n)} }\right \rfloor\right )$$
And we know that $ \lfloor x/k \rfloor - \lfloor (x-1)/k \rfloor = 1 $ when $k|x$ (for $k\geq1$) and $0$ otherwise, so
$$a_{x+2}-a_{x+1}=\sum_{n:\alpha(n)|x} \varphi(n)\,\,\,\, (1)$$
but we have
Proposition for every positive integer $n$ $$\alpha(n)|x \Leftrightarrow n|a_x$$
proof
first it's clear that if $\alpha(n)=k$ with $k|x$ then $n|a_k$, and because $a_k$ and $a_x$ are Fibonacci numbers then $a_k|a_x$ finally $n|a_x$.
Second, given a divisor $n$ of $a_x$,let $\alpha(n)=k\leq x$ then $n|a_k$ so $n|gcd(a_k,a_x)=a_{gcd(x,k)}$ ( because $a_x$ and $a_k$ are Fibonacci numbers) using the definition of $\alpha(n)$ we have $k\leq gcd(x,k)$ hence $k|x$.
Using the proposition, the sum $(1)$ becomes:
$$a_{x+2}-a_{x+1}=\sum_{n:n|a_x} \varphi(n)$$
using Euler's identity $\sum_{d:d|n} \varphi(d)=n$ :
$$a_{x+2}-a_{x+1}=a_x $$
Finally $a_{x+2}$ is the next Fibonacci number
Best Answer
I'll recall (as is more or less indicated in the link you provided) that for the second identity $$ \sum_{0<k\leq 2n}\left\lfloor\frac nk\right\rfloor \varphi(k)=\frac{n^2+n}2 $$ both sides can be interpreted as counting the integer pairs $(x,y)$ satifying $0\leq x<y\leq n$ as follows. The right hand side counts by fixed value of $y$, giving $1+2+\cdots+n=\frac{n(n+1)}2$. The left hand side (where clearly only values $k\leq n$ contribute) counts by the value of $k=y/\gcd(x,y)$, in other words by the denominator of the fraction $x/y$ after reducing it. For such a $k$ there are $\phi(k)$ possible values for $l=x/\gcd(x,y)$ (the corresponding numerator), and for given $(l,k)$ the number of pairs $(x,y)$ that reduce to it is equal to the number of multiples of $k$ that are${}\leq n$, which is $\lfloor\frac nk\rfloor$.
Now the first identity can be done by a slight variation of this. The crucial point is to interpret $\lfloor\frac nk+\frac12\rfloor$ as the number of odd multiples of $k$ that are${}\leq2n$, which is easily checked. This leads us to count integer pairs $(x,y)$ satifying $0\leq x<y\leq2n$ and not both even. Counting by fixing $y$, one gets combining the odd values of $y$ the contribution $1+3+5+\cdots+(2n-1)=n^2$, and combining the even values of $y$ the contribution $1+2+3+\cdots+n=\frac{n(n+1)}2$, all in all $\frac{3n^2+n}2$ which is it right hand side of your first identity. For the left hand side the argument is exactly as before: the reduced pair $(l,k)$ cannot have both components even, so every $k$ gives the same number $\phi(k)$ of reduced pairs as before, however we can take only odd multiples of any reduced pair, giving $\lfloor\frac nk+\frac12\rfloor\phi(k)$ contributions from a given $k$ (for this case values $n<k\leq2n$ do contribute).
As you probably already had observed, one has $\lfloor\frac nk+\frac12\rfloor-\lfloor\frac nk\rfloor=1$ if $k\in S(n)$ and the difference is $0$ otherwise, which easily leads to your initial result.