Mathematical methods for economic theory

Martin J. Osborne
Previous section Previous page Contents Text Exercises Search Next page Next section

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).

    Solution

    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.

    Solution

    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?

    Solution

    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
    		.

    Solution

    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.