Instantly share code, notes, and snippets.

# RobertTalbert/proofv1.md Created Nov 23, 2015

What would you like to do?
Solutions to Proof assessment version 1.

# Proof assessment keys -- version 1

## Level 1

1(a): This is a proof by contradiction.

1(b): This is a direct proof.

2(a): The base case would be to prove that a one-element set has (1(1-1))/2 two-element subsets. (NOTE: There was a bit of an error here because the statement is not true for n = 0. This will be taken into account fairly in the grading process.)

2(b): Suppose that for some positive integer k, any set with k elements has k(k-1)/2 two-element subsets.

2(c): We want to prove that a set with k+1 elements has (k+1)(k)/2 two-element subsets.

3(a): We assume that ABC is not a right triangle.

3(b): We would prove that a^2 + b^2 != c^2 (where a,b,c are the side lengths).

## Level 2

1(a): Proof by contradiction, because this is not a conditional statement (there is no if-then structure) and because we are being asked to prove that something doesn't exist.

1(b): Proof by contrapositive, because it's easier to assume something about x and then prove something about x^2 - 6x + 5 than vice versa.

1(c): Induction, because the proposition pertains to proving a predicate to be true for all positive integers, and the left side of the equation in the predicate has a "recursive structure" to it -- that expression is built from smaller versions of itself.

2: The proposition is correct but the proof is incorrect. The main "killer flaw" in the proof comes in line 5 (with the displayed equation), because 5^k * 5 - 1 does not equal 5^k * 4. The multiplication takes precedence over the subtraction. Because of that computation error we can't conclude that the rightmost part of the equation is a multiple of 5.

3: The proposition is false. A counterexample would consist of A = {1,2,3} and B = {4,5,6}. Note that A - B = A, so |A - B| = 3. But |A| = 3 and |B| = 3 and therefore |A| - |B| = 0. So the two are not always equal.