I'm trying to show that: $$\sum_{k\geq1}{n \choose \left \lfloor{\log_{2}k}\right \rfloor} = 3^n$$ for all integers $k$ such that $n \geq \left \lfloor{\log_{2}k}\right \rfloor$.
Attempt: Induction. This is clearly true for $n = 0$. For $n = i + 1$, we have from Pascal's Identity ${n + 1 \choose k} = {n \choose k}{n \choose k -1}$. From the inductive hypothesis, ${n \choose k} = 3^n$, so all thats left to show is that the "leftover" parts of the sum equal $2\times 3^n$.
HINT: You don’t need induction. If $0\le\ell$, then $\lfloor\lg k\rfloor=\ell$ for all $k$ satisfying $2^\ell\le k<2^{\ell+1}$, and there are $2^\ell$ such values of $k$, so
$$\sum_{k=2^\ell}^{2^{\ell+1}-1}\binom{n}{\lfloor\lg k\rfloor}=\binom{n}{\ell}2^\ell\;.$$
Thus,
$$\sum_{k\ge 1}\binom{n}{\lfloor\lg k\rfloor}=\sum_{\ell\ge 0}\binom{n}\ell 2^\ell\;.$$
Now simplify that righthand side.
(My $\lg k$ is your $\log_2k$; it’s a standard notation, and it’s handy when one is mostly working with binary logs.)