Your proposed formula is always true. To show this, first to reduce the algebra involved, define
$$m = \lfloor \log_2 n \rfloor, \; \; j = \nu_2(n) \tag{1}\label{eq1A}$$
Since $m$ is the index of the largest non-zero binary coefficient of $n$, this means
$$n = \sum_{i = 0}^{m}c_i 2^i, \; 0 \le c_i \le 1 \; \forall \; 0 \le i \le m \tag{2}\label{eq2A}$$
With just the first floor function value which is being summed, using \eqref{eq2A} gives
$$\begin{equation}\begin{aligned}
\left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor & = \left\lfloor\frac{\sum_{i = 0}^{m}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\
& = \left\lfloor\frac{\sum_{i = k+1}^{m}c_i 2^{i+1} + \sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\
& = \left\lfloor\frac{\sum_{i = k+1}^{m}c_i 2^{i+1}}{2^{k+2}} + \frac{\sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\
& = \left\lfloor\sum_{i = k+1}^{m}c_i 2^{(i+1) - (k+2)} + \frac{\sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\
& = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + \left\lfloor\frac{\sum_{i = 0}^{k}c_i 2^{i+1} + 2^{k+1} - 1}{2^{k+2}}\right\rfloor \\
& = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + \left\lfloor\frac{(c_k + 1)\left(2^{k+1}\right) + (\sum_{i = 0}^{k - 1}c_i 2^{i+1} - 1)}{2^{k+2}}\right\rfloor \\
\end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Note the numerator of the fraction in \eqref{eq3A} is greater than or equal to $2^{k+2}$ iff $c_k = 1$ and there's at least one $c_i = 1$ for some $0 \le i \le k - 1$, with the latter condition only being true if $k \gt j$. To make this simpler to handle, define a boolean type indicator function of
$$B(e) = \begin{cases}
0 & e \text{ is false} \\
1 & e \text{ is true}
\end{cases} \tag{4}\label{eq4A}$$
Using this function, \eqref{eq3A} can be simplified to
$$\left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + c_{k}B(k \gt j) \tag{5}\label{eq5A}$$
The second floor function being summed is basically the same, but with the powers of $2$ being $1$ larger, so it becomes
$$\left\lfloor\frac{2n - 1 + 2^{k+2}}{2^{k+3}}\right\rfloor = \sum_{i = k+2}^{m}c_i 2^{i-k-2} + c_{k+1}B(k + 1 \gt j) \tag{6}\label{eq6A}$$
With the third floor function which is summed, all of the terms with powers of $2$ less than $k + 2$ become part of the fraction, so the result is
$$\left\lfloor\frac{n}{2^{k+2}}\right\rfloor = \sum_{i=k+2}^{m}c_i 2^{i-k-2} \tag{7}\label{eq7A}$$
Using \eqref{eq5A}, \eqref{eq6A} and \eqref{eq7A} gives
$$\begin{equation}\begin{aligned}
& \left\lfloor\frac{2n - 1 + 2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2n - 1 + 2^{k+2}}{2^{k+3}}\right\rfloor - \left\lfloor\frac{n}{2^{k+2}}\right\rfloor \\
& = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + c_{k}B(k \gt j) - \left(\sum_{i = k+2}^{m}c_i 2^{i-k-2} + c_{k+1}B(k + 1 \gt j)\right) - \sum_{i=k+2}^{m}c_i 2^{i-k-2} \\
& = \sum_{i = k+1}^{m}c_i 2^{i-k-1} + c_{k}B(k \gt j) - 2\sum_{i = k+2}^{m}c_i 2^{i-k-2} - c_{k+1}B(k + 1 \gt j) \\
& = \left(c_{k+1} + \sum_{i = k+2}^{m}c_i 2^{i-k-1}\right) - \sum_{i = k+2}^{m}c_i 2^{i-k-1} + c_{k}B(k \gt j) - c_{k+1}B(k + 1 \gt j) \\
& = c_{k+1} - c_{k+1}B(k + 1 \gt j) + c_{k}B(k \gt j) \\
& = (1 - B(k + 1 \gt j))c_{k+1} + c_{k}B(k \gt j)
\end{aligned}\end{equation}\tag{8}\label{eq8A}$$
Letting the result be $r$, using \eqref{eq2A} and \eqref{eq8A} gives
$$\begin{equation}\begin{aligned}
r & = n - \sum_{k=0}^{\lfloor \log_2{n} \rfloor}\left(\left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2n-1+2^{k+2}}{2^{k+3}}\right\rfloor - \left\lfloor \frac{n}{2^{k+2}} \right\rfloor\right)2^k \\
& = \sum_{k = 0}^{m}c_k 2^k - \sum_{k = 0}^{m}\left((1 - B(k + 1 \gt j))c_{k+1} + c_{k}B(k \gt j)\right)2^k \\
& = \sum_{k = 0}^{m}\left(c_k - ((1 - B(k + 1 \gt j))c_{k+1} + c_{k}B(k \gt j))\right)2^k \\
& = \sum_{k = 0}^{m}\left((1 - B(k \gt j))c_{k} - (1 - B(k + 1 \gt j))c_{k+1}\right)2^k
\end{aligned}\end{equation}\tag{9}\label{eq9A}$$
If $n$ is odd, then $c_0 = 1$ and $j = 0$. Thus, $B(k \gt j)$ is $0$ only for $k = 0$, and $1$ otherwise. In addition, $B(k + 1 \gt j)$ would always be $1$. This means the coefficient of $c_{k}$ is $1$ only for $k = 0$, while $c_{k+1}$'s coefficient is always $0$. This gives $r = c_{0}2^{0} = 1$.
With $n$ being even, then $j \gt 0$. Since $c_k = 0$ for $k \lt j$, and $1 - B(k \gt j) = 0$ for $k \gt j$, the only non-zero value of $(1 - B(k \gt j))c_{k}$ is $c_j$ for $k = j$. Similarly, the only non-zero value of $(1 - B(k + 1 \gt j))c_{k + 1}$ is $c_j$ for $k + 1 = j \implies k = j - 1$. As such, in \eqref{eq9A}, the only non-zero summation terms are for $k = j - 1$ and $k = j$, giving
$$\begin{equation}\begin{aligned}
r & = (0 - c_j)2^{j-1} + (c_j - 0)2^{j} \\
& = (0 - 1)2^{j-1} + (1 - 0)2\left(2^{j-1}\right) \\
& = 2^{j-1} \\
& = 2^{\nu_2(n) - 1}
\end{aligned}\end{equation}\tag{10}\label{eq10A}$$
You’re not wrong, but your result does not contradict the assertion that $$\operatorname{bits}(\lfloor x/2\rfloor)\le\operatorname{bits}(x)-1\,:$$ after all, if $a=b$, then it’s certainly also true that $a\le b$. However, I have to admit that I don’t see why the author chose to state the weaker conclusion, since the stronger one follows easily from his own calculations:
$$\begin{align*}
\operatorname{bits}(\lfloor x/2\rfloor)&=\lfloor\log_2(x/2)\rfloor+1\\
&=\lfloor\log_2x-1\rfloor+1\\
&=\lfloor\log_2x\rfloor-1+1\\
&=\operatorname{bits}(x)-1\,.
\end{align*}$$
Yes, he really ought either to restrict himself to integers $x\ge 2$ or mention that $x=1$ is an exception, though in practice I doubt that the oversight will cause much trouble.
Best Answer
Note that as lulu's comment suggests, the expression simplifies to
$$mt^2 + 2rt + \left\lfloor\frac{r^2}{m}\right\rfloor$$
For $n \le 3$, have $t = 0$, so the result is $\left\lfloor\frac{r^2}{m}\right\rfloor$. Then for $n = 1$, we can use $m = 3$, $r = 2$. With $n = 2$, there's $m = 4$, $r = 3$. Finally, for $n = 3$, we can use $m = 5$, $r = 4$.
With $n \gt 3$, using $t = r = 1$ and $m = n - 2$, since $m \gt 1$ so $\frac{r^2}{m} \lt 1 \;\to\; \left\lfloor\frac{r^2}{m}\right\rfloor = 0$, the above expression becomes
$$(n - 2)(1^2) + 2(1)(1) + 0 = n$$
Alternatively, as indicated in peterwhy's comment, a somewhat simpler solution which works for all $n \ge 1$ is to use $m = n + 2$, $t = 0$ and $r = m - 1$ which gives
$$\left\lfloor\frac{(m - 1)^2}{m}\right\rfloor = m - 2 + \left\lfloor\frac{1^2}{m}\right\rfloor = (n + 2) - 2 + 0 = n$$
For the more general case of your extended question, i.e., expressing all positive integers $n$ in the form
$$n = \left\lfloor\frac{(mt+r)^k}{m}\right\rfloor$$
for a fixed positive integer $k$, this can also always be done. For $k = 1$, choose $t = n$, $m = 2$ and $r = 1$. For $k \ge 2$, using $t = 0$, we get
$$n = \left\lfloor\frac{r^k}{m}\right\rfloor$$
Choose any positive integer $r$ where $r \ge n - 1$ and $r^{k} \ge (r + 1)n$. Then there's an integer $m \ge r + 1 \;\to\; r \le m - 1 \;\to\; n \le m$, and an integer $0 \le a \lt n \;\to\; 0 \le a \lt m$, where
$$r^k = mn + a \;\;\to\;\; \frac{r^k}{m} = n + \frac{a}{m} \;\;\to\;\; \left\lfloor\frac{r^k}{m}\right\rfloor = n$$