How to show $n=1+\sum_{k=1}^{n}\left\lfloor{\log_2\frac{2n-1}{2k-1}}\right\rfloor$ for every natural number $n$.

A Combinatorial Proof:

We are going to count the number of even numbers in the interval $[1,2n-1]$ in two different methods.

Counting in method 1: There are exactly $n-1$ even numbers in the interval $[1,2n-1]$ namely $2,4,\ldots,2n-2$.

Counting in method 2: Note that every even number can be represented as $2^am$ where $a\geq1$ and $m$ is odd. Clearly even numbers which are less than $2n-1$ must have odd parts less than $2n-1$. Let $N_k$ denote the number of even numbers in the interval $[1,2n-1]$ which have odd part $2k-1$. Therefore $$n-1=\sum_{k=1}^{n}N_k\tag{1}$$ Clearly $N_k$ is the largest integer $l$ such that $2^l(2k-1)\leq2n-1$ or equivalently $$N_k=\left\lfloor\mathrm{log}_2\frac{2n-1}{2k-1}\right\rfloor$$ Therefore we get from $(1)$, $$n-1=\sum_{k=1}^{n}\left\lfloor\mathrm{log}_2\frac{2n-1}{2k-1}\right\rfloor\\\implies n=1+\sum_{k=1}^{n}\left\lfloor\mathrm{log}_2\frac{2n-1}{2k-1}\right\rfloor$$

I don't know any way to solve this using Legendre's formula (including its alternate form) or any other similar method. Instead, this can be solved by using mathematical induction. Note that your requested formula of

$$n = 1 + \sum_{k \, = \, 1}^{n} \left\lfloor \log_{2}\cfrac{2n - 1}{2k - 1} \right\rfloor \tag{1}\label{eq1}$$

works for $n = 1$ as it becomes just simply $n = 1 + \left\lfloor \log_{2}\cfrac{2 - 1}{2 - 1} \right\rfloor = 1 + 0 = 1$. Assume \eqref{eq1} works for all $n <= m$ for some natural number $m$. To prove it works for $n = m + 1$, there are $3$ specific things to note.

1. Going from $n = m$ to $n = m + 1$ involves summing one extra term, with the final term always being $0$ as it is $\left\lfloor \log_{2}\cfrac{2m + 1}{2m + 1} \right\rfloor$.
2. For each term in both summations, i.e., for $k = 1, 2, 3, \ldots, m$, the value is non-decreasing, i.e., $\left\lfloor \log_{2}\cfrac{2m + 1}{2k - 1} \right\rfloor \ge \left\lfloor \log_{2}\cfrac{2m - 1}{2k - 1} \right\rfloor$, since $\log_{2}$ is an increasing function.
3. Based on the above considerations, to prove that \eqref{eq1} works, it's required need to show exactly one of the terms always increases by exactly $1$.

For any $1 \leq k \leq m$,

$$\left\lfloor \log_{2}\cfrac{2m - 1}{2k - 1} \right\rfloor = j \tag{2}\label{eq2}$$

for some integer $j \ge 0$, means

$$2^j \leq \cfrac{2m - 1}{2k - 1} \lt 2^{j + 1} \tag{3}\label{eq3}$$

Note the "$\leq$" is only needed for $j = 0$, else it can be just "$\lt$" instead as the numerator and denominator of $\cfrac{2m - 1}{2k - 1}$ are odd integers and, thus, their division can't be an even integer. In a similar fashion, consider if for any specific $k$ gives

$$\left\lfloor \log_{2}\cfrac{2m + 1}{2k - 1} \right\rfloor = j + 1 \tag{4}\label{eq4}$$

then you also have

$$2^{j + 1} \lt \cfrac{2m + 1}{2k - 1} \lt 2^{j + 2} \tag{5}\label{eq5}$$

Note the increase will not be by more than $1$ since, even for $k = 1$, going from $2m - 1$ to $2m + 1$ is not sufficient for such an increase. Since $2k - 1 \gt 0$, multiplying everything in both \eqref{eq3} and \eqref{eq5} by $2k - 1$ and combining the $2$ equations through their common $2^{j + 1}$ value gives

$$2m - 1 \lt 2^{j + 1}\left(2k - 1\right) \lt 2m + 1 \tag{6}\label{eq6}$$

This shows $2^{j + 1}\left(2k - 1\right)$ must be the sole even integer between the $2$ consecutive odd integers of $2m - 1$ and $2m + 1$. This even integer is $2m$, with $j + 1$ being the power of $2$ of the factorization of it and $2k - 1$ being the odd part of the integer. This confirms there always exists one, and only one, such value which will increase by $1$, as the steps are reversible. As such, this means by the inductive step that \eqref{eq1} works for $n = m + 1$ as well, thus finishing the proof by induction.

As an example, consider the case of $n = 5$ going to $n = 6$, so $2n - 1$ goes from $9$ to $11$. The value in between is $10 = 2 \times 5$. Thus, $j = 0$ here and $2k - 1 = 5$, so $k = 3$. This indicates that the $3$rd summation term, and no other, will increase by $1$, going from $0$ to $1$. First, here are the terms for $n = 5$

\begin{align} 5 & = 1 + \left\lfloor \log_{2} \cfrac{9}{1} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{3} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{5} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{7} \right\rfloor + \left\lfloor \log_{2} \cfrac{9}{9} \right\rfloor \\ & = 1 + 3 + 1 + 0 + 0 + 0 \tag{7}\label{eq7} \end{align}

Next, here are the terms for $n = 6$

\begin{align} 6 & = 1 + \left\lfloor \log_{2} \cfrac{11}{1} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{3} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{5} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{7} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{9} \right\rfloor + \left\lfloor \log_{2} \cfrac{11}{11} \right\rfloor \\ & = 1 + 3 + 1 + 1 + 0 + 0 + 0 \tag{8}\label{eq8} \end{align}

The final lines of \eqref{eq7} and \eqref{eq8} show that, as predicted, the $3$rd summation term is the only one to change, going up by $1$ from $0$ to $1$.