Mathematical Logic & Reasoning Complete Study Guide - 1 BAC Science Exp

Theoretical Foundations of Mathematical Logic

• Quantifiers in First-Order Logic:

  • Universal Quantifier ($\forall$): Read as "for all" or "for every". A statement $(\forall x \in E): P(x)$ is true if and only if the predicate $P(x)$ holds true for every element $x$ in the set $E$.
  • Existential Quantifier ($\exists$): Read as "there exists at least one". A statement $(\exists x \in E): P(x)$ is true if there exists at least one element $x_0 \in E$ for which $P(x_0)$ is true.

• Rules of Logical Negation:

  • Negation of Universal Statement: $\overline{(\forall x \in E): P(x)} \iff (\exists x \in E): \overline{P(x)}$
  • Negation of Existential Statement: $\overline{(\exists x \in E): P(x)} \iff (\forall x \in E): \overline{P(x)}$
  • Negation of Implication: $\overline{P \implies Q} \iff P \land \overline{Q}$
  • De Morgan's Laws: $\overline{P \land Q} \iff \overline{P} \lor \overline{Q}$ and $\overline{P \lor Q} \iff \overline{P} \land \overline{Q}$

• Methods of Proof:

  • Direct Deduction: To prove $P \implies Q$, assume $P$ is true and apply logical deductions to arrive at $Q$.
  • Proof by Counterexample: To prove that a universal proposition $(\forall x \in E): P(x)$ is false, construct a specific element $x_0 \in E$ (a counterexample) for which $P(x_0)$ is false.
  • Proof by Contrapositive: The implication $P \implies Q$ is logically equivalent to its contrapositive $\overline{Q} \implies \overline{P}$. Proving $\overline{Q} \implies \overline{P}$ establishes $P \implies Q$
  • Proof by Logical Equivalence: To prove $P \iff Q$, demonstrate a chain of reversible logic steps $P \iff R_1 \iff R_2 \iff \dots \iff Q$, or prove both implications $P \implies Q$ and $Q \implies P$
  • Proof by Disjunction of Cases: If the universal domain $E$ can be partitioned into exhaustive cases $E_1, E_2, \dots, E_k$, proving the statement for each individual case proves it for all $E$
  • Proof by Contradiction (Reductio ad Absurdum): To prove $P$ is true, assume its negation $\overline{P}$ is true, and derive a logical impossibility or contradiction (such as $1 = 0$ or $a \land \overline{a}$).
  • Mathematical Induction: To prove a proposition $P(n)$ for all integers $n \ge n_0$:
  1. Initialization (Base Case): Show $P(n_0)$ is true.
  2. Heredity (Inductive Step): Assume $P(k)$ is true for an arbitrary integer $k \ge n_0$, and prove $P(k+1)$ is true.
  3. Conclusion: Conclude that $P(n)$ is true for all integers $n \ge n_0$

Exercise 1: Quantified Statements, Truth Values, and Negations

• Statement $P_1$:

  • Form: $P_1: (\exists x \in \mathbb{R}): 3x + 6 = 0$
  • Truth Value Analysis: Solving $3x + 6 = 0$ yields $x = -2$. Since $-2 \in \mathbb{R}$, there exists a real solution.
  • Truth Value: True
  • Negation: $\overline{P_1}: (\forall x \in \mathbb{R}): 3x + 6 \ne 0$

• Statement $P_2$:

  • Form: $P_2: (\exists x \in \mathbb{R}): x^2 - 3x + 2 = 0$
  • Truth Value Analysis: The quadratic equation has discriminant $\Delta = (-3)^2 - 4(1)(2) = 1 > 0$, providing real solutions $x = 1$ and $x = 2$. Thus, the existential condition is satisfied.
  • Truth Value: True
  • Negation: $\overline{P_2}: (\forall x \in \mathbb{R}): x^2 - 3x + 2 \ne 0$

• Statement $P_3$:

  • Form: $P_3: (\forall x \in [1; 6]): x^2 - 7x + 6 \le 0$
  • Truth Value Analysis: Factorizing the quadratic gives $x^2 - 7x + 6 = (x - 1)(x - 6)$. For any $x \in [1; 6]$, $x - 1 \ge 0$ and $x - 6 \le 0$. The product of a non-negative number and a non-positive number is non-positive ($\le 0$). Thus, the inequality holds for all $x$ in the interval.
  • Truth Value: True
  • Negation: $\overline{P_3}: (\exists x \in [1; 6]): x^2 - 7x + 6 > 0$

• Statement $P_4$:

  • Form: $P_4: (\forall x \in \mathbb{R}): x^2 - 2x + 3 > 0$
  • Truth Value Analysis: Rewriting as a completed square yields $x^2 - 2x + 3 = (x - 1)^2 + 2$. Since $(x - 1)^2 \ge 0$ for all real $x$, $(x - 1)^2 + 2 \ge 2 > 0$. Alternatively, discriminant $\Delta = 4 - 12 = -8 < 0$ with coefficient $a = 1 > 0$, so the polynomial is strictly positive everywhere on $\mathbb{R}$.
  • Truth Value: True
  • Negation: $\overline{P_4}: (\exists x \in \mathbb{R}): x^2 - 2x + 3 \le 0$

Exercise 2: Proof by Counterexample

• Disproving Proposition $P_1$:

  • Proposition: $P_1: (\forall x \in \mathbb{R}): \sqrt{x^2} = x$
  • Counterexample Construction: Choose $x = -2 \in \mathbb{R}$.
  • Verification: $\sqrt{(-2)^2} = \sqrt{4} = 2$. However, $x = -2$. Since $2 \ne -2$, $\sqrt{x^2} \ne x$ for $x = -2$.
  • Conclusion: $P_1$ is false.

• Disproving Proposition $P_2$:

  • Proposition: $P_2: (\forall x \in \mathbb{R}): x^2 \ge x$
  • Counterexample Construction: Choose $x = \frac{1}{2} \in \mathbb{R}$.
  • Verification: $x^2 = \left(\frac{1}{2}\right)^2 = \frac{1}{4}$. Comparing values, $\frac{1}{4} < \frac{1}{2}$, which means $x^2 < x$.
  • Conclusion: $P_2$ is false.

• Negation of Implication Proposition $(R)$:

  • Given Proposition: $(R): (\forall x \in \mathbb{R}): [x^2 = 2x \implies x = 0]$
  • Applying the negation rule $\overline{A \implies B} \iff A \land \overline{B}$:
  • Negation: $\overline{R}: (\exists x \in \mathbb{R}): [x^2 = 2x \text{ et } x \ne 0]$

• Deducing Truth Value of Proposition $(R)$:

  • Test $x = 2 \in \mathbb{R}$:
  • Evaluating premises: $2^2 = 4$ and $2 \times 2 = 4$, so $x^2 = 2x$ is true.
  • Evaluating conclusion condition: $x = 2 \ne 0$, so $x \ne 0$ is true.
  • Since $\overline{R}$ is true for $x = 2$, the original statement $(R)$ is false.

Exercise 3: Counterexample Method Applied to Real Functions

• Setting: Function $f$ defined on $\mathbb{R}$ by $f(x) = x^2 - 3x + 2$

• Solving $f(x) = 0$ in $\mathbb{R}$:

  • Equation: $x^2 - 3x + 2 = 0$
  • Factorization: $(x - 1)(x - 2) = 0$
  • Solutions: $x = 1$ or $x = 2$
  • Solution Set: $S = \{1, 2\}$

• Negation of Proposition $(P)$:

  • Given Proposition: $(P): (\forall (a, b) \in \mathbb{R}^2): f(a) = f(b) \implies a = b$
  • Negation: $\overline{P}: (\exists (a, b) \in \mathbb{R}^2): [f(a) = f(b) \text{ et } a \ne b]$

• Deducing $(P)$ is False:

  • Choose $a = 1$ and $b = 2$.
  • From the roots solved above, $f(1) = 0$ and $f(2) = 0$, so $f(1) = f(2)$.
  • Since $1 \ne 2$, the negation $\overline{P}$ holds true.
  • Conclusion: Proposition $(P)$ is false (meaning $f$ is not injective).

• Evaluation of $f(1)$ and $f(-1)$ and Function Parity Analysis:

  • Calculation of $f(1)$: $f(1) = 1^2 - 3(1) + 2 = 0$
  • Calculation of $f(-1)$: $f(-1) = (-1)^2 - 3(-1) + 2 = 1 + 3 + 2 = 6$
  • Testing Evenness Condition ($(\forall x): f(-x) = f(x)$):
  • For $x = 1$, $f(-1) = 6$ and $f(1) = 0$. Since $6 \ne 0$, $f(-1) \ne f(1)$. Thus, $f$ is not even.
  • Testing Oddness Condition ($(\forall x): f(-x) = -f(x)$):
  • For $x = 1$, $f(-1) = 6$ and $-f(1) = -0 = 0$. Since $6 \ne 0$, $f(-1) \ne -f(1)$. Thus, $f$ is not odd.
  • Conclusion: The function $f$ is neither even nor odd.

Exercise 4: Direct Implication and Contraposition

• Setting: Real variable $x \in \mathbb{R}$ and proposition $(P): (x^2 = 4x) \implies (x = 0 \text{ ou } x = 4)$

• Direct Proof that $(P)$ is True:

  • Assume the premise $x^2 = 4x$
  • Subtract $4x$ from both sides: $x^2 - 4x = 0$
  • Factor out $x$: $x(x - 4) = 0$
  • Apply zero-product property: $x = 0 \text{ ou } x - 4 = 0$
  • Solving the linear term gives $x = 0 \text{ ou } x = 4$
  • Since the conclusion follows directly from the premise, proposition $(P)$ is true.

• Determining the Contrapositive Implication:

  • General Rule: The contrapositive of $A \implies B$ is $\overline{B} \implies \overline{A}$
  • Here, premise $A$ is $x^2 = 4x$
  • Conclusion $B$ is $(x = 0 \text{ ou } x = 4)$
  • Negation $\overline{B}$: $\overline{(x = 0 \text{ ou } x = 4)} \iff (x \ne 0 \text{ et } x \ne 4)$
  • Negation $\overline{A}$: $x^2 \ne 4x$
  • Contrapositive Form: $(x \ne 0 \text{ et } x \ne 4) \implies x^2 \ne 4x$

Exercise 5: Domain of Definition of Real-Valued Functions

• Function 1: $f(x) = x^4 - 5x - 2$

  • Type: Polynomial function
  • Constraint: Defined for all real numbers
  • Domain of Definition: $D_f = \mathbb{R}$

• Function 2: $f(x) = \frac{x+4}{x^2-4}$

  • Type: Rational function
  • Constraint: Denominator must be non-zero
  • Condition: $x^2 - 4 \ne 0 \iff (x - 2)(x + 2) \ne 0 \iff x \ne 2 \text{ et } x \ne -2$
  • Domain of Definition: $D_f = \mathbb{R} \setminus \{-2, 2\} = ]-\infty, -2[ \cup ]-2, 2[ \cup ]2, +\infty[$

• Function 3: $f(x) = \sqrt{6 - 2x}$

  • Type: Square root function
  • Constraint: Radicand must be non-negative
  • Condition: $6 - 2x \ge 0 \iff 2x \le 6 \iff x \le 3$
  • Domain of Definition: $D_f = ]-\infty, 3]$

• Function 4: $f(x) = \sqrt{x^2 - 2x + 2}$

  • Type: Square root function
  • Constraint: $x^2 - 2x + 2 \ge 0$
  • Discriminant Analysis: $\Delta = (-2)^2 - 4(1)(2) = 4 - 8 = -4 < 0$
  • Sign Analysis: Since $\Delta < 0$ and leading coefficient $a = 1 > 0$, $x^2 - 2x + 2 > 0$ for all $x \in \mathbb{R}$
  • Domain of Definition: $D_f = \mathbb{R}$

• Function 5: $f(x) = \sqrt{x^2 - 5x}$

  • Type: Square root function
  • Constraint: $x^2 - 5x \ge 0$
  • Factorization: $x(x - 5) \ge 0$
  • Roots: $x = 0$ and $x = 5$
  • Sign Table Analysis: The product is positive outside the roots $(-\infty, 0]$ and $[5, +\infty)$, and negative inside $(0, 5)$
  • Domain of Definition: $D_f = ]-\infty, 0] \cup [5, +\infty[$

Exercise 6: Direct Deductive Reasoning

• Proof 1: Let $x \in \mathbb{R}$ and $y \in \mathbb{R}$. Show $(x^2 + y^2 = 2xy) \implies (x = y)$

  • Proof:     $x^2 + y^2 = 2xy \implies x^2 - 2xy + y^2 = 0$$(x - y)^2 = 0$$x - y = 0$$x = y$

• Proof 2: Let $x \in \mathbb{R}$ and $y \in \mathbb{R}$. Show $(1 + xy - x - y = 0) \implies (y = 1 \text{ ou } x = 1)$

  • Proof by Factorization:     $1 + xy - x - y = 0 \implies (1 - x) - y(1 - x) = 0$$(1 - x)(1 - y) = 0$$1 - x = 0 \text{ ou } 1 - y = 0$$x = 1 \text{ ou } y = 1$

• Proof 3: Show that if $m$ and $n$ are two odd natural integers, then $m + n$ is even

  • Proof:     Since $m$ and $n$ are odd natural numbers, by definition there exist integers $k \in \mathbb{N}$ and $p \in \mathbb{N}$ such that $m = 2k + 1$ and $n = 2p + 1$     Adding the expressions:     $m + n = (2k + 1) + (2p + 1) = 2k + 2p + 2 = 2(k + p + 1)$     Define $k' = k + p + 1 \in \mathbb{N}$. Then $m + n = 2k'$, which matches the definition of an even integer.

Exercise 7: Proof by Logical Equivalence

• Proof 1: For $x \in \mathbb{R}$, show $\frac{x^2 + x + 1}{x^2 + 1} \le \frac{3}{2}$

  • Equivalence Chain:     $\frac{x^2 + x + 1}{x^2 + 1} \le \frac{3}{2} \iff \frac{3}{2} - \frac{x^2 + x + 1}{x^2 + 1} \ge 0$$\iff \frac{3(x^2 + 1) - 2(x^2 + x + 1)}{2(x^2 + 1)} \ge 0$$\iff \frac{3x^2 + 3 - 2x^2 - 2x - 2}{2(x^2 + 1)} \ge 0$$\iff \frac{x^2 - 2x + 1}{2(x^2 + 1)} \ge 0$$\iff \frac{(x - 1)^2}{2(x^2 + 1)} \ge 0$
  • Since $(x - 1)^2 \ge 0$ and $2(x^2 + 1) > 0$ for all real $x$, the final inequality is unconditionally true. Thus, by equivalence, the initial inequality holds.

• Proof 2: For $x, y \in \mathbb{R}^+$, show $\sqrt{x + y} = \sqrt{x} + \sqrt{y} \iff (x = 0 \text{ ou } y = 0)$

  • Equivalence Chain (squaring non-negative expressions):     $\sqrt{x + y} = \sqrt{x} + \sqrt{y} \iff (\sqrt{x + y})^2 = (\sqrt{x} + \sqrt{y})^2$$\iff x + y = x + 2\sqrt{x}\sqrt{y} + y$$\iff 0 = 2\sqrt{xy}$$\iff \sqrt{xy} = 0$$\iff xy = 0$$\iff x = 0 \text{ ou } y = 0$

• Proof 3: For $a, b \in \mathbb{R}^+$, show $(a + b = 0) \iff (a = 0 \text{ et } b = 0)$

  • Right-to-Left Implication ($\Leftarrow$):     If $a = 0$ and $b = 0$, then $a + b = 0 + 0 = 0$.
  • Left-to-Right Implication ($\Rightarrow$):     Assume $a + b = 0$. Since $a \ge 0$ and $b \ge 0$, if either $a$ or $b$ were strictly positive, the sum $a + b$ would be strictly positive ($> 0$). Hence, for non-negative terms to sum to zero, both must be zero ($a = 0$ and $b = 0$).

• Proof 4: For $x, y \in \mathbb{R}^+$, show $(x + y + 13 = 4\sqrt{x} + 6\sqrt{y}) \iff (x = 4 \text{ et } y = 9)$

  • Equivalence Chain:     $x + y + 13 = 4\sqrt{x} + 6\sqrt{y} \iff x - 4\sqrt{x} + y - 6\sqrt{y} + 13 = 0$$\iff (\sqrt{x})^2 - 4\sqrt{x} + 4 + (\sqrt{y})^2 - 6\sqrt{y} + 9 = 0$$\iff (\sqrt{x} - 2)^2 + (\sqrt{y} - 3)^2 = 0$
  • Since squares of real numbers are non-negative, the sum of two squares equals zero if and only if each squared term is zero:     $\iff \sqrt{x} - 2 = 0 \text{ et } \sqrt{y} - 3 = 0$$\iff \sqrt{x} = 2 \text{ et } \sqrt{y} = 3$$\iff x = 4 \text{ et } y = 9$

Exercise 8: Proof by Disjunction of Cases

• Problem 1: Show that for all $n \in \mathbb{N}$, $n^2 + n + 1$ is odd using cases $n = 2k$ and $n = 2k + 1$

  • Case 1 ($n$ is even, $n = 2k$ where $k \in \mathbb{N}$):     $n^2 + n + 1 = (2k)^2 + 2k + 1 = 4k^2 + 2k + 1 = 2(2k^2 + k) + 1$     Set $k' = 2k^2 + k \in \mathbb{N}$. $n^2 + n + 1 = 2k' + 1$, which is odd.
  • Case 2 ($n$ is odd, $n = 2k + 1$ where $k \in \mathbb{N}$):     $n^2 + n + 1 = (2k + 1)^2 + (2k + 1) + 1 = 4k^2 + 4k + 1 + 2k + 1 + 1$$= 4k^2 + 6k + 3 = 2(2k^2 + 3k + 1) + 1$     Set $k'' = 2k^2 + 3k + 1 \in \mathbb{N}$. $n^2 + n + 1 = 2k'' + 1$, which is odd.
  • Conclusion: In all cases, $n^2 + n + 1$ is odd.

• Problem 2: Show that $n(n + 1)(n + 2)$ is a multiple of 3 using cases $n = 3k$, $n = 3k + 1$, $n = 3k + 2$

  • Case 1 ($n = 3k$):     $n(n + 1)(n + 2) = 3k(3k + 1)(3k + 2) = 3[k(3k + 1)(3k + 2)]$, divisible by 3.
  • Case 2 ($n = 3k + 1$):     $n + 2 = (3k + 1) + 2 = 3k + 3 = 3(k + 1)$$n(n + 1)(n + 2) = (3k + 1)(3k + 2) \cdot 3(k + 1) = 3[(3k + 1)(3k + 2)(k + 1)]$     divisible by 3.
  • Case 3 ($n = 3k + 2$):     $n + 1 = (3k + 2) + 1 = 3k + 3 = 3(k + 1)$$n(n + 1)(n + 2) = (3k + 2) \cdot 3(k + 1) \cdot (3k + 4) = 3[(3k + 2)(k + 1)(3k + 4)]$     divisible by 3.
  • Conclusion: $n(n + 1)(n + 2)$ is always a multiple of 3.

• Problem 3: Show $(\forall x \in \mathbb{R}): \sqrt{x^2 + 1} - x > 0$ using cases $x < 0$ and $x \ge 0$

  • Case 1 ($x < 0$):     Since $x < 0$, $-x > 0$. Additionally, $\sqrt{x^2 + 1} > 0$.     The sum of two strictly positive numbers $\sqrt{x^2 + 1} + (-x) = \sqrt{x^2 + 1} - x > 0$
  • Case 2 ($x \ge 0$):     $x^2 + 1 > x^2 \implies \sqrt{x^2 + 1} > \sqrt{x^2} = |x| = x$ (since $x \ge 0$).     Subtracting $x$ from both sides yields $\sqrt{x^2 + 1} - x > 0$
  • Conclusion: The inequality holds for all $x \in \mathbb{R}$.

• Problem 4: Solve equations in $\mathbb{R}$ using disjunction of cases:

  • Equation $(E_1): x^2 - |x - 1| - 1 = 0$

  • Case 1 ($x < 1 \implies |x - 1| = -(x - 1) = 1 - x$):       $x^2 - (1 - x) - 1 = 0 \iff x^2 + x - 2 = 0$       Factorization: $(x + 2)(x - 1) = 0 \implies x = -2 \text{ ou } x = 1$       Filtering by constraint $x < 1$ gives solution $S_1 = \{-2\}$

  • Case 2 ($x \ge 1 \implies |x - 1| = x - 1$):       $x^2 - (x - 1) - 1 = 0 \iff x^2 - x = 0 \iff x(x - 1) = 0 \implies x = 0 \text{ ou } x = 1$       Filtering by constraint $x \ge 1$ gives solution $S_2 = \{1\}$

  • Total Solution Set: $S = S_1 \cup S_2 = \{-2, 1\}$

  • Equation $(E_2): |x + 1| - 3|x - 2| + 1 = 0$

  • Partitioning $\mathbb{R}$ around critical points $x = -1$ and $x = 2$:

  • Sub-case 1 ($x \in ]-\infty, -1[$):       $|x + 1| = -x - 1$ and $|x - 2| = -(x - 2) = 2 - x$$-x - 1 - 3(2 - x) + 1 = 0 \iff 2x - 6 = 0 \iff x = 3$       Since $3 \notin ]-\infty, -1[$, there are no solutions in this interval.

  • Sub-case 2 ($x \in [-1, 2]$):       $|x + 1| = x + 1$ and $|x - 2| = 2 - x$$(x + 1) - 3(2 - x) + 1 = 0 \iff 4x - 4 = 0 \iff x = 1$       Since $1 \in [-1, 2]$, $x = 1$ is a valid solution.

  • Sub-case 3 ($x \in ]2, +\infty[$):       $|x + 1| = x + 1$ and $|x - 2| = x - 2$$(x + 1) - 3(x - 2) + 1 = 0 \iff -2x + 8 = 0 \iff x = 4$       Since $4 \in ]2, +\infty[$, $x = 4$ is a valid solution.

  • Total Solution Set: $S = \{1, 4\}$

Exercise 9: Proof by Contrapositive

• Problem 1a: For $y \in \mathbb{R}$ and $x \in \mathbb{R}^*$, show $(y \ne 2 \text{ et } y \ne -2) \implies (2y^2 - 8 \ne 0)$

  • Contrapositive Statement: $(2y^2 - 8 = 0) \implies (y = 2 \text{ ou } y = -2)$
  • Proof of Contrapositive:     $2y^2 - 8 = 0 \implies 2(y^2 - 4) = 0 \implies y^2 = 4 \implies y = 2 \text{ ou } y = -2$
  • Since the contrapositive is true, the original implication holds.

• Problem 1b: For $x \in \mathbb{R}^*$, show $(x \ne 0) \implies \left(\sqrt{x + 1} \ne 1 + \frac{x}{2}\right)$

  • Contrapositive Statement: $\left(\sqrt{x + 1} = 1 + \frac{x}{2}\right) \implies (x = 0)$
  • Proof of Contrapositive:     Assume $\sqrt{x + 1} = 1 + \frac{x}{2}$     Squaring both sides:     $x + 1 = \left(1 + \frac{x}{2}\right)^2 = 1 + x + \frac{x^2}{4}$     Subtracting $x + 1$ from both sides:     $0 = \frac{x^2}{4} \implies x^2 = 0 \implies x = 0$
  • Since the contrapositive is true, the original implication holds.

• Problem 2: For $n \in \mathbb{N}$, show that if $n^2$ is even, then $n$ is even

  • Contrapositive Statement: If $n$ is odd, then $n^2$ is odd.
  • Proof of Contrapositive:     Assume $n$ is odd, so $n = 2k + 1$ for some $k \in \mathbb{N}$.     $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 = 2k' + 1$     where $k' = 2k^2 + 2k \in \mathbb{N}$. Thus, $n^2$ is odd.
  • Conclusion: By contraposition, if $n^2$ is even, then $n$ is even.

• Problem 3: For $x, y \in ]2; +\infty[$, show $(x \ne y) \implies (x^2 - 4x \ne y^2 - 4y)$

  • Contrapositive Statement: $(x^2 - 4x = y^2 - 4y) \implies (x = y)$
  • Proof of Contrapositive:     Assume $x^2 - 4x = y^2 - 4y$$x^2 - y^2 - 4x + 4y = 0 \implies (x - y)(x + y) - 4(x - y) = 0$$(x - y)(x + y - 4) = 0$     Since $x > 2$ and $y > 2$, adding the inequalities gives $x + y > 4$, which implies $x + y - 4 > 0$.     Since $x + y - 4 \ne 0$, we divide by $(x + y - 4)$ to get $x - y = 0 \implies x = y$
  • Conclusion: The original implication is proved.

Exercise 10: Proof by Contradiction (Absurdity)

• Problem 1: Show that $\left(\forall x \in \mathbb{R} - \left\{\frac{2}{3}\right\}\right): \frac{4x + 1}{3x - 2} \ne \frac{4}{3}$

  • Proof by Contradiction:     Assume there exists $x \in \mathbb{R} \setminus \left\{\frac{2}{3}\right\}$ such that $\frac{4x + 1}{3x - 2} = \frac{4}{3}$     Cross-multiplying yields:     $3(4x + 1) = 4(3x - 2)$$12x + 3 = 12x - 8$     Subtracting $12x$ from both sides:     $3 = -8$     This is an impossible mathematical contradiction. Hence, the original proposition is true.

• Problem 2: Show that $(\forall n \in \mathbb{N}): \frac{6n + 5}{4n + 2} \notin \mathbb{N}$

  • Proof by Contradiction:     Assume there exists $n \in \mathbb{N}$ such that $k = \frac{6n + 5}{4n + 2} \in \mathbb{N}$$6n + 5 = k(4n + 2) = 2k(2n + 1)$     Analyzing parity:     Left side: $6n + 5 = 2(3n + 2) + 1$, which is an odd integer.     Right side: $2[k(2n + 1)]$, which is an even integer.     An odd integer cannot equal an even integer (contradiction). Thus, $\frac{6n + 5}{4n + 2} \notin \mathbb{N}$.

• Problem 3: Show that $(\forall x \in \mathbb{R}): x - \sqrt{x^2 + 1} < 0$

  • Proof by Contradiction:     Assume there exists $x \in \mathbb{R}$ such that $x - \sqrt{x^2 + 1} \ge 0$     Rearranging gives $x \ge \sqrt{x^2 + 1}$     Since $\sqrt{x^2 + 1} > 0$, $x$ must be strictly positive ($x > 0$).     Squaring both non-negative sides:     $x^2 \ge (\sqrt{x^2 + 1})^2 \implies x^2 \ge x^2 + 1 \implies 0 \ge 1$     This is a contradiction. Therefore, $x - \sqrt{x^2 + 1} < 0$ for all $x \in \mathbb{R}$.

Exercise 11: Mathematical Induction and Summation Formulas

• Setting: For all $n \in \mathbb{N}^*$, let $S_n = 1 + 2 + \dots + n$

• Calculating First Terms:

  • $S_1 = 1$
  • $S_2 = 1 + 2 = 3$
  • $S_3 = 1 + 2 + 3 = 6$

• Proof by Recurrence of Formula $S_n = \frac{n(n + 1)}{2}$:

  • Initialization: For $n = 1$, $S_1 = 1$ and $\frac{1(1 + 1)}{2} = \frac{2}{2} = 1$. The formula holds for $n = 1$
  • Heredity: Fix $k \in \mathbb{N}^*$. Assume $S_k = \frac{k(k + 1)}{2}$. Prove $S_{k+1} = \frac{(k + 1)(k + 2)}{2}$.     $S_{k+1} = S_k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1)$     Factor out $(k + 1)$:     $S_{k+1} = (k + 1)\left(\frac{k}{2} + 1\right) = (k + 1)\left(\frac{k + 2}{2}\right) = \frac{(k + 1)(k + 2)}{2}$
  • Conclusion: By induction, $(\forall n \in \mathbb{N}^*): S_n = \frac{n(n + 1)}{2}$

• Deducing Parity of $n(n + 1)$:

  • Since $S_n = \frac{n(n + 1)}{2} \in \mathbb{N}$ as a sum of natural integers, multiplying both sides by 2 gives $n(n + 1) = 2S_n$.
  • Because $n(n + 1)$ is expressed as $2$ times an integer $S_n$, $n(n + 1)$ is always even.

• Calculating $S_{100}$:

  • $S_{100} = \frac{100(100 + 1)}{2} = 50 \times 101 = 5050$

Exercise 12: Divisibility, Inequalities, and Sums by Recurrence

• Problem 1: Prove $(\forall n \in \mathbb{N}^*): 7^n - 2^n$ is divisible by 5

  • Initialization: For $n = 1$, $7^1 - 2^1 = 5 = 5 \times 1$, divisible by 5. True for $n = 1$
  • Heredity: Let $k \in \mathbb{N}^*$. Assume $7^k - 2^k = 5m$ for some $m \in \mathbb{N}$.     $7^{k+1} - 2^{k+1} = 7 \cdot 7^k - 2 \cdot 2^k = 7 \cdot 7^k - 7 \cdot 2^k + 7 \cdot 2^k - 2 \cdot 2^k$$= 7(7^k - 2^k) + 2^k(7 - 2) = 7(5m) + 5(2^k) = 5(7m + 2^k)$     Since $7m + 2^k \in \mathbb{N}$, $7^{k+1} - 2^{k+1}$ is divisible by 5.
  • Conclusion: $7^n - 2^n$ is divisible by 5 for all $n \in \mathbb{N}^*$

• Problem 2: Prove $(\forall n \in \mathbb{N}): 1 + 4 + 4^2 + \dots + 4^n = \frac{4^{n+1} - 1}{3}$

  • Initialization: For $n = 0$, Left Side = $4^0 = 1$, Right Side = $\frac{4^{0+1} - 1}{3} = \frac{3}{3} = 1$. True for $n = 0$
  • Heredity: Let $k \in \mathbb{N}$. Assume $1 + 4 + \dots + 4^k = \frac{4^{k+1} - 1}{3}$.     $1 + 4 + \dots + 4^k + 4^{k+1} = \frac{4^{k+1} - 1}{3} + 4^{k+1} = \frac{4^{k+1} - 1 + 3 \cdot 4^{k+1}}{3}$$= \frac{4 \cdot 4^{k+1} - 1}{3} = \frac{4^{k+2} - 1}{3}$
  • Conclusion: True for all $n \in \mathbb{N}$

• Problem 3: Prove $(\forall n \in \mathbb{N}): 1 + 2^3 + 3^3 + \dots + n^3 = \left[\frac{n(n + 1)}{2}\right]^2$

  • Initialization: For $n = 0$, sum is $0$ and $\left[\frac{0}{2}\right]^2 = 0$. For $n = 1$, $1^3 = 1$ and $\left[\frac{1(2)}{2}\right]^2 = 1$. True.
  • Heredity: Assume true for $k \in \mathbb{N}$.     $1^3 + 2^3 + \dots + k^3 + (k + 1)^3 = \left[\frac{k(k + 1)}{2}\right]^2 + (k + 1)^3$$= (k + 1)^2 \left[ \frac{k^2}{4} + (k + 1) \right] = (k + 1)^2 \left[ \frac{k^2 + 4k + 4}{4} \right]$$= (k + 1)^2 \frac{(k + 2)^2}{4} = \left[\frac{(k + 1)(k + 2)}{2}\right]^2$
  • Conclusion: True for all $n \in \mathbb{N}$

• Problem 4: Prove $(\forall n \in \mathbb{N}): 2^n \ge n$

  • Initialization: For $n = 0$, $2^0 = 1 \ge 0$. True for $n = 0$
  • Heredity: Let $k \in \mathbb{N}$. Assume $2^k \ge k$.     $2^{k+1} = 2 \cdot 2^k \ge 2k = k + k$     For $k \ge 1$, $k + k \ge k + 1$, so $2^{k+1} \ge k + 1$.     For $k = 0$, $2^1 = 2 \ge 1$, which also holds.
  • Conclusion: $2^n \ge n$ for all $n \in \mathbb{N}$