Proof-Based Math for Beginners

• A mathematical statement is a sentence that has a definite truth value: it is either true or false. "2 + 2 = 4" is a statement, and "x + 2 = 4" is not a statement by itself because it depends on what x is. Math cares a lot about being precise about what is being claimed, so we separate statements from expressions, questions, and commands. Many statements come with conditions like "if..." or with hidden assumptions like "let x be a real number." When you read a sentence in math, your first job is to ask: does it claim something that can be checked as true or false given the rules of the system?
• A key idea is the difference between proving and disproving. A universal claim like "all integers have property P" is disproved by finding one counterexample, a single integer that fails the property. But proving a universal claim is harder: you must give a reasoning chain that works for every allowed input, not just examples. This is why proofs rely on definitions and algebraic steps rather than checking cases randomly. Beginners often mistake "I tested it a few times" for proof. Testing builds intuition, but a proof is what guarantees the claim for all cases.

• "2 + 2 = 4" is a statement (true).
• "x + 2 = 4" is not a statement (depends on x).
• "For all real x, x + 2 > x" is a true statement.

Classify each as statement or not. If statement, say true or false.

• 19 is prime
• 2What time is it
• 3For all integers n, n^2 >= n
• 4x^2 = 9
• 5There exists an integer n with n^2 = 2
• 6If it rains, the ground is wet
• 7Every even integer is divisible by 4
• 80 < 1

MCQ

Which is a statement?

• Quantifiers tell you the scope of a claim. "For all" (written forall) means a property holds for every element in a specified set, like "for all integers n." "There exists" (written exists) means at least one element has the property, like "there exists an integer n such that..." The set matters: "there exists a real x with x^2 = 2" is true, but "there exists an integer x with x^2 = 2" is false. When translating English into math, identify (1) the set you are talking about, (2) whether the claim is for all or there exists, and (3) the exact property being asserted.
• The order of quantifiers can completely change meaning. Compare "for every x, there exists a y" (forall x exists y) with "there exists a y such that for every x" (exists y forall x). Example: "For every real x, there exists a real y with y > x" is true, but "There exists a real y such that for every real x, y > x" is false (no single number is bigger than every real number). Good proof writing starts with correctly expressing claims, because if you misunderstand the quantifiers, you can prove the wrong thing perfectly.

• Every integer has a successor: forall n in Z, exists m in Z such that m = n + 1.
• Some integer is even: exists n in Z such that n is even.

Translate to symbols.

• 1Every real number has a square that is nonnegative.
• 2Some integer is divisible by 7.
• 3For every integer n, there exists an integer k with n = 2k or n = 2k + 1.
• 4There exists a real x such that for all real y, x <= y.

MCQ

Which translation matches 'Every integer has a successor'?

• Negation is how you correctly express "the opposite" of a statement, and it is essential for contradiction proofs and for spotting counterexamples. The most important rule is that negation flips quantifiers: the negation of "for all x, P(x)" is "there exists an x such that not P(x)." Symbolically, not (forall x P(x)) is equivalent to exists x not P(x). Similarly, not (exists x P(x)) is equivalent to forall x not P(x). This matches common sense: to deny "everyone passed," you only need "someone failed," and to deny "someone passed," you need "no one passed."
• You also need De Morgan's laws for combining statements. The negation of "P and Q" is "not P or not Q," and the negation of "P or Q" is "not P and not Q." Beginners often negate incorrectly by keeping the same connector. Finally, be careful with inequalities: the negation of "x >= 3" is "x < 3," and the negation of "x > 3" is "x <= 3." Correct negations matter because they tell you exactly what must be shown to disprove a claim or what assumption you take on when proving by contradiction.

• Negate 'For all integers n, n is even': 'There exists an integer n that is not even.'
• Negate 'There exists x such that x^2 = 2' (over integers): 'For all integers x, x^2 != 2.'

Negate each carefully.

• 1For all real x, x^2 >= 1
• 2There exists an integer n such that n is prime and n is even
• 3For every student s, there exists a class c that s has taken
• 4There exists x in R such that for all y in R, x + y = y

MCQ

What is the negation of 'For all real x, x^2 >= 1'?

• Most beginner proofs follow a predictable structure: start with an arbitrary object, rewrite assumptions using definitions, then manipulate until you reach the conclusion. For example, to prove "if n is even then n^2 is even," you begin by letting n be even, which by definition means n = 2k for some integer k. That definition is powerful because it turns a word ("even") into algebra you can use. Once you rewrite in definitional form, the proof often becomes straightforward algebra: n^2 = (2k)^2 = 4k^2 = 2(2k^2), which matches the definition of even again.
• Disproving is different: to refute a "for all" claim, you only need one counterexample, and the best counterexamples are simple and decisive. If someone claims "all primes are odd," the number 2 instantly kills it. If someone claims "for all integers n, n^2 > n," then n = 0 or n = 1 refutes it. Learning when to prove and when to counterexample is a core skill: your first step should always be identifying whether a statement is universal (needs proof, vulnerable to counterexample) or existential (needs an example or construction).

• If n is even then n^2 is even (direct proof with n = 2k).
• Disprove 'for all integers n, n^2 > n' with n = 0.

• 1Prove: If n is odd, then n^2 is odd.
• 2Disprove: For all integers n, 2n + 1 is even.
• 3Prove: For all real numbers x, x^2 >= 0.

• 1Translate: 'Every integer has an additive inverse.'
• 2Negate: 'There exists a real x such that x^2 < 0.'
• 3Give a counterexample to: 'All primes are odd.'

MCQ

Which is a valid counterexample to 'For all integers n, n^2 > n'?

• An implication has the form P -> Q, read "if P then Q." P is the hypothesis and Q is the conclusion. The most common beginner mistake is confusing an implication with its converse. "If it's a square, then it's a rectangle" is true, but "if it's a rectangle, then it's a square" is false. In proofs, you should treat an implication as a promise: you are allowed to assume P, and your job is to logically derive Q. Also note that P -> Q is considered true whenever P is false, which is why we focus on situations where P actually holds.
• A key technique is proving an implication by proving its contrapositive because the contrapositive is logically equivalent and often easier. The contrapositive of P -> Q is not Q -> not P. Example: proving "if n^2 is even then n is even" is tricky directly, but the contrapositive "if n is odd then n^2 is odd" is straightforward using n = 2k + 1. In practice, when the conclusion is a "simple" property (like evenness) and the hypothesis is "complicated" (like n^2 is even), contrapositive is often the cleanest route.

• If n^2 is even then n is even (proved by contrapositive: odd n gives odd n^2).

• 1Write the contrapositive: If a number is divisible by 4, then it is even.
• 2Is the converse true? If a number is even then divisible by 4?
• 3Prove: If n is divisible by 6, then n is divisible by 3.

MCQ

What is the contrapositive of 'If a number is divisible by 4, then it is even'?

• A statement of the form P iff Q (P <-> Q) means two implications at once: P -> Q and Q -> P. This is why "iff" proofs always have two directions, usually labeled "(->)" and "(<-)" or "(1)" and "(2)." The mindset is: you are proving equivalence, so you must show each condition guarantees the other. If you only prove one direction, you have not proved "iff," you have proved only a one-way implication.
• Good "iff" proofs lean heavily on definitions and known lemmas. For example, "n is even iff n^2 is even" is proven by two short pieces: (->) even implies square even by substituting n = 2k, and (<-) square even implies even by a contrapositive or a separate lemma. Many math definitions are iff statements, like "n is odd iff n = 2k + 1 for some integer k." Treating "iff" properly also prevents logical errors in algebraic manipulation, where people assume they can reverse steps that are not reversible.

• An integer n is even iff n^2 is even (prove both directions).

• 1Prove: n is odd iff n^2 is odd.
• 2Prove: n is divisible by 5 iff its last digit is 0 or 5 (or prove the easy direction).

MCQ

To prove P iff Q, what must you show?

• Proof by cases is used when the universe naturally splits into a small number of exhaustive and non-overlapping possibilities. You prove the desired conclusion separately in each case, and because every object falls into one of the cases, the conclusion holds universally. Typical splits include: integer is even or odd, real number is >= 0 or < 0, and a set element is in A or not in A. The crucial requirement is exhaustiveness. If your cases do not cover every possibility, the proof is incomplete.
• A classic example is proving that n(n+1) is even for every integer n. The cases are: n is even, so the product is even, or n is odd, so n+1 is even, so the product is even. Case proofs are especially common when working with parity and modular arithmetic, because "mod m" arguments often reduce to checking a small set of residues. The main writing skill here is clarity: state the cases explicitly, finish each case cleanly, and then conclude that since the cases cover all possibilities, the claim is proven.

• For every integer n, n(n+1) is even (case on n even or odd).

• 1Prove: For every integer n, n^2 and n have the same parity.
• 2Prove: |x| >= 0 for all real x (cases x >= 0 and x < 0).

MCQ

Which case split is most natural to prove |x| >= 0 for all real x?

• Proof by contradiction is used when it is hard to build the object directly or when the statement claims something cannot exist. The structure is: assume the negation of what you want to prove, then logically derive a contradiction, meaning you reach something impossible (like 1 = 0) or you violate a known fact or definition. Since the assumption leads to impossibility, it must be false, so the original statement is true. This method depends on having correct negations, especially with quantifiers and inequalities.
• The classic beginner example is proving sqrt(2) is irrational. You assume the opposite, that sqrt(2) = a/b in lowest terms, then algebra forces a and b to both be even, contradicting the assumption that the fraction was reduced. Contradictions often emerge from parity (even/odd), divisibility, ordering (smaller than smallest), or minimality (choosing a smallest counterexample). A good contradiction proof clearly marks the assumption, shows the chain of reasoning, and explicitly identifies the contradiction at the end.

• There is no smallest positive real number (assume s, then s/2 is smaller).

• 1Prove: sqrt(2) is irrational.
• 2Prove: There is no integer n such that n^2 = 2.

• 1Give the contrapositive of: If x is a multiple of 8, then x is divisible by 4.
• 2Prove or disprove: If n^2 is divisible by 3 then n is divisible by 3.

MCQ

Which proof method starts by assuming the negation and reaching a contradiction?

• Set proofs are usually done by element-chasing, which means you prove membership statements by tracking what it means to belong to a set. To prove A subseteq B, you start with "Let x be an arbitrary element of A" and then use the definition of A to show x must be in B. This is the set version of a direct proof: assume membership in the left set, derive membership in the right set. Similarly, to prove two sets are equal, you show both inclusions: A subseteq B and B subseteq A.
• The operations union, intersection, and difference translate into logical connectors. x in A union B means x in A or x in B. x in A intersect B means x in A and x in B. x in A \ B means x in A and not in B. Once you write membership in logic form, the proof often becomes a logic exercise. The main discipline is writing each step explicitly: state what membership gives you, transform it, then repackage it as membership in the target set.

• A intersect B subseteq A: if x in A intersect B, then x in A.

• 1Prove: A intersect B subseteq B
• 2Prove: A subseteq A union B
• 3Prove: If A subseteq B and B subseteq C, then A subseteq C

MCQ

To prove A subseteq B, you should start with:

• Set identities like A intersect (B union C) = (A intersect B) union (A intersect C) are proven by showing both directions using element-chasing. For the "subseteq" direction, assume x is in the left side, translate that into logical form, then deduce x satisfies the right-side condition. For the "supseteq" direction, assume x is in the right side and reverse the logic. This is similar to proving "iff" statements because equality of sets is equivalent to "x is in the left iff x is in the right."
• De Morgan's laws for sets match De Morgan's laws for logic. For example, the complement of a union is the intersection of complements, and the complement of an intersection is the union of complements. For difference, A \ (B union C) equals (A \ B) intersect (A \ C). These identities become almost automatic if you always translate set membership into "and/or/not." The deeper skill here is learning to move fluently between set notation and logic, because many later topics (probability, analysis, abstract algebra) use the same pattern.

• 1Prove: A intersect (B union C) = (A intersect B) union (A intersect C)
• 2Prove: A \ (B union C) = (A \ B) intersect (A \ C)

MCQ

To prove A intersect (B union C) = (A intersect B) union (A intersect C), you must:

• A function f: A -> B assigns each input in A exactly one output in B. The set A is the domain and B is the codomain. A function is injective (one-to-one) if different inputs can't map to the same output. The standard proof format is: assume f(a) = f(b) and then show a = b. A function is surjective (onto) if every element of the codomain is hit: for each y in B, there exists x in A such that f(x) = y. The proof format is constructive: start with an arbitrary y, then solve f(x)=y for x and show that x lies in the domain.
• A function is bijective if it is both injective and surjective. Bijectivity matters because bijections are exactly the functions that have inverses. Many beginner mistakes come from mixing up domain and codomain. For example, f(x)=x^2 from R to R is not surjective because negative numbers are not hit, but from R to [0, infinity) it is surjective. Function proofs are often algebra plus careful attention to where variables live. The point is not complicated computation. It's demonstrating logical control over definitions.

• f(x) = 2x + 1 from Z to Z is injective.

• 1Show f(x) = x^2 from R to R is not injective.
• 2Show f(x) = x^3 from R to R is bijective.
• 3Determine if f(x) = 2x from Z to Z is surjective.

MCQ

The function f(x) = x^2 from R to R is:

• Function composition is defined by (f o g)(x) = f(g(x)). Composition is a way to build complex functions from simpler ones, and many proof properties behave nicely under composition. For instance, if f and g are injective, then f o g is injective, because equality of outputs forces equality step-by-step going backward through g and then through f. If f and g are surjective, then f o g is surjective, because you can hit any target y by first finding an input for f and then finding an input for g.
• An inverse function f^-1 exists exactly when f is bijective. The defining property is f^-1(f(x)) = x for all x in the domain and f(f^-1(y)) = y for all y in the codomain. Proving something is an inverse is usually done by verifying these two identities. Beginners often treat inverses as automatic algebraic "undoing," but that only works if the function is one-to-one and onto in the specified sets. Thinking set-theoretically about inverses prevents errors like claiming x^2 has an inverse on all real numbers.

• 1If f and g are injective, prove f o g is injective.
• 2If f and g are surjective, prove f o g is surjective.
• 3Give an example where f o g is bijective but f is not bijective (codomains differ).

• 1Prove: A subseteq B implies A union C subseteq B union C.
• 2Decide if f(x) = x^2 from R to [0, infinity) is surjective.

MCQ

If f and g are injective, then f o g is:

• Divisibility is a definition disguised as notation. Saying a divides b (a | b) means there exists an integer k such that b = ak. Almost every divisibility proof starts by rewriting using that definition, because it converts a statement about divisibility into an algebra statement about multiples. For example, to show a | (b + c) given a | b and a | c, you write b = ak and c = al, then add them to get b + c = a(k + l), which matches the definition again.
• Divisibility proofs often involve closure properties: multiples of a stay multiples of a under addition and under multiplication by integers. You also learn transitivity: if a|b and b|c then a|c, because c = bq = (ap)q = a(pq). The key writing skill is keeping track of which numbers are integers, because divisibility lives in the integers. Whenever you introduce a k from "a|b," explicitly state k is an integer. That small habit prevents many hidden logical gaps.

• If a | b and a | c then a | (b + c): b = ak, c = al, so b + c = a(k + l).

• 1If a | b then a | bc for any integer c.
• 2If a | b and b | c then a | c.
• 3If a | b and a | c then a | (mb + nc) for integers m, n.

MCQ

The statement a | b means:

• A prime is a positive integer p > 1 whose only positive divisors are 1 and p. Prime numbers are central because they behave like "atomic" divisibility objects. A major tool is Euclid's Lemma: if p is prime and p | ab, then p | a or p | b. This is not true for non-primes. For example, 6 | (2*3) but 6 does not divide 2 or 3. Euclid's Lemma is what makes prime factorization and many number theory arguments work.
• At a beginner level, you can treat Euclid's Lemma as a theorem you are allowed to use, but it's still important to know how it is used: it lets you pull a prime divisor out of a product. For instance, if p | a^2, then p | a because a^2 = a*a and the lemma says p divides one of the a's, which is the same as p | a. As you get further, you'll connect this to gcd arguments and Bezout's identity, but early on the main goal is learning how primes interact with products in proofs.

• 1Prove: If p is prime and p | a^2 then p | a.
• 2Prove: If gcd(a,b) = 1 and a | bc then a | c.

MCQ

Euclid's Lemma says: if p is prime and p | ab, then:

• Modular arithmetic formalizes "same remainder." The statement a == b (mod m) means m divides (a - b), so a and b differ by a multiple of m. This definition is powerful because it turns a remainder claim into a divisibility claim, letting you use algebra safely. Once you know a == b (mod m), you can add the same number to both sides and keep congruence, subtract, and multiply, because these operations preserve the "difference is a multiple of m" property.
• The main beginner technique is reducing complicated expressions to small cases. For example, mod 2 there are only two residues: 0 and 1, corresponding to even and odd. Mod 4 there are residues 0,1,2,3, which lets you prove statements about squares by checking a small set of cases. Always be explicit about the modulus and what it means. Writing "mod m" without stating the definition is how mistakes happen. If you can restate congruence as "m | (a-b)" on demand, you are doing modular arithmetic correctly.

• 1Show: if a == b (mod m) then a + c == b + c (mod m).
• 2Compute: 17 mod 5 and 100 mod 7.
• 3Prove: if n is odd then n == 1 (mod 2).

MCQ

a == b (mod m) means:

• Many "impossibility" number theory proofs come from restricting what values are possible modulo a small number. A famous example: for any integer n, n^2 == 0 or 1 (mod 4). The proof is by cases on parity. If n is even, n = 2k, so n^2 = 4k^2 == 0 (mod 4). If n is odd, n = 2k + 1, so n^2 = 4k(k+1) + 1 == 1 (mod 4). This is extremely useful because it means n^2 can never be congruent to 2 or 3 mod 4.
• Once you know the possible residues, you can prove impossibility statements cleanly. For instance, there is no integer n with n^2 == 2 (mod 4) because squares mod 4 are only 0 or 1. This style generalizes: learn what values an expression can take mod m, then use that to rule out equations or divisibility claims. It's a controlled version of proof by cases, and it becomes a major technique in contest math and in early number theory.

• 1Prove: n divisible by 3 iff sum of digits divisible by 3 (outline ok).
• 2Prove: For any integer n, n^2 == 0 or 1 (mod 4).
• 3Prove: There is no integer n such that n^2 == 2 (mod 4).

• 1Prove: If a == b (mod m) then a^2 == b^2 (mod m).
• 2Evaluate: 2^10 mod 7.

MCQ

For any integer n, n^2 mod 4 can be:

• Mathematical induction proves statements indexed by integers (usually n >= some start). The logic is like dominoes: you prove a base case (the first domino falls), and then you prove that if the statement is true for an arbitrary k, it must also be true for k+1 (each domino knocks down the next). Formally, induction proves a universal statement over the integers. It is not "assume what you want and done." The inductive step must show how truth at k forces truth at k+1.
• Induction proofs have a standard form: (1) Base case: verify n = n0. (2) Inductive hypothesis: assume the statement holds for n = k. (3) Inductive step: using the hypothesis, prove it holds for n = k+1. The main beginner pitfall is not using the hypothesis in a logically valid way or accidentally proving the same n twice. The right mindset is: the hypothesis is a tool you may use exactly for k, and your job is to transform the k+1 statement until it contains the k statement inside it.

• Sum 1 + 2 + ... + n = n(n + 1)/2 for n >= 1.

• 1Prove: 1 + 3 + 5 + ... + (2n - 1) = n^2.
• 2Prove: 2^n >= n + 1 for n >= 0.

MCQ

In the inductive step, you must show:

• Induction is especially clean for divisibility statements because many expressions have a natural recurrence. Suppose you want to prove something like "7^n - 1 is divisible by 6 for all n >= 1." The inductive step works because 7^(k+1) - 1 can be rewritten as 7(7^k - 1) + 6. That splits the expression into a multiple of the previous term plus an obvious multiple of 6. This is the general pattern: rewrite the (k+1) expression so it contains the k expression plus a term you can directly show is divisible by the target integer.
• The "rewrite to reveal the hypothesis" habit is the core skill. If your hypothesis is "6 | (7^k - 1)," you want to manufacture (7^k - 1) somewhere in the next expression. Similarly, induction can prove inequalities, sums, and recursion formulas, but divisibility is where you see the mechanism most transparently because "being divisible by m" is stable under adding multiples of m.

• 1Prove: 7^n - 1 is divisible by 6 for n >= 1.
• 2Prove: 3 divides (n^3 - n) for all integers n.

MCQ

A good inductive step for 7^n - 1 divisible by 6 starts with:

• Strong induction is a variation where, to prove the statement for k+1, you may assume it is true for all values up to k, not just for k alone. This is useful when k+1 depends on multiple earlier cases. For example, proving "every integer n >= 2 can be written as a product of primes" uses strong induction. In the inductive step, either n is prime (done) or n is composite, meaning n = ab with 2 <= a,b < n. Then you need the statement for a and b, which are smaller than n, not necessarily equal to n-1. Strong induction gives you that.
• Conceptually, strong induction is not "stronger" than normal induction in logical power, but it is stronger in convenience. It matches many natural recursive breakdowns, like factoring, tiling problems, and coin problems. The key requirement is still the same: you must cover the base cases that make the argument work. If your breakdown uses n-4 or n-5, you must ensure those earlier statements exist and have been established.

• 1Prove: Every integer n >= 2 can be written as a product of primes.
• 2Prove: Every amount of postage >= 12 can be made with 4 and 5 cent stamps.

MCQ

In strong induction, the hypothesis assumes:

• Most induction errors are structural, not algebraic. A frequent mistake is a weak base case, where you prove n = 1 but your inductive step actually needs n = 2 and n = 3 as well. Another common mistake is circularity, where you "prove" the k+1 case by rewriting it into itself without progress. Good induction proofs explicitly label the hypothesis, explicitly show where it is used, and clearly finish with the exact k+1 statement, not something close to it.
• Polishing an induction proof means making the logic easy to audit. A clean inductive step often starts with the left-hand side of the k+1 statement, then performs algebra until the k-case statement appears, then replaces it using the inductive hypothesis, then simplifies to reach the desired form. If you can't find where to use the hypothesis, that's a sign you need a different algebraic rewrite or a different proof method. Induction is a tool, not a default. Use it when the statement naturally relates n to n+1.

Rewrite one induction proof you wrote this week.

• 1Induction: Prove 1 + 2 + ... + n <= n^2 for n >= 1.

MCQ

Which is a common induction mistake?

• Counting proofs start with two basic rules. The sum rule applies when choices are in disjoint categories: if there are a ways to do task A or b ways to do task B, and you cannot do both at once, then there are a + b total ways. The product rule applies when a procedure is sequential: if there are a choices for step 1 and for each of those there are b choices for step 2, then there are ab total outcomes. These rules are simple, but they are the foundation of most combinatorics.
• A subtle but important skill is defining what counts as one outcome. You must specify whether order matters, whether repetition is allowed, and what the "alphabet" or set of objects is. Many counting mistakes come from silently switching these assumptions. Once your assumptions are clear, counting becomes a chain of product and sum rule applications. Counting is also proof-based because many identities are proven by counting the same set in two different ways, which leads directly into combinations and binomial identities.

• 1How many 5-letter strings from {A,B,C} (repetition allowed)?
• 2How many 5-letter strings with no repetition from {A,B,C,D,E,F}?
• 3Prove: number of subsets of an n-element set is 2^n.

MCQ

How many 5-letter strings from {A,B,C} with repetition allowed?

• The binomial coefficient C(n,k), read "n choose k," counts how many ways to choose a k-element subset from an n-element set when order does not matter. It is defined by the formula C(n,k) = n!/(k!(n-k)!), but proof-based combinatorics prefers reasoning over formula memorization. A key identity is Pascal's identity: C(n,k) = C(n-1,k) + C(n-1,k-1). The cleanest proof is a counting argument: count k-person committees from n people by splitting into committees that include a particular person versus those that do not.
• Another fundamental identity is symmetry: C(n,k) = C(n,n-k), because choosing k elements to include is equivalent to choosing the n-k elements to exclude. These are best understood via bijections rather than algebra. In proof-based math, you learn to justify formulas, not just apply them. Once you can build and explain these identities with words and logic, you can handle more advanced counting problems without getting lost in algebraic manipulation.

• 1Prove Pascal identity using counting.
• 2Prove: C(n,k) = C(n,n-k).
• 3Compute C(10,3).

MCQ

C(n,k) counts:

• The pigeonhole principle is a simple idea with strong consequences: if you place more than n objects into n boxes, then some box contains at least two objects. In proof form, you identify what counts as "objects" and what counts as "boxes." For example, if the objects are 13 people and the boxes are the 12 months, at least two people share a birth month. This works because every person must belong to exactly one month box.
• The principle generalizes: if you distribute N objects among n boxes, some box contains at least ceil(N/n) objects. Many problems become pigeonhole once you choose the right grouping. A common pattern in number theory is using remainders as boxes. For example, among n+1 integers, two have the same remainder mod n, because there are only n possible remainders. The main challenge is not the logic, it's modeling the situation correctly.

• 1Among 13 people, at least two share a birth month.
• 2In any set of n + 1 integers, two have the same remainder mod n.
• 3Any 6 people include 3 mutual acquaintances or 3 mutual strangers (optional).

MCQ

'Among 13 people, at least two share a birth month' uses:

• A bijection proof shows two sets have the same size by giving a function that pairs each object in one set with exactly one object in the other, with no leftovers. This is stronger than "they look the same size" because it explicitly constructs a perfect matching. Bijections are widely used to prove combinatorial identities, like C(n,k) = C(n,n-k): map each k-subset to its complement, which is an (n-k)-subset. The complement map is reversible, so it's a bijection.
• Bijection thinking also helps you avoid double counting and clarifies when order matters. If you can build a bijection, you have a proof that two counts are equal without computing either count directly. This style becomes more important later in algebra and discrete math, where structure-preserving maps (isomorphisms) are essentially advanced bijections. For beginners, the goal is learning to describe the map clearly and argue it is one-to-one and onto.

• 1Give a bijection proof of C(n,k) = C(n,n-k).
• 2Prove: number of odd-sized subsets equals number of even-sized subsets (n >= 1).

• 1Use pigeonhole: show among any 5 integers, two differ by a multiple of 4.

MCQ

A bijection is used to prove:

• A relation on a set A is any rule that tells you which pairs (a,b) in A x A are related. Relations generalize ideas like "<=", "same parity," and "congruent mod n." Relations can have properties: reflexive means every element relates to itself (aRa). Symmetric means if aRb then bRa. Transitive means if aRb and bRc then aRc. Proofs here are direct definition proofs: take the definition, assume the hypothesis, and show the property.
• A standard beginner example is the relation "aRb if a-b is even" on integers. Reflexive holds because a-a=0 is even. Symmetric holds because if a-b is even, then b-a = -(a-b) is also even. Transitive holds because if a-b and b-c are even, then adding gives a-c = (a-b) + (b-c), which is even. These proofs train you to do "definition, then algebra" cleanly, which is the same structure you use later in abstract algebra.

On integers, define a R b if a - b is even. Prove R is reflexive.

• 1Prove R is symmetric.
• 2Prove R is transitive.

MCQ

For a R b defined by a - b even, which property follows from 'if a - b is even then b - a is even'?

• An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equivalence relations capture the idea of "same type" under some criterion, like "same remainder mod n." When a relation is an equivalence relation, it partitions the set into equivalence classes, where each class consists of all elements related to a given element. For example, under "same parity," there are exactly two classes: the evens and the odds. Each element belongs to exactly one class.
• Equivalence classes matter because they let you simplify a messy set into a smaller set of categories. Modular arithmetic is built on this: the equivalence classes mod n are the residue classes [0], [1], ..., [n-1]. Proving something is an equivalence relation is usually straightforward, but the deeper understanding is recognizing that once you have equivalence classes, you can work with representatives and avoid repeating the same argument for infinitely many elements.

• 1Describe the equivalence class of 3 under 'same parity'.
• 2Show congruence mod n is an equivalence relation.

MCQ

The equivalence class of 3 under 'same parity' is:

• A partition is a collection of nonempty subsets that are pairwise disjoint and whose union is the entire set. Equivalence relations automatically create partitions: the equivalence classes form the blocks of the partition. Two key facts make this work. First, classes are either identical or disjoint: if two classes share an element, then by transitivity they must be the same class. Second, every element lies in its own equivalence class, so the union of all classes is the whole set.
• These are proof exercises that reinforce controlled logical reasoning. To show "classes are disjoint or equal," you assume two classes overlap, pick an element in the overlap, and use the relation properties to show every element of one class must relate to every element of the other in the right way, forcing equality. This style is similar to set equality proofs, but now the structure of the relation (especially transitivity) does the heavy lifting.

• 1Prove equivalence classes are either disjoint or identical.
• 2Prove union of all classes is the whole set.

MCQ

Two equivalence classes are:

• At this stage, you should be comfortable choosing a proof method rather than defaulting to one. If a statement is universal, a direct proof or case proof often works. If it's an implication with a hard direction, try the contrapositive. If it asserts nonexistence or minimality, contradiction is often clean. If it involves sets, do element-chasing. If it involves "same remainder," translate to divisibility and use modular arithmetic. If it involves "for all n," consider induction if there's a natural n to n+1 connection.
• The skill you are building is proof strategy. Many beginner proofs fail because the writer does not decide what they are allowed to assume and what they must show. A good proof begins by restating the definitions and isolating the goal. Once you see the goal in definitional form, the path becomes much clearer. This is why learning the definitions and practicing rewriting is more important than memorizing tricks.

• 1If n == m (mod 5) then n^2 == m^2 (mod 5).
• 2If gcd(a,b) = 1 and a | b then a = 1 or a = -1.
• 3n(n+1)(n+2) divisible by 3.
• 4If f is bijective, then f has an inverse function.

• 1Show 'same remainder mod 4' is an equivalence relation, and list the 4 classes.

MCQ

If f is bijective, then:

• A correct proof can still be hard to read, and proof-based math cares about communication. Good proof style means: state the claim clearly, define your terms, introduce variables with their sets ("let n be an integer"), and justify each step. Avoid skipping the key step where a word becomes algebra, like "n is even, so n = 2k." Also avoid "obvious" unless you can explain it in one line. A proof should be checkable by another person without guessing what you meant.
• Revision is a real part of mathematics. When you revise, look for hidden assumptions, unclear variable declarations, and steps that are true but not justified. Also watch for the most common beginner issue: proving a stronger or different statement than what was asked. A good revision pass compares each line to the goal: does this line move me closer to the conclusion, or is it unrelated algebra? Clean proofs are usually shorter, not longer, because every line has a job.

Revise two older proofs using the checklist.

MCQ

Which item belongs on the proof revision checklist?

• Mixed practice is where you learn to select the right tool. If you see an "iff," split into two directions. If you see set equality, prove two inclusions. If you see a divisibility statement, rewrite using "= ak." If you see something about squares and parity, consider cases mod 2 or mod 4. If you see a sum or a power indexed by n, consider induction. Strategy becomes almost mechanical once you recognize these signal phrases and structures.
• The goal is not to know advanced theorems. It's to know how to translate a problem into the right language and then apply a standard proof pattern cleanly. This is why earlier weeks drilled translation, negation, and definitions. In a mixed proof session, you should always start by rewriting the statement in precise math form, then pick a method, then write the proof with explicit steps. Skipping the rewrite step is the fastest way to get stuck.

• 1If n is odd then n^2 == 1 (mod 8) is false; fix it.
• 2Prove: A \ (B intersect C) = (A \ B) union (A \ C).
• 3Induction: 1^3 + 2^3 + ... + n^3 = (n(n+1)/2)^2.
• 4Prove Euclid's Lemma (outline ok).
• 5If f and g are bijections then f o g is a bijection.
• 6Pigeonhole: among any 10 integers, two have the same last digit.

MCQ

Which identity is correct?

• A proof portfolio is a set of polished proofs that demonstrate mastery of core methods. "Polished" means: correct logic, clear structure, minimal fluff, and explicit use of definitions. The portfolio should include a variety: at least one contrapositive proof, one contradiction proof, one induction proof, one set identity proof, one function property proof, and one modular or divisibility proof. This ensures you can move between styles and topics without relying on a single technique.
• When selecting proofs, choose ones you can explain out loud. If you cannot explain why each step is valid, it's not yet portfolio-ready. For each proof, aim for a clean beginning that sets variables and hypotheses, a middle that uses definitions and algebra or logic, and a crisp ending that restates the conclusion. The portfolio is less about difficulty and more about correctness and clarity, because those are the foundational skills proof-based math demands.

Core: even/odd proofs, set identities, bijection, induction, modular proofs.

• 1Stretch: sqrt(2) irrational, prime factorization, Pascal identity, odd/even subsets.

MCQ

How many polished proofs are required in the final portfolio?

• In a final assessment, the most important skill is controlling the logical structure under time pressure. Start by identifying the type of statement: implication, universal, existence, equality. Then commit to a method and write in a disciplined format. For example, for divisibility: "Let k be an integer such that..." and for subsets: "Let x be an arbitrary element of..." Those openings are not filler, they are the correct logical entry points.
• If you get stuck, don't do random algebra. Return to definitions and the goal. Ask: what exactly do I need to show? Can I rewrite it in a more workable form? Many proofs fail because the writer never wrote the goal in an actionable form, like "show m divides (expression)" becoming "show expression = m*t for some integer t." That rewrite often creates the path forward. A strong beginner proof is not fancy. It is controlled, explicit, and logically complete.

• 1Prove: For all integers n, n^3 - n is divisible by 3.
• 2Prove: If A subseteq B then A \ C subseteq B \ C.

MCQ

A standard factorization for n^3 - n is: