Is there a proof to a sum over the 2-adic valuation? Is there a way to find an asymptotic form for,
$${1 \over n} \cdot \sum_{k=1}^n v_2(2 \cdot k)$$
As, $n$ approaches infinity?
I currently have logarithmic form, no constants, for the asymptotic relation, but I'd assume something better can be derived.
$v_2(x)$ is the 2-adic valuation of $x$. It finds the largest exponent $k$ such that $2^k$ divides $x$.
 A: Notice $\frac{1}{n}\sum_{k=1}^n v_2(2n)=1+\frac{1}{n}\sum_{k=1}^n v_2(k)$. Anyway, let's generalize.
Let $p$ be a prime. The sum $\sum_{k=1}^n v_p(k)$ collects a $1$ from every multiple of $p$ that is $\le n$, collects another $1$ from every multiple of $p^2$ in that range, and so on. The number of multiples of $p^e$ that are $\le n$ is bound between $n/p^e-1$ and $n/p^e$. Let $p^\ell$ be the biggest power of $p$ that is $\le n$. Then
$$\sum_{e=1}^\ell \left(\frac{n}{p^e}-1\right)\le \sum_{k=1}^n v_p(k)\le \sum_{e=1}^\ell \frac{n}{p^e}.$$
Dividing by $n$ gives
$$\left(\sum_{e=1}^\ell \frac{1}{p^e}\right)-\frac{\ell}{n}\le \frac{1}{n}\sum_{k=1}^n v_p(k) \le \sum_{e=1}^\ell \frac{1}{p^e}. $$
Since $p^\ell\le n\Rightarrow \ell\le \log_p n$ we know $\ell/n\to0$ as $n\to\infty$. Squeeze theorem yields
$$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n v_p(k)=\sum_{e=1}^\infty \frac{1}{p^e}=\frac{1}{p-1}. $$
A: Oldest trick book really, can't believe I forgot! $v_2(x)$ is self-similar and satisfies,
$$(1) \quad v_2(x)=v_2(2^k-x)=v_2(2 \cdot n)-1$$
Therefore, we can build a recursive formula for the summation about powers of two.
$$(2) \quad S_{j}=2 \cdot S_{j-1}+j+1$$
Here, the index $j$ corresponds to summing up the first $2^{n+1}-1$ terms in $(1)$.
I'm skipping details, but all one has to do is show that there is a one to one correspondence between terms in the sum on the "left" and "right" side of a central point with value $j+1$. This is shown in $(1)$. All that's left is to show these central points are just $v_2(2^{n})$ and located at $2^n$.
Intuitively, the first values of $v_2(2 \cdot x)$, where x is a positive integer, are,
$$1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2...$$
Hopefully this helps illuminate the reasoning being used.
We define $S_0=1$ and we're done with the heavy lifting. The asymptotic form can be easily derived from here.
$$S_j \sim 2^j$$
If we divide by $2^{n+1}-1$ and take the limit, we get $2$!
So we can say,
$$\lim_{n \to {\infty}} {1 \over n} \cdot \sum_{k=1}^n v_2(2 \cdot k)=2$$
A: I'll just focus on this, since it basically behaves like a logarithm we can pull out all the 2s, in general we can work it out as,
$$\frac{1}{n}\sum_{k=1}^n v_p(k) = \frac{v_p(n!)}{n}$$
Now we can use Legendre's Formula to get,
$$\frac{1}{n} \frac{n - s_p(n)}{p-1}$$
$s_p(n)$ is the sum of the digits of n in base p. Doing a little algebra on it gets us,
$$\frac{1}{p-1} - \frac{s_p(n)}{n} \frac{1}{p-1}$$
At the very most, $s_p(n)$ can be the largest digit repeated for each digit all added together so it can be no larger than $(p-1)*\log_p(n)$
$$\frac{1}{p-1} - \frac{\log_p(n)}{n}$$
Taking the limit, all that's left is,
$$\frac{1}{p-1}$$
