Greedy algorithm for Set Cover problem - need help with approximation
You have shown that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then the greedy algorithm finds $k$ sets which cover at least $n/2$ elements, and so at most $n/2$ elements are left uncovered. You can prove by induction that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then for each $t$, the first $tk$ sets found by the greedy algorithm cover all but at most $n/2^t$ elements. The idea now is to pick a value of $t$ such that $n/2^t &lt; 1$. Since the number of elements left uncovered by the algorithm is an integer, if the number $m$ of elements left uncovered satisfies $m &lt; 1$, then in fact $m = 0$, i.e., all elements are covered.

As a side note, you can actually improve on your reasoning and show that the first $k$ sets cover at least $(1-1/e)n$ elements, and so leave only $n/e$ elements uncovered. This improves the bound from your $k\log_2 n$ to the sharp $k\ln n$, which is known to be tight (unless P=NP).