How do we prove the following?

Question

The expression is:

a₁ | a₂ |⋯| a_n ≤ a₁ + a₂ +⋯+ a_n , where '|' denotes the Bitwise OR operator

Answer 1

By definition, each bit of the OR of two numbers is independent from each other. That is,

$$\left(\sum_{i=0}^N a_i2^i\right) \mid \left(\sum_{i=0}^N b_i2^i\right) = \sum_{i=0}^N (a_i \mid b_i) 2^i$$

So it suffices to show this for $a_i, b_i \in \{0, 1\}$. However, that is easy, since

1. For $a_i = b_i = 0$, $a_i \mid b_i = 0 \leq 0 + 0 = 0$.
2. For $a_i = 0, b_i = 1$ or the other way around, $a_i \mid b_i = 1 \leq 0 + 1 = 1$.
3. For $a_i = b_i = 1$, $a_i \mid b_i = 1 \leq 1 + 1 = 2$.

---

With a similar proof, you have $a + b = (a \mid b) + (a \& b)$ where $\&$ is the bitwise AND operation.

From this, use induction.