How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$
Here is the idea. When $n$ is even,
$$ \frac{T(n)}{n} \approx \frac{1}{2} \frac{T(n/2)}{n/2}. $$
In contrast, when $n$ is odd,
$$ \frac{T(n)}{n} \approx \frac{T(\lfloor n/2 \rfloor)}{\lfloor n/2 \rfloor}, $$
due to the factor 2 in the recurrence.
This suggests that in order to find your set $X$, you want to hit the &quot;odd&quot; case all the way. If $m = \frac{n-1}{2}$ then $n = 2m+1$, so if $m$ is a good choice, so is $n$. This suggests considering the sequence defined by $n_0 = 1$ and $n_{t+1} = 2n_t+1$, which is $1,3,7,15,\ldots$. As you can see, $n_t = 2^{t+1}-1$. The value of $T$ on this sequence is $1,2,4,8,\ldots$, that is, $T(n_t) = 2^t$.
We can now prove by induction that $T(2^{t+1}-1) = 2^t$. When $t = 0$, this just states the base case $T(1) = 1$. When $t &gt; 0$,
$$
T(2^{t+1}-1) = 2T\left(\frac{2^{t+1}-2}{2}\right) = 2T(2^t-1) = 2\cdot 2^{t-1} = 2^t.
$$
Finally, note that
$$
T(2^{t+1}-1) = 2^t \geq \frac{1}{2} (2^{t+1}-1),
$$
and so you can take $X = \{ 2^{t+1}-1 : t \in \mathbb N \}$ as your infinite set.