Question

Show that if m and n are integers with m ≥ 3 and n ≥ 3, then R(m, n) ≤ R(m, n − 1) + R(m − 1, n)

Short answer

\(R\left( {m,n} \right) \le R\left( {m - 1,n} \right) + R\left( {m,n - 1} \right)\)

Step-by-step solution

Given

\(m\)and n are integers\(m \ge 3\)and\(n \ge 3\).

For a group of people\(\left\{ {1,2,3,........,r} \right\}\)

\(\begin{array}{l}p = R\left( {m - 1,n} \right)\\q = R\left( {m,n - 1} \right)\\r = p + q\end{array}\)

Explanation

Let L be the set of persons friends to\(1\)and M be the set of persons enemies to\(1\).

Therefore, L has at least P persons or M has at least q person.

If L has p people, then it contains a subset of \(m - 1\)persons who are mutual friends or it contains a subset of n persons who are mutual enemies .

If it contains a subset of \(m - 1\) persons who are mutual friends then \(m - 1\) person and person comprise of \(m\) person who are mutual friends.

Calculation

Therefore, a group of r people must include m mutual friends or n mutual enemies.

Therefore,

\(\begin{array}{l}R\left( {m,n} \right) \le r\\R\left( {m,n} \right) \le p + q\\R\left( {m,n} \right) \le R\left( {m - 1,n} \right) + R\left( {m,n - 1} \right)\end{array}\)

Similarly, if m has q persons then

\(R\left( {m,n} \right) \le R\left( {m - 1,n} \right) + R\left( {m,n - 1} \right)\)

Conclusion

\(R\left( {m,n} \right) \le R\left( {m - 1,n} \right) + R\left( {m,n - 1} \right)\)