# Max SAT prob- expected number of clauses

In the problem, we are given a set of clauses, and we want to find an assignment that satisfies as many of them as possible.

-

You can expand the brackets that will give you $m - \sum_{j=1}^{m}(\frac{1}{2})^{k_j}$. Now using the fact that $k_j \geq 1$ you can show that $(\frac{1}{2})^{k_j} \leq \frac{1}{2}$. Upper bound each term in the sum and you will obtain the desired inequality.
well, since each $(\frac{1}{2})^{k_j} \leq \frac{1}{2}$ then $\sum_{j=1}^{m}(\frac{1}{2})^{k_j} \leq \sum_{j=1}^{m}\frac{1}{2} \leq \frac{m}{2}$ –  Alexander Zimin Dec 3 '12 at 0:58