Question (a), the decimal case, has been answered in the comments. This answer addresses question (b), the binary case.
Preliminaries
In this answer, the natural numbers $\Bbb N$ are taken to be the strictly positive integers $1,2,3,\dots$
If $n\in\Bbb N$, we use $\ell(n)$ to denote the number of digits in the binary expansion of $n$. So $2^{\ell(n)-1}\le n<2^{\ell(n)}$.
We call a (finite or infinite) sequence $(a_i)=(a_1,a_2,\ldots)$ of natural numbers valid if (i) $a_{i+1}\le 2a_i$ for all $i\in\Bbb N$, and (ii) the number of $1$'s in the binary expansion of $a_i$ is different for each element.
Given a valid sequence $(a_i)$, we can pre-process it in two ways:
- We can sort the sequence into increasing order. The resulting sequence will also be valid.
- After sorting, $\ell(a_{i+1})$ must equal $\ell(a_i)$ or $\ell(a_i)+1$ for all $i$. But the number of instances where $\ell(a_{i+1})=\ell(a_i)$ must be finite: $\ell(a_i)$ must always be $\ge i$ (because there are $i$ different $1$-counts among the elements $a_1,\ldots,a_i$), but each such instance decreases the excess $\ell(a_i)-i$ by $1$.
So if we start with an infinite valid sequence $(a_i)$, we can sort it and then discard all elements up to and including the last instance where $\ell(a_{i+1})=\ell(a_i)$; and we end up with an infinite valid sequence with strictly increasing bit lengths. We call this a lengthening sequence.
Theorem
There is no valid infinite sequence.
Proof
Suppose we have an infinite valid sequence $(a_i)$. We may suppose that it is a lengthening sequence, as defined above. Let $Z_n$ be the average number of $0$'s in the binary expansions of the $n$ integers $a_1,\ldots,a_n$, and let $k=\ell(a_1)$ be the number of digits in the binary expansion of $a_1$. Then we will show that
- $Z_n\le k-1$ for all $n$;
- $Z_n\ge k$ for all sufficiently large $n$.
This contradiction establishes the theorem.
Part I
From $\ell(a_{i+1})=\ell(a_i)+1$, we have $\ell(a_i)=k+i-1$ for all $i$. So the total number of binary digits in all the integers $a_1,\ldots,a_n$ is
$$C=\sum_{i=1}^n(k+i-1)=(k-1)n+\frac12n(n+1)$$
Of these digits, at least
$$D=\sum_{i=1}^n i=\frac12n(n+1)$$
must be $1$'s, because each $a_i$ has a different number of $1$'s.
Therefore at most $C-D=n(k-1)$ of these digits can be $0$. Hence the average number of zeroes $Z_n$ can be at most $k-1$.
Part II
Define the sequence $(x_1,x_2,\ldots)$ of real numbers by $x_i=2^{-(n+k)}a_i$. What we are doing here is mapping the sequence $(a_i)$ of integers, such as $$(1111_2,11100_2,110111_2,1100000_2,10111111_2,\ldots)$$ to the sequence $(x_i)$ of real numbers $$(0.1111_2,0.11100_2,0.110111_2,0.1100000_2,0.10111111_2,\ldots)$$ in the interval $[\frac12,1)$. This sequence is monotonic decreasing, and bounded below, therefore it has an infimum $m$. Let $m_i$ denote the $i$th binary digit after the decimal (binary?) point.
Now, if $(m_i)$ contained only a finite number of $0$'s, it would end in $...0111\ldots$ , which we can replace by $...1000\ldots$ So we can always choose the $m_i$ so that an infinite number of them are $0$. Now choose $M$ such that the number of $0$'s in the sequence $(m_1,\ldots,m_M$) (i.e. the first $M$ binary digits of $m$) is $\ge k+1$.
Because the sequence $x_i$ tends to the limit $m$ from above, there exists $N$ such that $0\le x_i-m<2^{-(N+1)}$ whenever $i\ge N$. So the first $N$ binary digits of $x_i$ and $m$ must be identical. This means that the binary expansion of $x_i$ (and therefore of $a_i$) contains at least $k+1\;$ $0$'s for all $i\ge N$. (Note: this requires the fact that we are dealing with a lengthening sequence! Otherwise $\ell(a_i)$ might be less than $k+i-1$, and we couldn't necessarily count all $0$'s in $x_i$ as $0$'s in $a_i$.) So the average number of $0$'s in the first $(k+1)N$ integers $a_i$ is at least $$\frac{(k+1)\cdot kN}{(k+1)N}=k$$
as claimed. This completes the proof.
Further thoughts
I feel that this problem shouldn't require the machinery of real analysis! But I couldn't find a combinatoric proof, despite strenuous efforts. Perhaps somebody out there can fill this gap.
If $k=4$ we have the maximal-length sequence
$$1111_2\\
11100_2\\
110111_2\\
1100000_2\\
10111111_2\\
101111100_2\\
1011110111_2\\
10111011111_2\\
101101111111_2\\
1010111111111_2\\
10011111111111_2\\
100000000000000_2$$
This was generated by following the simple rule of always choosing the largest admissible integer as the next element of the sequence; an exhaustive search was also done to prove that this is a maximal lengthening sequence.
But if we follow the same rule in the case $k=5$, we generate a sequence of length $65532$. Exhaustive search is obviously out of the question here; all I can say is, I expect that this sequence is maximal too.