number theory - Average order of $mathrm{rad}(n)$

Let $\mathrm{rad}(n)$ denote the radical of an integer $n$, which is the product of the distinct prime numbers dividing n. Or equivalently, $$\mathrm{rad}(n)=\prod_{\scriptstyle p\mid n\atop p\text{ prime}}p.$$ Assume $\mathrm{rad}(1)=1$, so that $\mathrm{rad}(n)$ is multiplicative.

I was wondering if one has a nice asymptotic formula for the sum $$\sum_{n\le x}\mathrm{rad}(n).$$
At first, I wanted to use the Wiener-Ikehara Theorem. Using Euler Product, we have
\begin{align}
\begin{split}
R(s)&=\sum_{n\ge 1}\frac{\mathrm{rad}(n)}{n^s}=\prod_{p}(1+\frac{p}{p^s}+\frac{p}{p^{2s}}+\cdots)\\
&=\prod_{p}(1+\frac{p}{p^s}\frac{1}{1-p^{-s}})\\
&=\zeta(s)\prod_{p}(1+\frac{p-1}{p^s}).
\end{split}
\end{align}
However, the Wiener-Ikehara Theorem seems not to work here because the product part diverges when $s=1.$

Comparing term-wisely with the product and using $1$$\frac{\zeta(s)^2}{\zeta(2s)}

Moreover, if multiplicative function $\mathrm{core}(n)$ is defined to map positive integers ''n'' to square-free numbers by reducing the
exponents in the prime power representation modulo 2, or in formula
: $$\mathrm{core}(p^e) = p^{e\mod 2}.$$ with $\mathrm{core}(1) =1 .$ Or equivalently, $$\mathrm{core}(p^{2k+1})=p,$$ $$\mathrm{core}(p^{2k})=1$$
Then we always have $$\mathrm{core}(n) \le \mathrm{rad}(n).$$
Since the Dirichlet generating function of $\mathrm{core}$ is
:

\begin{align}
\begin{split}
C(s)&=\sum_{n\ge 1}\frac{\mathrm{core}(n)}{n^s}
=\prod_{p}(1+\frac{p}{p^s}+\frac{1}{p^{2s}}+\frac{p}{p^{3s}}+\frac{1}{p^{4s}}+\cdots)\\
&=\prod_{p}(1+\frac{\frac{p}{p^s}+\frac{1}{p^{2s}}}{1-\frac{1}{p^{2s}}})\\
&=\frac{\zeta(2s)\zeta(s-1)}{\zeta(2s-2)}.
\end{split}
\end{align}

$$\frac{\zeta(2s)\zeta(s-1)}{\zeta(2s-2)}
Here we may use the Wiener-Ikehara Theorem to derive asymptotic bounds.

This was as far as I could work out.
Are there any results considering the average order of $\mathrm{rad}(n)$ or analytic expression of its Dirichlet series? Thanks.

Answer

The general methodology used in this answer will handle your sum: Mean Value of a Multiplicative Function close to $n$ in Terms of the Zeta Function. (See also this MSE answer, and this answer on Math Overflow)

The main theorem proven in that answer is that if we let $g$ be defined so that $(1*g)(n)=\frac{f(n)}{n}$, then for any $0<\sigma<1$ we have that

$$\sum_{n\leq x}f(n)=\frac{x^2}{2}\sum_{d=1}^\infty\frac{g(d)}{d}+O\left(x^{1+\sigma}\sum_{d=1}^\infty \frac{|g(d)|}{d^\sigma}\right).$$

Note this result does not make sense unless $f$ is close to $n$ as a multiplicative function, as otherwise the series involving $g(n)$ will not converge.

In our case, $f(p^k)=p$ for all $k$, and so $f(p^k)/p^k = 1/p^{k-1}$. Convolving with the mobius function we find that $$g(p^{k})=\begin{cases}
0 & \text{if }k=1\\
\frac{1}{p^{k-1}}-\frac{1}{p^{k-2}} & \text{if }k\geq2
\end{cases} $$
Thus, since $$\sum_{n=1}^{\infty}\frac{g(n)}{n}=\prod_{p}\left(1+\frac{g(p)}{p}+\frac{g(p^{2})}{p^{2}}+\cdots\right) =

\prod_{p}\left(1+\frac{\frac{1}{p}-1}{p^{2}}+\frac{\frac{1}{p}-1}{p^{4}}+\cdots\right)=\prod_{p}\left(1-\left(\frac{p-1}{p}\right)\left(\frac{1}{p^{2}-1}\right)\right)=\prod_{p}\left(1-\frac{1}{p(p+1)}\right), $$ by taking $\sigma = 1+\frac{1}{\log x}$ we obtain

$$\sum_{n\leq x}\text{rad}(n)=\frac{x^2}{2}\prod_p \left(1-\frac{1}{p(p+1)}\right)+O\left(x^{3/2}\log x\right).$$

real analysis - Injective functions with intermediate-value property are continuous. Better proof?

A function $f: \mathbb{R} \to \mathbb{R}$ is said to have the intermediate-value property if for any $a$, $b$ and $\lambda \in [f(a),f(b)]$ there is $x \in [a,b]$ such that $f(x)=\lambda$.

A function $f$ is injective if $f(x)=f(y) \Rightarrow x=y$.

Now it is the case that every injective function with the intermediate-value property is continuous. I can prove this using the following steps:

1. An injective function with the intermediate-value property must be monotonic.


2. A monotonic function possesses left- and right-handed limits at each point.


3. For a function with the intermediate-value property the left- and right-handed limits at $x$, if they exist, equal $f(x)$.

I am not really happy with this proof. Particularly I don't like having to invoke the intermediate-value property twice.

Can there be a shorter or more elegant proof?

probability - Finite sample bounds for generalized coupon collector problem

Consider the usual generalization of the coupon collector problem where $m$ copies of each coupon need to be collected. Let $T_m$ be the first time m copies of each coupon are collected. Donald J. Newman and Lawrence Shepp showed that
$$\mathbf{E} (T_{m})=n\log n+(m-1)n\log \log n+O(n),\ {\text{as}}\ n\to \infty $$

Then Erdős and Rényi showed that:

$$\displaystyle \operatorname {P} {\bigl (}T_{m}

But these statement are asymptotic. Are there known finite sample (upper and lower) bounds on $T_m$ ?

Answer

What follows is a minor contribution where we compute a formula for
the expectation for the case where $j$ instances of each of $n$ types
of coupons must be seen. Using the notation from the following MSE
link we have from
first principles that

$$P[T = m] = \frac{1}{n^m}\times {n\choose 1}\times
(m-1)! [z^{m-1}]
\left(\exp(z) - \sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1}
\frac{z^{j-1}}{(j-1)!}

\\ = \frac{n}{n^m}\times
{m-1\choose j-1} (m-j)! [z^{m-j}]
\left(\exp(z) - \sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1}.$$

We verify that this is a probability distribution. The goal here
is to find a closed form for the infinite series in $m$ so that its
value may be calculated rather than approximated. Expanding the power
we find

$$\sum_{m\ge j} P[T=m] =

\frac{n}{n^j} \sum_{m\ge 0} \frac{1}{n^m} \times
{m+j-1\choose j-1} m! [z^m]
\sum_{k=0}^{n-1}
{n-1\choose k} \exp(kz) \\ \times (-1)^{n-1-k}
\left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}
\\ = \frac{n}{n^j} \sum_{m\ge 0} \frac{1}{n^m} \times
{m+j-1\choose j-1} m!
\sum_{k=0}^{n-1}
{n-1\choose k}
\sum_{p=0}^m \frac{k^{m-p}}{(m-p)!} \\ \times (-1)^{n-1-k}

[z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}
\\ = \frac{n}{n^j} \sum_{k=0}^{n-1}
{n-1\choose k} (-1)^{n-1-k}
\sum_{p\ge 0}
[z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}
\\ \times \sum_{m\ge p}\frac{1}{n^m} \times
{m+j-1\choose j-1} m! \times \frac{k^{m-p}}{(m-p)!}
\\ = \frac{n}{n^j} \sum_{k=0}^{n-1}
{n-1\choose k} (-1)^{n-1-k}
\sum_{p\ge 0}

n^{-p} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}
\\ \times \sum_{m\ge 0}\frac{1}{n^m} \times
{m+p+j-1\choose j-1} (m+p)! \times \frac{k^m}{m!}$$

The inner sum is

$$\frac{1}{(j-1)!} \sum_{m\ge 0} (k/n)^m \frac{(m+p+j-1)!}{m!}
= \frac{(p+j-1)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}$$

and with $P=(n-1-k)(j-1)$ we obtain

$$\bbox[5px,border:2px solid #00A000]{
n \sum_{k=0}^{n-1}
{n-1\choose k} \frac{(-1)^{n-1-k}}{(n-k)^j}
\times \sum_{p=0}^P
\frac{1}{(n-k)^p} \frac{(p+j-1)!}{(j-1)!}
[z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}.}$$

We claim that the inner sum is $(n-k)^{j-1},$ proof for $j=2$ at end
of document. With this the sum reduces to

$$n \sum_{k=0}^{n-1}
{n-1\choose k} \frac{(-1)^{n-1-k}}{n-k}
\\ = - \sum_{k=0}^{n-1} {n\choose k} (-1)^{n-k}
= 1 - \sum_{k=0}^{n} {n\choose k} (-1)^{n-k} = 1$$

and we see that we indeed have a probability distribution.

Continuing with the expectation and re-capitulating the earlier
computation we find

$$E[T] = \sum_{m\ge j} m P[T = m] =
\frac{n}{n^j} \sum_{k=0}^{n-1}
{n-1\choose k} (-1)^{n-1-k}
\sum_{p\ge 0}
n^{-p} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}
\\ \times \sum_{m\ge 0}\frac{1}{n^m} \times
{m+p+j-1\choose j-1} (m+p)! (m+p+j) \times \frac{k^m}{m!}$$

The inner sum has two pieces, the first is

$$\frac{1}{(j-1)!} \sum_{m\ge 1} (k/n)^m \frac{(m+p+j-1)!}{(m-1)!}
= \frac{1}{(j-1)!} \frac{k}{n}
\sum_{m\ge 0} (k/n)^m \frac{(m+p+j)!}{m!}
\\ = \frac{k}{n} \frac{(p+j)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j+1}}
= \frac{k}{n-k} \frac{(p+j)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}$$

and the second has been evaluated when we summed the probabilities to
give

$$(p+j) \frac{(p+j-1)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}
= \frac{(p+j)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}.$$

Substituting these into the outer sum we thus obtain

$$\bbox[5px,border:2px solid #00A000]{E[T] = n^2 \sum_{k=0}^{n-1}
{n-1\choose k} \frac{(-1)^{n-1-k}}{(n-k)^{j+1}}
\times \sum_{p=0}^P
\frac{1}{(n-k)^p} \frac{(p+j)!}{(j-1)!}
[z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}.}$$

There is a very basic program which confirmed this formula for several
digits of precision by simulation which is written in C and goes as
follows.

#include 
#include 
#include 
#include 


int main(int argc, char **argv)
{
  int n = 6 , j = 3, trials = 1000; 

  if(argc >= 2){
    n = atoi(argv[1]);
  }

  if(argc >= 3){

    j = atoi(argv[2]);
  }

  if(argc >= 4){
    trials = atoi(argv[3]);
  }

  assert(1 <= n);
  assert(1 <= j);
  assert(1 <= trials);


  srand48(time(NULL));
  long long data = 0;

  for(int tind = 0; tind < trials; tind++){
    int seen = 0; int steps = 0; 
    int dist[n];

    for(int cind = 0; cind < n; cind++){
      dist[cind] = 0;

    }

    while(seen < n){
      int coupon = drand48() * (double)n;

      steps++;

      if(dist[coupon] == j-1)
        seen++;
      dist[coupon]++;

    }

    data += steps;
  }

  long double expt = (long double)data/(long double)trials;
  printf("[n = %d, j = %d, trials = %d]: %Le\n", 
         n, j, trials, expt);

  exit(0);

}

Proof of inner sum for $j=2.$
Setting $j=2$ we have to show that

$$n-k = \sum_{p=0}^{n-1-k} {n-1-k\choose p}
\frac{1}{(n-k)^p} (p+1)!.$$

This is

$$\frac{1}{(n-1-k)!} =
\sum_{p=0}^{n-1-k} \frac{1}{(n-1-k-p)!} \frac{p+1}{(n-k)^{p+1}}.$$

Re-writing as follows

$$\frac{1}{m!} =
\sum_{p=0}^{m} \frac{1}{(m-p)!} \frac{p+1}{(m+1)^{p+1}}.$$

and introducing

$$\frac{1}{(m-p)!} =
\frac{1}{2\pi i}
\int_{|w|= \gamma}
\frac{1}{w^{m-p+1}} \exp(w) \; dw$$

we obtain for the sum (the integral vanishes nicely when $p\gt m$ so
we may extend $p$ to infinity)

$$\frac{1}{2\pi i}

\int_{|w|= \gamma}
\frac{1}{w^{m+1}} \exp(w) \frac{1}{m+1}
\sum_{p\ge 0} \frac{p+1}{(m+1)^p} w^p
\; dw
\\ = \frac{1}{m+1} \frac{1}{2\pi i}
\int_{|w|= \gamma}
\frac{1}{w^{m+1}} \exp(w)
\frac{1}{(1-w/(m+1))^2}
\; dw.$$

We now use the fact that residues sum to zero and the poles are at
$w=0$, $w=m+1$ and $w=\infty.$ We get for the residue at infinity

$$-\frac{1}{m+1}
\mathrm{Res}_{w=0} \frac{1}{w^2} w^{m+1} \exp(1/w)
\frac{1}{(1-1/w/(m+1))^2}
\\ = - \frac{1}{m+1} \mathrm{Res}_{w=0} w^{m+1} \exp(1/w)
\frac{1}{(w-1/(m+1))^2}
\\ = - (m+1) \mathrm{Res}_{w=0} w^{m+1} \exp(1/w)
\frac{1}{(1-w(m+1))^2}

\\ = -(m+1) [w^{-(m+2)}] \exp(1/w)
\frac{1}{(1-w(m+1))^2}.$$

Extracting coefficients we find

$$-(m+1)\sum_{q\ge 0} \frac{1}{(q+m+2)!} (q+1) (m+1)^q.$$

This is

$$-(m+1) \left(\sum_{q\ge 0} \frac{1}{(q+m+1)!} (m+1)^q

- \sum_{q\ge 0} \frac{1}{(q+m+2)!} (m+1)^{q+1}\right)
\\ = -(m+1) \left(\sum_{q\ge 0} \frac{1}{(q+m+1)!} (m+1)^q
- \sum_{q\ge 1} \frac{1}{(q+m+1)!} (m+1)^{q}\right)
\\ = -(m+1) \frac{(m+1)^0}{(m+1)!} = - \frac{1}{m!}.$$

We thus have the claim if we can show the residue at $w=m+1$ is zero.
We use

$$(m+1)\frac{1}{2\pi i}
\int_{|w|= \gamma}

\frac{1}{w^{m+1}} \exp(w)
\frac{1}{(w-(m+1))^2}
\; dw.$$

and observe that

$$\left.\left(\frac{1}{w^{m+1}} \exp(w) \right)'\right|_{w=m+1}
\\= \left.\left( -(m+1)\frac{1}{w^{m+2}} \exp(w)
+ \frac{1}{w^{m+1}} \exp(w) \right)\right|_{w=m+1}
\\ = \exp(m+1)

\left(-(m+1)\frac{1}{(m+1)^{m+2}}+\frac{1}{(m+1)^{m+1}}\right)
= 0$$

as required. This concludes the computation.

sequences and series - Convert recurrent formula with polynomial term / parameter to explicit formula

So, I know how to convert to explicit formulas things like the Fibonacci sequence cause it only consists of $a_n$ like this:

$$a_{n} = a_{n-1} + a_{n-2}$$

However my problem is I've encountered a type of this problem I haven't been thought how to approach, and can't find the solution anywhere:

$$a_{n} = a_{n-1} + n+1$$

The sequence this is supposed to represent is: $0, 2, 5, 9, 14, 20, 27 ...$

The correct explicit formula that I don't know how to get to for this is:

$$a_n = \frac{n}{2}(n+3)$$

---

To solve this, I've tried converting it to:

$$r^n = r^{n-1} + n + 1$$

and treating n as the superscript of r... to end up with

$$r^2=r+2+1$$

..which is the standard procedure I've been taught, then solving for $r$ to get $r_1$ and $r_2$ and adding $\alpha$ and $\beta$ like I've been taught to get:

$$a_n = \alpha(r_1)^n + \beta(r_2)^n$$

.. then plugging in known $n$ and $a_n$ values to get a system of equations and then finally plug in the resulting $\alpha$ and $\beta$ to get the explicit formula, which however turned out to be complete gibberish. I'm sure I didn't mess up the system of equations or any step since I used automated equation solving to make sure.

That means the problem is me not knowing how to deal with that problem in the first place, I think. It seems to have a non-standard procedure to it.

Answer

The formula which you give, $a_n=\frac{n}{2}(n+3)$ is not the correct formula for the sequence defined recursively by $a_1=0, a_{n+1}=a_n+n+1$.

This is a sequence with a constant second difference.

The sequence is

$$ 0, 2, 5, 9, 14, 20, 27,\cdots $$

The first difference is found by subtracting each term from the following term:

$$ 2, 3, 4, 5, 6, 7, \cdots $$

The second difference is a constant sequence consisting entirely of ones.

When the second difference is constant, $a_n$ is a second degree polynomial in $n$

$$a_n=rn^2+sn+t$$

We are given that

$$ a_{n+1}-a_n=n+1 $$

Therefore

\begin{eqnarray}

r(n+1)^2+s(n+1)+t-(rn^2+sn+t)&=&n+1\\
2rn+r+s&=&n+1
\end{eqnarray}

So

\begin{eqnarray}
2r&=&1\\
r+s&=&1
\end{eqnarray}

which gives $r=s=\frac{1}{2}$

Now we have that

\begin{eqnarray}
a_n&=&\frac{1}{2}n^2+\frac{1}{2}n+t\\
a_1&=&\frac{1}{2}+\frac{1}{2}+t=0\\
\end{eqnarray}

Therefore, $t=-1$

\begin{eqnarray}
a_n&=&\frac{1}{2}n^2+\frac{1}{2}n-1\\
&=&\frac{1}{2}(n^2+n-2)\\
&=&\frac{1}{2}(n-1)(n+2)
\end{eqnarray}

field theory - smallest normal extension containing an infinite algebraic extension

Let $F/k$ be an algebraic extension. Let $S(F/k)$ be the set of all embeddings of F over k into algebraic closure $k^\mathrm{a} $. I'm trying to prove that the smallest normal extension of k containing F is

$E= \displaystyle\prod_{\sigma \in S(F/k)} \sigma F$ ($\Pi$ is used to denote the compositum of fields)

In the finite extension case, matter is simple as if $\tau$ is embedding of E over k, $\sigma \mapsto \tau\sigma$ is an injective mapping of $S(F/k)$ into $S(F/k)$. Since $S(F/k)$ is finite, the above mapping is bijective and $E= \displaystyle\prod_{\sigma \in S(F/k)} \sigma F=\prod{\tau\sigma F} $.

But in the infinite extension case when $S(F/k) $ might not be finite, surjective part must be added to prove that $\tau$ induces permutation on $S(F/k) $. I don't quite get an idea of how I should prove the surjectiveness.

calculus - show that $int_{-infty}^{infty} frac {(sin x) (x^2+a^2)}{x(x^2+b^2)}dx=frac{pi(a^2+e^{-b}(b^2-a^2))}{b^2}$

show that $$\int_{-\infty}^{\infty} \frac {(\sin x) (x^2+a^2)}{x(x^2+b^2)}dx=\frac{\pi(a^2+e^{-b}(b^2-a^2))}{b^2}$$

for every $a,b>0$

thanks for all

Answer

Consider the contour integral

$$\oint_C dz \frac{(z^2+a^2) e^{i z}}{z (z^2+b^2)}$$

where $C$ is the semicircular contour of radius $R$ in the upper half-plane, with an additional semicircular contour of radius $\epsilon$ centered at the origin, jutting into the upper half-plane.

The contour integral is equal to

$$\int_{-R}^{-\epsilon} dx \, \frac{(x^2+a^2) e^{i x}}{x (x^2+b^2)} + i \epsilon \int_{-\pi}^0 d\phi e^{i \phi} \frac{(a^2+\epsilon^2 e^{i 2 \phi}) e^{i \epsilon e^{i \phi}}}{\epsilon e^{i \phi} (b^2+\epsilon^2 e^{i 2 \phi})}+\\\int_{\epsilon}^R dx \, \frac{(x^2+a^2) e^{i x}}{x (x^2+b^2)}+i R \int_0^{\pi} d\theta e^{i \theta}\frac{(a^2+R^2 e^{i 2 \theta}) e^{i R e^{i \theta}}}{Re^{i \theta} (b^2+R^2 e^{i 2 \theta})} $$

We take the limit as $R \to \infty$ and $\epsilon \to 0$ and get

$$PV \int_{-\infty}^{\infty} dx \, \frac{(x^2+a^2) e^{i x}}{x (x^2+b^2)} - i \pi \frac{a^2}{b^2}$$

Note that the magnitude of fourth integral vanishes as

$$2 \int_0^{\pi/2} e^{-R \sin{\theta}} \le 2 \int_0^{\pi/2} e^{-2 R \theta/\pi} \le \frac{\pi}{R}$$

as $R \to \infty$. By the residue theorem, the contour integral is equal to $i 2 \pi$ times the residue of the pole at $z=i b$. Therefore

$$PV \int_{-\infty}^{\infty} dx \, \frac{(x^2+a^2) e^{i x}}{x (x^2+b^2)} = i \pi \frac{a^2}{b^2} - i 2 \pi \frac{(a^2-b^2) e^{-b}}{2 b^2}$$

Similarly,

$$PV \int_{-\infty}^{\infty} dx \, \frac{(x^2+a^2) e^{-i x}}{x (x^2+b^2)} = -i \pi \frac{a^2}{b^2} + i 2 \pi \frac{(a^2-b^2) e^{-b}}{2 b^2}$$

Therefore,

$$\int_{-\infty}^{\infty} dx \, \frac{(x^2+a^2) \sin{x}}{x (x^2+b^2)} = \pi \frac{a^2}{b^2} - \pi \frac{(a^2-b^2) e^{-b}}{ b^2}$$

which is equivalent to the stated result.

calculus - How to find $lim_{xtoinfty}{frac{e^x}{x^a}}$?

$$\lim_{x\to\infty}{\frac{e^x}{x^a}}$$ For $a\in \Bbb R,$ find this limit.

I would say for $a\ge 0$ lim is equal to $\lim_{x\to\infty}{\frac{e^x}{a!x^0}=\infty}$ (from L'Hopital).

For $a<0$, lim eq. to $\frac{\infty}{0}$so lim doesnt exist. Is this correct?

Answer

Because $e^x > x$ for all $x$, $$\lim_{x \to \infty}\frac{e^x}{x}=\lim_{x \to \infty}\frac{1}{2}\left(\frac{e^{x/2}}{x/2}\right)e^{x/2} = \infty.$$
since $e^{x/2}/(x/2) > 1,$ and $e^{x/2} \to \infty$ as $x \to \infty$.

Then, it follows that $$\lim_{x \to \infty}\frac{e^x}{x^a}=\lim_{x \to \infty}\frac{1}{a^a}\cdot \left( \frac{e^{x/a}}{x/a}\right)^a = \infty$$

since we just showed that what is in parentheses approaches $\infty$ as $x \to \infty$, so the whole limit has to go to $\infty.$