prove $\sum_{i=1}^{n} \max\left\{k\in\mathbb {N} \left| \frac{i}{2^k}\in\mathbb{N} \right.\right\}=n-1$

Question

I'm trying to prove the following:

$$\sum_{i=1}^{n} \max\left\{k\in\mathbb {N} \left| \frac{i}{2^k}\in\mathbb{N} \right.\right\}=n-1 \\ \text{where}\ n=2^x,\, x\in\mathbb{N}$$

If I write down the values of $k$ in the sequence for say $n=32$ , I get $$\langle 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5\rangle$$

which do sum up to $31$. I also know that there are sixteen $1$s, four $2$s, two $3$s, one $4$, and one $5$.

However, I'm having trouble proving it. I had an idea including inclusion & exclusion principle but that didn't work that well. Any ideas?

Answer 1

Since $n = 2^x$, $$\sum_{i=1}^n \max\{k\in\mathbb{N}: \frac{i}{2^k}\in\mathbb{N}\} = \sum_{i=1}^\infty\left\lfloor \frac{n}{2^i}\right\rfloor = \sum_{i=1}^\infty\left\lfloor 2^{x-i}\right\rfloor = \sum_{i=1}^x 2^{x-i} = \frac{2^x-1}{2-1} = n-1 $$ where the first equality follows from combinatorics.

Because we can interpret the first sum as the biggest number $k$ such that $2^k$ divides $n!$, and we already have Legendre's formula.

Answer 2

You can try it using induction.

The induction hypothesis is that the sum of all terms is $n-1$. You can check this directly for $n=2$.

Let $v(t)=\max\{j\in\Bbb N:t/2^j\in\Bbb N\}$, for $t\in\Bbb N_+$.
Note that if $2^x<i<2^{x+1}$, $v(i)=v(i-2^x)$. In addition, $v(2^{x+1})=v(2^x)+1$.

Then $$\begin{align} \sum_{i=1}^{2n} v(i)&=n-1+\sum_{i=n+1}^{2n}v(i)\\ &=n-1+v(2n)+\sum_{i=1}^{n-1} v(n+i)\\ &=n-1+[1+v(n)]+\sum_{i=1}^{n-1}v(i)\\ &=n-1+1+\sum_{i=1}^{\color{red}n}v(i)\\ &=2n-1 \end{align}$$

Answer 3

Here is a bit detailed explanation using double summation.

If $k \geq 1$ and $2^k$ divides $i$, then so does $2^j$ for $1 \leq j \leq k$. So, using the indicator-function notation

$$\mathbf{1}(\cdots) = \begin{cases} 1, &\text{if $\cdots$ holds}; \\ 0, &\text{if $\cdots$ does not hold}, \end{cases}$$

then we have

$$ \max\{k \in \mathbb{N} : 2^k \text{ divides } i\} = \sum_{j\geq 1} \mathbf{1}\text{($2^j$ divides $i$)}, $$

meaning that the right-hand side counts the number of $j$'s for which $2^j$ divides $i$. Using this,

\begin{align*} S := \sum_{i=1}^{n} \max\{k \in \mathbb{N} : 2^k \text{ divides } i\} &= \sum_{i=1}^{n} \sum_{j\geq 1} \mathbf{1}\text{($2^j$ divides $i$)} \\ &= \sum_{j\geq 1} \sum_{i=1}^{n} \mathbf{1}\text{($2^j$ divides $i$)}, \end{align*}

where the last line holds because we can add (finitely many) numbers in any order we like. Also, now the inner sum counts the number of multiples of $2^j$ within $\{1, \cdots, n\}$, hence

\begin{align*} \sum_{i=1}^{n} \mathbf{1}\text{($2^j$ divides $i$)} &= \text{[# of multiples of $2^j$ in $\{1,\cdots,n\}$]} \\ &= \left\lfloor \frac{n}{2^j} \right\rfloor = \begin{cases} 2^{x-j}, & \text{if $j \leq x$}; \\ 0, & \text{if $j > x$}, \end{cases} \end{align*}

where we utilized OP's assumption $n = 2^x$ in the last step. So it follows that

\begin{align*} S = \sum_{j = 1}^{x} 2^{x-j} = 2^{x-1} + \cdots + 2^0 = 2^x - 1 = n - 1. \end{align*}