# Mathematical methods for economic theory

Martin J. Osborne

## 1.1 Exercises on logic: basics and proof by induction

1. A, B, and C are statements. The following theorem is true:
if A is true and B is not true then C is true.
Which of the following statements follow from this theorem?
1. If A is true then C is true.
2. If A is not true and B is true then C is not true.
3. If either A is not true or B is true (or both) then C is not true.
4. If C is not true then A is not true and B is true.
5. If C is not true then either A is not true or B is true (or both).
Only (e) follows from the theorem.

2. A and B are statements. The following theorem is true:
A is true if and only if B is true.
Which of the following statements follow from this theorem?
1. If A is true then B is true.
2. If B is true then A is true.
3. If A is not true then B is not true.
4. If B is not true then A is not true.
All four statements follow from the theorem.

3. Let G be a group of people. Assume that
for every person A in G, there is a person B in G such that A knows a friend of B.
Is it true that
for every person B in G, there is a person A in G such that B knows a friend of A?
Yes. In the first statement A and B are variables that can stand for any person; they may be replaced by any other two symbols---for example, A can be replaced by B, and B by A, which gives us the second statement.

4. Prove by induction that for every positive integer k we have
k
i=1
 1 i(i + 1)
=
 k k + 1
.
For k = 1, the left-hand side is 1/2, equal to the right-hand side. So the statement is true for k = 1.

Now assume the statement is true for k = 1, ..., n. We want to prove it is true for k = n + 1. That is, we want to prove that

n+1
i=1
 1 i(i + 1)
=
 n + 1 n + 2
.
Now, by the assumption that the statement is true for k = n, the left-hand side of this equation is
 n n + 1
+
 1 (n + 1)(n + 2)
.
After some algebra, this expression reduces to
 n + 1 n + 2
so that indeed the statement is true for k = n + 1.