Math 1510 – Proof Techniques & Introductory Examples (Wk 2, p1)

Introduction & Context
  • Course: Math 1510 – Proofs & Discrete Mathematics

  • Session goal: transition from symbolic logic to proof techniques, emphasizing a rigorous approach to mathematical statements.

  • Classroom logistics briefly mentioned (projectors, slides) ➜ informational, not mathematically relevant.

Review of Quantifiers & Their Negations
  • A proposition depending on (x) (e.g. P(x):  x>3P(x):\;x>3) is a statement whose truth value varies based on the specific element from the domain assigned to (x). It can be true or false for different domain elements.

  • The specified domain of discourse is crucial:

    • If domain = R\mathbb R (all real numbers), then P(4)P(4) is true, while P(2)P(2) is false.

    • If domain = [−1,0][-1,0] (the closed interval from -1 to 0), the statement ∃x  P(x)\exists x\;P(x) (there exists an x such that P(x) is true) is false, because no number in this domain satisfies x>3x>3. The statement ∀x  P(x)\forall x\;P(x) (for all x, P(x) is true) would also be false.

  • Negation rules (De Morgan‐style for quantifiers): These rules show how to logically negate statements involving quantifiers.

    • ¬(∃x  P(x))  ≡  ∀x  ¬P(x)\neg\big(\exists x\;P(x)\big)\;\equiv\;\forall x\;\neg P(x). This means "It is not the case that there exists an x for which P(x) is true" is logically equivalent to "For all x, P(x) is false."

    • ¬(∀x  P(x))  ≡  ∃x  ¬P(x)\neg\big(\forall x\;P(x)\big)\;\equiv\;\exists x\;\neg P(x). This means "It is not the case that for all x, P(x) is true" is logically equivalent to "There exists at least one x for which P(x) is false."

  • Set‐theoretic picture teased: This provides a visual intuition for quantifiers.

    • Let set A:=x∣P(x) trueA:={x\mid P(x)\text{ true}} be the subset of elements in the domain DD for which the proposition P(x)P(x) is true.

    • The statement ∀x P(x)\forall x\,P(x) is true if and only if the set AA is equal to the entire domain DD (A=DA=D).

    • The statement ∃x P(x)\exists x\,P(x) is true if and only if the set AA is not empty (A≠∅A\neq\emptyset).

Proofs vs Calculations
  • Proof = an essay-like logical argument that demonstrates the truth of a mathematical statement based on definitions, axioms, and previously established theorems. It is not simply a rote computation or finding a numerical answer.

  • Must be: logically consistent, detailed enough for any reasonably knowledgeable reader to meticulously rebuild your line of reasoning step-by-step.

  • Use only previously established facts, definitions, rules, or axioms; there is no need to re-derive fundamental arithmetic like 2+2=42+2=4. The foundation of a proof rests on what is already known and accepted.

  • Creative process – there is no guaranteed algorithm or single formula for constructing a proof, unlike applying derivative rules. It often requires insight and strategic thinking.

Catalogue of Proof Methods Introduced
  • Direct proof: Directly showing that the conclusion follows from the premises.

  • Mathematical induction (standard & strong): Proving statements about natural numbers.

  • Proof by contradiction: Assuming the negation of what you want to prove and deriving an impossibility.

  • Pigeonhole principle: A combinatorial principle stating that if you have more items than categories, at least one category must contain more than one item.

  • Double counting & other combinatorial tricks: Counting the same set of objects in two different ways to show that two expressions are equal.

Mathematical Induction (Standard)
  • Domino metaphor: Imagine an infinite line of dominoes, P<em>1,P</em>2,P<em>3,…P<em>1, P</em>2, P<em>3, \dots, where P</em>nP</em>n represents the statement you want to prove for a given integer (n).

  • Two steps are required to show that all dominoes fall (i.e., that the statement is true for all natural numbers):

    1. Base case: Prove that P1P_1 is true (the first domino falls). This establishes a starting point for the induction.

    2. Inductive step: Prove that for any arbitrary natural number (k), if P<em>kP<em>k is true (the k-th domino falls), then P</em>k+1P</em>{k+1} must also be true (the (k+1)-th domino will fall). This establishes the chain reaction.

  • Then, by the principle of mathematical induction, you can conclude that ∀n∈N,  Pn\forall n\in\mathbb N,\;P_n is true. This method is typically used for statements involving properties of integers, such as sums of series, inequalities, divisibility rules, or properties of sequences and graphs that depend on an integer parameter (n).

  • Typical domains: formulas depending on an integer parameter (n) (e.g. sequences, sums, graph properties, divisibility statements, inequalities).

Σ-notation refresher

  • Summation notation: ∑i=abf(i)=f(a)+f(a+1)+⋯+f(b)\displaystyle\sum_{i=a}^{b}f(i)=f(a)+f(a+1)+\dots+f(b).

    • The variable (i) is the index of summation.

    • (a) is the lower limit of summation, and (b) is the upper limit.

    • f(i)f(i) is the expression being summed, evaluated at each integer from (a) to (b).

  • Examples:

    • ∑i=15i=1+2+3+4+5=15\sum_{i=1}^{5} i =1+2+3+4+5=15. This sums the first 5 natural numbers.

    • ∑i=15i2=12+22+32+42+52=1+4+9+16+25=55\sum_{i=1}^{5} i^2 =1^2+2^2+3^2+4^2+5^2 = 1+4+9+16+25=55. This sums the squares of the first 5 natural numbers.

  • Half-integer example: ∑i=010i2=0+12+1+⋯+5\sum_{i=0}^{10}\frac{i}{2}=0+\tfrac12+1+\dots+5. This sum has (11) terms, starting from i=0i=0 up to i=10i=10. Note that the index (i) still increments by 1.

Classic Induction Example – Sum 1+2+…+n

  • Claim: The sum of the first (n) natural numbers is given by the formula ∑i=1ni=n(n+1)2  .\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\;.

    1. Base case: For n=1n=1, the sum is just 1. The formula gives 1(1+1)2=1⋅22=1\frac{1(1+1)}{2}=\frac{1\cdot2}{2}=1. Since 1=11=1, the base case holds. ✓

    2. Inductive step: Assume the formula is true for some arbitrary integer k≥1k\ge1. That is, assume ∑<em>i=1ki=k(k+1)2\sum<em>{i=1}^{k} i =\frac{k(k+1)}{2} (this is the inductive hypothesis, P</em>kP</em>k). We need to prove that it follows that the formula is true for (k+1)(k+1) (P<em>k+1P<em>{k+1}). So, we consider the sum up to (k+1)(k+1): ∑</em>i=1k+1i=(∑<em>i=1ki)+(k+1)\sum</em>{i=1}^{k+1} i = \Big(\sum<em>{i=1}^{k} i\Big)+(k+1). By the inductive hypothesis (P</em>kP</em>k), we replace the sum ∑<em>i=1ki\sum<em>{i=1}^{k} i with its assumed formula: =k(k+1)2+(k+1)=\frac{k(k+1)}{2}+(k+1) Now, we algebraically manipulate this expression to match the formula for (k+1)(k+1). Factor out (k+1)(k+1): =(k+1)(k2+1)=(k+1)\Big(\frac{k}{2}+1\Big) =(k+1)(k+22)=(k+1)\Big(\frac{k+2}{2}\Big) =(k+1)(k+2)2=\frac{(k+1)(k+2)}{2}. This matches the formula with (n)(n) replaced by (k+1)(k+1). Thus, P</em>k⇒Pk+1P</em>k\Rightarrow P_{k+1} is proven.

    3. Conclusion: By the principle of mathematical induction, the claim ∑i=1ni=n(n+1)2\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2} is true for all natural numbers n≥1n\ge1.

  • Geometric link: This formula has a visual interpretation. The area under the line y=xy=x on the interval [0,1], approximated using Riemann sums with unit width rectangles, can be seen to relate to this sum. More broadly, arranging the numbers 1,2,…,n1, 2, \dots, n in a triangular pattern leads to a rectangle of size n×(n+1)n \times (n+1), whose area is double the sum.

Other Induction Claims Mentioned

  • n!<nn(∀n≥1)n!< n^{n} \quad(\forall n\ge1): The factorial of (n) (product of integers from 1 to n) is strictly less than nn raised to the power of nn. This can be proven by comparing terms term-wise, i≤ni \le n for each factor in n!n!.

  • 9n−19^{n}-1 divisible by 4: This statement asserts that for all natural numbers (n), 9n−19^n-1 is a multiple of 4. Proving this typically relies on 9k−1=4m9^k-1 = 4m for some integer (m) in the inductive hypothesis.

  • Fibonacci recurrence F<em>0=0,F</em>1=1,F<em>n=F</em>n−1+F<em>n−2F<em>0=0,F</em>1=1,F<em>{n}=F</em>{n-1}+F<em>{n-2}: The Fibonacci sequence is defined by its first two terms and a recurrence relation. The identity ∑</em>i=0nF<em>i=F</em>n+2−1\sum</em>{i=0}^{n} F<em>i = F</em>{n+2}-1 states that the sum of the first (n+1)(n+1) Fibonacci numbers (from F<em>0F<em>0 to F</em>nF</em>n) equals the (n+2)(n+2)-th Fibonacci number minus 1.

Strong Induction
  • Hypothesis assumes all previous statements: Instead of just assuming P<em>kP<em>k to prove P</em>k+1P</em>{k+1}, strong induction's hypothesis assumes that all statements P<em>1,P</em>2,…,P<em>kP<em>1, P</em>2, \dots, P<em>k are true (P</em>1∧P<em>2∧⋯∧P</em>k⇒Pk+1P</em>1\wedge P<em>2\wedge\dots\wedge P</em>k \Rightarrow P_{k+1}). This is a stronger assumption.

  • Equivalent power, sometimes easier: Strong induction is logically equivalent to standard induction (any proof using one can be converted to the other), but sometimes the proof for P<em>k+1P<em>{k+1} naturally depends on earlier cases (e.g., P</em>k−1P</em>{k-1}, Pk−2P_{k-2}) making strong induction conceptually simpler or more direct to apply.

Strong Induction Example – Sequence cnc_n

  • Definition: This sequence is defined recursively.

    • c0=0c_0=0,

    • c<em>n=c</em>⌊n/2⌋+n  (n≥2)c<em>n = c</em>{\lfloor n/2\rfloor}+n \; (n\ge2): This recurrence relation means the value of cnc_n depends on an earlier term calculated from the floor of n/2n/2. The floor function ⌊x⌋\lfloor x\rfloor gives the greatest integer less than or equal to (x).

  • Claim: cn<2n    (n≥1)c_n<2n \;\;(n\ge1): We want to prove this inequality for all n≥1n\ge1.

  • Proof outline:

    1. Base cases: When using strong induction, sometimes multiple base cases are needed if the recurrence relation refers to values that would fall outside the standard P<em>1P<em>1 base case. In this specific claim, the claim starts at n≥1n\ge1. Let's check n=1n=1. We have c</em>1c</em>1 implicitly defined by c<em>1=c</em>⌊1/2⌋+1=c<em>0+1=0+1=1c<em>1 = c</em>{\lfloor 1/2\rfloor} + 1 = c<em>0 + 1 = 0+1=1. For n=1n=1, the claim is c</em>1<2(1)c</em>1 < 2(1), which is 1<21<2. This is true. ✓

    2. Inductive step: Assume that c<em>m<2mc<em>m<2m holds for all integers mm such that 1≤m≤k1\le m\le k, for some k≥1k\ge1. This is our strong inductive hypothesis. We need to show that c</em>k+1<2(k+1)c</em>{k+1}<2(k+1).
      Let's compute c<em>k+1c<em>{k+1}. By definition, c</em>k+1=c<em>⌊(k+1)/2⌋+k+1c</em>{k+1}=c<em>{\lfloor(k+1)/2\rfloor}+k+1. Let m=⌊(k+1)/2⌋m = \lfloor(k+1)/2\rfloor. Since k≥1k\ge1, (k+1)≥2(k+1)\ge2, so m=⌊(k+1)/2⌋≥1m = \lfloor(k+1)/2\rfloor \ge 1. Also, m=⌊(k+1)/2⌋≤(k+1)/2≤km = \lfloor(k+1)/2\rfloor \le (k+1)/2 \le k for k≥1k\ge1. Specifically, if k+1=2k+1=2, m=1m=1; if k+1=3k+1=3, m=1m=1; if k+1=4k+1=4, m=2m=2. In all cases, m≤km \le k. Therefore, we can apply our inductive hypothesis to c</em>mc</em>m, so c<em>m<2mc<em>m < 2m. Substituting this back: c</em>k+1=c<em>⌊(k+1)/2⌋+k+1c</em>{k+1} = c<em>{\lfloor(k+1)/2\rfloor}+k+1 Using the hypothesis on the floor index (c</em>m<2mc</em>m < 2m):
      <2⌊k+12⌋+k+1< 2\lfloor\tfrac{k+1}{2}\rfloor+k+1
      Next, use the property of the floor function: ⌊x⌋≤x\lfloor x\rfloor \le x. So, ⌊k+12⌋≤k+12\lfloor\tfrac{k+1}{2}\rfloor \le \frac{k+1}{2}.
      ≤2(k+12)+k+1\le 2\Big(\frac{k+1}{2}\Big)+k+1
      =(k+1)+(k+1)= (k+1)+(k+1)
      =2(k+1)= 2(k+1).
      This shows that ck+1<2(k+1)c_{k+1} < 2(k+1), which is exactly what we needed to prove for the inductive step.

  • Hence, by strong induction, the inequality cn<2nc_n<2n holds for all n≥1n\ge1.

Proof by Contradiction
  • Strategy: To prove a statement PP, you assume its negation ¬P\neg P is true, and then logically derive a contradiction (a statement that is always false, denoted by ⊥\bot). Since your assumption led to a falsehood, the assumption itself must be false, meaning PP must be true.

  • Logical equivalence: The statement P⇒QP\Rightarrow Q (If P then Q) is logically equivalent to (P∧¬Q)⇒⊥(P\wedge\neg Q)\Rightarrow \bot (If P is true and Q is false, then a contradiction arises). This equivalence forms the basis for this proof technique, as assuming ¬Q\neg Q within the context of PP and finding a contradiction means QQ must be true if PP is.

Examples

  1. Factor below n\sqrt n for composites: If an integer nn is composite, it can be written as n=abn=ab for integers a,b>1a,b>1. The proof by contradiction goes: Assume, for the sake of contradiction, that both factors aa and bb are greater than n\sqrt n. So, a>na>\sqrt n and b>nb>\sqrt n. Multiplying these inequalities, we get ab>n⋅nab > \sqrt n \cdot \sqrt n which simplifies to n>nn>n. This is a contradiction (nn cannot be strictly greater than itself). Therefore, our initial assumption must be false, meaning at least one of the factors (aa or bb) must be less than or equal to n\sqrt n. This is a crucial result for optimizing primality tests.

  2. Infinitely many primes (Euclid): This classic proof is by contradiction.

    • Suppose, for a contradiction, that there are only finitely many prime numbers. Let these be p<em>1,p</em>2,…,prp<em>1,p</em>2,\dots,p_r (a complete list of all primes).

    • Consider the number N=p<em>1⋯p</em>r+1N=p<em>1\cdots p</em>r+1. This number is formed by multiplying all prime numbers on our supposed finite list and adding 1.

    • By the Fundamental Theorem of Arithmetic, any integer greater than 1 must have at least one prime divisor. So, NN must have a prime divisor, let's call it pp.

    • This prime divisor pp must be one of the primes on our list (p<em>1,…,p</em>rp<em>1, \dots, p</em>r), because we assumed our list contains all primes. Therefore, pp divides p<em>1⋯p</em>rp<em>1\cdots p</em>r.

    • If pp divides NN and pp divides p<em>1⋯p</em>rp<em>1\cdots p</em>r, then pp must also divide their difference: N−(p<em>1⋯p</em>r)=(p<em>1⋯p</em>r+1)−(p<em>1⋯p</em>r)=1N - (p<em>1\cdots p</em>r) = (p<em>1\cdots p</em>r+1) - (p<em>1\cdots p</em>r) = 1.

    • So, pp divides 1. The only positive integer that divides 1 is 1 itself. But 1 is not a prime number. This is a contradiction, as pp was defined as a prime divisor.

    • Thus, our initial assumption that there are finitely many primes must be false. Therefore, there are infinitely many prime numbers.

  3. Irrationality of 2\sqrt2 (two proofs):

    • a. Co-prime fraction method leads to even/odd parity clash: Assume, for contradiction, that 2\sqrt2 is rational. This means 2=p/q\sqrt2 = p/q for some integers pp and qq where q≠0q\neq0 and the fraction p/qp/q is in its lowest terms (i.e., pp and qq share no common factors other than 1; they are coprime).
      Squaring both sides gives 2=p2/q22 = p^2/q^2, so 2q2=p22q^2 = p^2. This implies p2p^2 is an even number. If p2p^2 is even, then pp must also be even (because an odd number squared is always odd).
      Since pp is even, we can write p=2kp=2k for some integer kk. Substituting this into 2q2=p22q^2 = p^2 gives 2q2=(2k)2=4k22q^2 = (2k)^2 = 4k^2. Dividing by 2, we get q2=2k2q^2 = 2k^2. This implies q2q^2 is an even number. If q2q^2 is even, then qq must also be even.
      So, we have deduced that both pp and qq are even. This means they both have a common factor of 2. But we initially assumed that pp and qq are coprime (have no common factors other than 1). This is a contradiction. Therefore, our initial assumption that 2\sqrt2 is rational must be false. Hence, 2\sqrt2 is irrational.

    • b. Minimal denominator method produces smaller denominator, contradicting minimality: This less common proof assumes 2=p/q\sqrt2 = p/q where p,qp,q are positive integers and qq is the smallest possible positive denominator for which 2\sqrt2 can be expressed as a fraction. From 2q2=p22q^2 = p^2, we know pp must be even. Let p=2kp=2k. Then 2q2=(2k)2=4k2⇒q2=2k22q^2 = (2k)^2 = 4k^2 \Rightarrow q^2 = 2k^2. This implies qq must also be even. So, q=2mq=2m. Then 2=p/q=(2k)/(2m)=k/m\sqrt2 = p/q = (2k)/(2m) = k/m. Here, m=q/2m = q/2. Since qq is a positive integer, mm is also a positive integer and m<qm<q. This contradicts our initial assumption that qq was the smallest possible positive denominator. Therefore, 2\sqrt2 must be irrational.

Pigeonhole Principle (PHP)
  • Formal Statement: If mm objects are placed into nn boxes (or categories or containers), and m>nm>n, then at least one box must contain two or more objects. This is a powerful, yet simple, combinatorial principle.

  • Simple corollaries:

    • If you have 13 people, and each person has a birth-month, then by PHP, at least two people must share the same birth-month (13 objects, 12 possible boxes/months; 13>1213>12).

    • In any group of two or more people, at least two individuals must have the same number of friends within that group (sketched via PHP): Let (N) be the number of people. The number of friends a person can have ranges from 0 to N−1N-1. However, if someone has 0 friends, no one can have N−1N-1 friends (as that person would be friends with everyone else). So, the possible number of friends are either 0,1,…,N−2{0, 1, \dots, N-2} or 1,2,…,N−1{1, 2, \dots, N-1}. In both cases, there are N−1N-1 possible values for the number of friends. Since there are (N) people (objects) and at most N−1N-1 possible friend counts (boxes), at least two people must fall into the same box, meaning they have the same number of friends.

Double Counting Technique
  • Count a quantity in two independent ways, ensuring both methods enumerate the same set of items or relationships. Since both methods count the same quantity, their results must be equal, leading to a mathematical identity.

  • Re-derivation of ∑i=1ni\sum_{i=1}^{n}i:

    • Let S=1+2+⋯+(n−1)+nS = 1+2+\dots+(n-1)+n.

    • Write the sum forward: S=1+2+⋯+(n−1)+nS=1+2+\dots+(n-1)+n

    • Write the sum backward: S=n+(n−1)+⋯+2+1S=n+(n-1)+\dots+2+1

    • Add the two equations vertically, term-by-term:
      2S=(1+n)+(2+n−1)+⋯+(n−1+2)+(n+1)2S = (1+n)+(2+n-1)+\dots+(n-1+2)+(n+1)
      Each pair sums to (n+1)(n+1). There are (n) such pairs.
      2S=n(n+1)2S = n(n+1)

    • Divide by 2 to find S: S=n(n+1)2S=\frac{n(n+1)}{2}.
      This simple example beautifully illustrates how counting the same sum in two different orders leads to a formula.

Graph Theory Preview & Contrapositive Use
  • Graph: A mathematical structure consisting of a set of vertices (or nodes) and a set of edges (or links) connecting pairs of vertices. Graphs are used to model relationships or connections between discrete objects.

  • Degree of a vertex: The number of edges incident to (connected to) that vertex.

  • Cycle: A closed walk (a sequence of vertices and edges that starts and ends at the same vertex) in which no vertex (other than the start/end vertex) and no edge is repeated. A cycle indicates a closed loop in the graph.

  • Bipartite graph: A graph whose vertices can be divided into two disjoint and independent sets, UU and VV, such that every edge connects a vertex in UU to one in VV. No edges exist within UU or within VV. This means all cycles in a bipartite graph must have even length.

  • Theorem pair (contrapositives): Two statements that are logically equivalent, where proving one automatically proves the other.

    • "If a graph has every vertex degree ≥2\ge2 then it has a cycle" (Original statement).

    • The contrapositive: "If a graph does not have a cycle (i.e., is acyclic), then it must possess at least one vertex of degree 1 (or 0)". Proving the contrapositive can often be simpler. For example, if a graph is acyclic and connected, it must be a tree, and every tree with more than one vertex has leaves (vertices of degree 1).

  • Illustration that proving the contrapositive can be easier: Sometimes, directly proving "if P then Q" is difficult. But proving "if not Q then not P" can be more straightforward, especially when "not Q" provides a stronger, more constructive starting point.

  • Bipartite graphs contain no odd-length cycles (sketch: Consider a cycle in a bipartite graph. As you traverse the cycle, you must alternate between vertices in set UU and vertices in set VV. To return to the starting vertex, you must have taken an even number of steps, as each step moves you from one partition to the other and back. Therefore, any cycle length must be even). This property is a fundamental characteristic of bipartite graphs.

Common Logical & Proof Pitfalls
  • Empirical verification (many cases) ≠\neq proof for all: Testing a statement on many examples, even a million, does not constitute a proof that it holds for all cases. A proof requires a universal argument, not just specific instances.

  • Confusing statement with its converse: For a statement "If P then Q" (P⇒QP\Rightarrow Q), its converse is "If Q then P" (Q⇒PQ\Rightarrow P). These are not logically equivalent. For example, "If it is raining, then the ground is wet" is true. Its converse, "If the ground is wet, then it is raining," is false (e.g., could be dew).

  • Post hoc fallacy: Short for "post hoc ergo propter hoc" (after this, therefore because of this). This is a logical fallacy where one assumes that because event B happened after event A, then A must have caused B. Correlation or sequence of events does not necessarily imply causation.

  • Assuming existence of an object not shown to exist: For instance, saying "Let xx be an integer such that x2=−1x^2=-1" without first proving such an xx exists (it doesn't in natural numbers). You must establish the existence of any mathematical object you intend to use in a proof.

  • Reusing same symbol for distinct objects: Using the same variable name (e.g., xx) to represent two different values or concepts within the same scope of a proof leads to ambiguity and logical errors.

  • Example fallacy: start with false premise (1=0), manipulate algebraically to reach true statement ⇒\Rightarrow does not validate original premise: If you start a logical argument with a false premise, you can logically deduce any conclusion, including true ones, valid ones, or contradictions. The apparent validity of the deduction does not validate the original false premise. The conclusion is merely consistent with the false premise, but the entire argument is unsound.

Miscellaneous Numerical / Symbolic Facts Referenced
  • Factorial definition: n!=n×(n−1)×(n−2)×⋯×3×2×1n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1. For n≥1n\ge 1. By definition, 0!=10! = 1. Factorials represent the number of ways to arrange (n) distinct items.

  • Power notation: nn=n×n×⋯×n⏟n timesn^n = \underbrace{n\times n\times\dots\times n}_{n\text{ times}}. Represents (n) multiplied by itself (n) times. (e.g., 33=3×3×3=273^3 = 3\times3\times3 = 27).

  • Floor function: ⌊x⌋\lfloor x\rfloor = the largest integer less than or equal to xx.

    • e.g. ⌊10.5⌋=10\lfloor10.5\rfloor=10

    • ⌊3⌋=3\lfloor 3\rfloor=3

    • ⌊−0.5⌋=−1\lfloor -0.5\rfloor=-1
      The floor function effectively truncates the decimal part of a positive number downwards.

Study Tips for Writing Proofs
  • Write in full sentences interleaved with mathematical expressions; the reader should be able to follow your argument like a narrative. Use clear prose to connect mathematical ideas and steps.

  • Justify every non-obvious step with precise references to prior definitions, axioms, established theorems, or basic algebraic rules. Do not skip steps that a reader might question.

  • Clearly separate assumptions from deductions. Use phrases like "Assume P is true," "By definition of X," "It follows from Theorem Y that…" to guide the reader through your logical flow.

  • Label variables carefully; avoid overloading symbols by using the same letter for different quantities or concepts within the same part of a proof. Introduce new variables explicitly when needed.

  • When stuck, consider alternate but equivalent statements (e.g., proving the contrapositive instead of the direct statement), or try a different proof method (e.g., standard induction vs. strong induction vs. contradiction). Sometimes approaching a problem from a different angle reveals a path forward.

Administrative Reminders (from lecture)
  • Workshops begin this week (check timetable).

  • Lecture recordings available via Panopto on Canvas.

  • Recommended text (optional): Proofs & Fundamentals by Johnston & Bao (title mentioned for supplementary reading).