ISI 2018 PCB A4

Question

Let A and B be two non-empty finite subsets of  ℤ, the set of all integers. Define A + B = { a + b : a ϵ A, b ϵ B }. Prove that | A + B | ≥ | A | + | B | - 1, where | S | denotes the cardinality of a finite set S.

Answer 1

Doing it with the help of induction on the number of elements in A.

Suppose Statement P(n) : If n be the number of elements in A and B be any non empty subset in Z then |A + B| >= |A| + |B| -1

Basis Step: To prove P(1) is true

P(1) : If there is only 1 element in A then |A + B| >= |A| + |B| -1

If there is 1 element in A then |A+B| =  |B| >= |A| + |B| -1 = |B|

Hence P(1) is true.

Inductive Hypothesis : We assume P(k) is true. That is If k be the number of elements in A then |A + B| >= |A| + |B| -1

Inductive Step : With the help of inductive hypothesis we prove that P(k+1) is true.

So, now |A| = k+1.

Now, since A is finite so A must contain a least element a_i.

Now, |A\a_i| = k .

So, from inductive hypothesis we get

|A\a_i + B| >= |A\a_i| + |B| -1 

=> |A\a_i + B| +1 >= |A\a_i| + |B| -1 +1 = |A| + |B| -1....................(1)

Now, since is finite it must contain a least element say b_i.

Note that the element (a_i + b_i) will belong to (A + B) but will not belong to (A\a_i + B)

So, |(A + B)| >= |(A\a_i + B)| + 1 ......................(2)

So, from the inequalities 1 and 2 we get

|A + B| >= |A| + |B| -1

Hence P(k+1) is true.

Thus whenever P(k) is true we will have P(k+1) is true.

Thus P(n) is true for all n belongs to Z.

Hence |A + B| >= |A| + |B| -1 is true for all non empty finite subsets of Z.

Answer 2

$\left | A + B \right | = \cup_{a\in A} \enspace \left | a+B \right | = \cup_{a\in A} \left | B \right |= \left | A \right |\left | B \right |\\[0.5cm] Now \left | A \right |\left | B \right | - \left | A \right | - \left | B \right |+1 = (\left | A \right |-1) (\left | B \right |-1)\geq 0.\\[0.5cm] Hence \left | A \right |\left | B \right | \geq \left | A \right | + \left | B \right |-1.$