Discrete Mathematics : Recitations

Contents

• Session 1: Propositional logic
• Session 2: Propositional logic
• Session 3: Predicate logic
• Session 4: Proof techniques
• Session 5: Proof techniques
• Session 6: Sequences
• Session 7: Sequences
• Session 8: Midterm
• Session 9: Sets
• Session 10: Functions
• Session 11: Functions
• Session 12: Relations
• Session 13: Final

Session 1: Propositional logic

Expression	Equivalent expression
$p \rightarrow q$	$\equiv \sim p \lor q$
$p$ implies $q$	$\equiv p \rightarrow q$
(Contrapositive of $p \rightarrow q$)	$\equiv \sim q \rightarrow \sim p$
(Converse of $p \rightarrow q$)	$\equiv q \rightarrow p$
(Inverse of $p \rightarrow q$)	$\equiv \sim p \rightarrow \sim q$
$p$ is sufficient for $q$	$\equiv p \rightarrow q$
$p$ is not sufficient for $q$	$\equiv \sim (p \rightarrow q)$
$p$ is necessary for $q$	$\equiv q \rightarrow p$
$p$ is not necessary for $q$	$\equiv \sim (q \rightarrow p)$
$p$ if $q$	$\equiv q \rightarrow p$
$p$ only if $q$	$\equiv p \rightarrow q$
$p$ if and only if $q$	$\equiv p \leftrightarrow q$
$p$ when/whenever $q$	$\equiv q \rightarrow p$
$p$ unless $q$	$\equiv \sim q \rightarrow p$
$p$ follows from $q$	$\equiv q \rightarrow p$
$p$, provided that $q$	$\equiv q \rightarrow p$

Solution

$p$	$q$	$r$	$p \oplus q$	$\sim q$	$\sim r$	$\sim q \rightarrow \sim r$	$(p \oplus q) \leftrightarrow (\sim q \rightarrow \sim r)$
$T$	$T$	$T$	$F$	$F$	$F$	$T$	$F$
$T$	$T$	$F$	$F$	$F$	$T$	$T$	$F$
$T$	$F$	$T$	$T$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$T$	$T$	$F$	$F$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$T$	$T$	$T$
$F$	$F$	$T$	$F$	$T$	$F$	$F$	$T$
$F$	$F$	$F$	$F$	$T$	$T$	$T$	$F$

Solution

$p$	$q$	$r$	$\sim p$	$q \land r$	$q \lor r$	$\sim p \rightarrow (q \land r)$	$\sim p \lor (q \lor r)$
$T$	$T$	$T$	$F$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$F$	$T$	$T$	$T$
$T$	$F$	$T$	$F$	$F$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$F$	$T$	$F$
$F$	$T$	$T$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$T$	$F$	$T$
$F$	$F$	$T$	$T$	$F$	$T$	$F$	$T$
$F$	$F$	$F$	$T$	$F$	$F$	$F$	$T$

The 7th and 8th columns are different at rows 4, 6, 7, and 8.
So, $\sim p \rightarrow (q \land r) \not\equiv \sim p \lor (q \lor r)$.

Solution (Subproblem 1)

Let $p$ denote ''Jules solved this problem correctly'' and $q$ denote ''Jules obtained the answer 2''.
Logical form: \begin{align*} & p \rightarrow q \\ & q \\ & \therefore p \end{align*} Invalid (Converse error). A conditional is not equivalent to its converse. When $p$ is false and $q$ is true, both premises are true but the conclusion is false.

Solution (Subproblem 2)

Let $p$ denote ''This real number is rational'' and $q$ denote ''This real number is irrational''.
Logical form: \begin{align*} & p \lor q \\ & \sim p \\ & \therefore q \end{align*} Valid (Elimination).

Solution (Subproblem 3)

Let $p$ denote ''I go to the movies'', $q$ denote ''I finish my homework'', and $r$ denote ''I do well on the exam tomorrow''.
Logical form: \begin{align*} & p \rightarrow \sim q \\ & \sim q \rightarrow \sim r \\ & \therefore p \rightarrow \sim r \end{align*} Valid (Transitivity). Here $\sim q$ plays the role of the middle statement in the rule.

Solution (Subproblem 4)

Let $p$ denote ''This number is larger than 2'' and $q$ denote ''The square of this number is larger than 4''.
Logical form: \begin{align*} & p \rightarrow q \\ & \sim p \\ & \therefore \sim q \end{align*} Invalid (Inverse error). A conditional is not equivalent to its inverse. When $p$ is false and $q$ is true, both premises are true but the conclusion is false. (For example, the number $-3$ is not larger than 2, but its square, 9, is larger than 4.)

Solution

				Premises			Conclusion
$p$	$q$	$r$	$\sim q$	$p$	$p \rightarrow q$	$\sim q \lor r$	$r$
$T$	$T$	$T$	$F$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$	$T$	$T$	$F$	$F$
$T$	$F$	$T$	$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$F$	$F$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$F$	$T$	$T$	$T$
$F$	$F$	$F$	$T$	$F$	$T$	$T$	$F$

A row in which all the premises are true is a critical row. An argument form is valid if the conclusion is true in every critical row.
Only row 1 (the highlighted row) is a critical row, and the conclusion $r$ is true in it.
So, the argument form is valid.

Session 2: Propositional logic

Solution

				Premises			Conclusion
$p$	$q$	$r$	$\sim q$	$p \lor q$	$p \rightarrow \sim q$	$p \rightarrow r$	$r$
$T$	$T$	$T$	$F$	$T$	$F$	$T$	$T$
$T$	$T$	$F$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$F$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$T$	$F$	$T$	$T$	$T$
$F$	$F$	$F$	$T$	$F$	$T$	$T$	$F$

A row in which all the premises are true is a critical row. An argument form is invalid if the conclusion is false in at least one critical row.
Rows 3, 5, and 6 are critical rows. In row 6 ($p$ is false, $q$ is true, and $r$ is false), all the premises are true but the conclusion $r$ is false.
So, the argument form is invalid.

Solution

By the precedence of the logical operators, (a) is $(\sim p \lor q) \rightarrow r$ and (e) is $(\sim p \land r) \rightarrow \sim s$.

1. \begin{align*} & p \rightarrow t && \text{by (d)} \\ & \sim t && \text{by (c)} \\ & \therefore \sim p && \text{by modus tollens} \end{align*}

2. \begin{align*} & \sim p && \text{by the conclusion of (1)} \\ & \therefore \sim p \lor q && \text{by generalization} \end{align*}

3. \begin{align*} & (\sim p \lor q) \rightarrow r && \text{by (a)} \\ & \sim p \lor q && \text{by the conclusion of (2)} \\ & \therefore r && \text{by modus ponens} \end{align*}

4. \begin{align*} & \sim p && \text{by the conclusion of (1)} \\ & r && \text{by the conclusion of (3)} \\ & \therefore \sim p \land r && \text{by conjunction} \end{align*}

5. \begin{align*} & (\sim p \land r) \rightarrow \sim s && \text{by (e)} \\ & \sim p \land r && \text{by the conclusion of (4)} \\ & \therefore \sim s && \text{by modus ponens} \end{align*}

6. \begin{align*} & s \lor \sim q && \text{by (b)} \\ & \sim s && \text{by the conclusion of (5)} \\ & \therefore \sim q && \text{by elimination} \end{align*}

Thus, $\sim q$ follows from the premises.

Solution

By the precedence of the logical operators, (a) is $\sim p \rightarrow (r \land \sim s)$.

1. \begin{align*} & u \lor w && \text{by (e)} \\ & \sim w && \text{by (d)} \\ & \therefore u && \text{by elimination} \end{align*}

2. \begin{align*} & u \rightarrow \sim p && \text{by (c)} \\ & u && \text{by the conclusion of (1)} \\ & \therefore \sim p && \text{by modus ponens} \end{align*}

3. \begin{align*} & \sim p \rightarrow (r \land \sim s) && \text{by (a)} \\ & \sim p && \text{by the conclusion of (2)} \\ & \therefore r \land \sim s && \text{by modus ponens} \end{align*}

4. \begin{align*} & r \land \sim s && \text{by the conclusion of (3)} \\ & \therefore \sim s && \text{by specialization} \end{align*}

5. \begin{align*} & t \rightarrow s && \text{by (b)} \\ & \sim s && \text{by the conclusion of (4)} \\ & \therefore \sim t && \text{by modus tollens} \end{align*}

Thus, $\sim t$ follows from the premises.

Session 3: Predicate logic

Session 4: Proof techniques

Proof

Direct proof.
Formal statement: $\forall$ integer $n$, if $n$ is odd, then $3n+5$ is even.
Suppose $n$ is odd. Then: \begin{align*} & 3n + 5 \\ &= 3(2k+1) + 5 && \text{(defn. of odd, } n = 2k+1 \text{ for integer } k \text{)}\\ &= 6k + 8 && \text{(simplifying)}\\ &= 2(3k+4) && \text{(taking 2 as common factor)}\\ &= 2p && \text{(} p = 3k+4 \text{ and mult. and add. are closed on integers)}\\ &= \text{even} && \text{(defn. of even)}\\ \end{align*}

Proof

Direct proof.
Formal statement: $\forall$ integers $a, b$, if $a$ and $b$ are odd, then $a^2 + b^2$ is even.
Suppose $a$ and $b$ are odd. Then: \begin{align*} & a^2 + b^2 \\ &= (2m+1)^2 + (2n+1)^2 && \text{(defn. of odd; } a = 2m+1, b = 2n+1 \text{)}\\ &= 4m^2 + 4m + 1 + 4n^2 + 4n + 1 && \text{(expand)}\\ &= 2(2m^2 + 2m + 2n^2 + 2n + 1) && \text{(taking 2 as common factor)}\\ &= 2p && \text{(} p = 2m^2 + 2m + 2n^2 + 2n + 1 \text{ is an integer)}\\ &= \text{even} && \text{(defn. of even)}\\ \end{align*}

Proof

Direct proof.
Formal statement: $\forall$ integer $n \gt 4$, if $n$ is a perfect square, then $n-1$ is not prime.
Suppose $n \gt 4$ is a perfect square. Then: \begin{align*} & n = k^2 \text{ for some integer } k \ge 0 && \text{(defn. of perfect square; take } k \ge 0 \text{)}\\ & \implies k^2 \gt 4 && \text{(} n \gt 4 \text{)}\\ & \implies k \ge 3 && \text{(} k \text{ is a nonnegative integer)}\\ \end{align*} Now consider $n - 1$. \begin{align*} & n - 1 \\ &= k^2 - 1 && \text{(} n = k^2 \text{)}\\ &= (k-1)(k+1) && \text{(difference of two squares)}\\ &= \text{composite} && \text{(} 1 \lt k-1 \lt n-1 \text{ and } 1 \lt k+1 \lt n-1 \text{; see below)}\\ \end{align*} We have $1 \lt k-1$ and $1 \lt k+1$ since $k \ge 3$. Also, $k-1 \lt (k-1)(k+1) = n-1$ since $k+1 \gt 1$, and $k+1 \lt (k-1)(k+1) = n-1$ since $k-1 \gt 1$. So $n-1$ is a product of two natural numbers that are strictly between $1$ and $n-1$. Hence $n-1$ is composite, and so it is not prime.

Solution

False!
Counterexample: $a = -3$ and $b = 2$.
In this example, $a^2 = 9 \gt 4 = b^2$ but $a \lt b$.

Expression	Result	Proof technique
rational + rational	rational	Direct proof
rational + irrational	irrational	Contradiction
irrational + irrational	rational or irrational	Examples: $\sqrt{2} + (-\sqrt{2}) = 0$ and $\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2}} = \sqrt{2}$
rational $\times$ rational	rational	Direct proof
rational $\times$ irrational	rational or irrational	Examples $0 \times \sqrt{2} = 0$ and $1 \times \sqrt{2} = \sqrt{2}$
irrational $\times$ irrational	rational or irrational	Examples $\sqrt{2} \times \sqrt{2} = 2$ and $\sqrt{2} \times \sqrt{3} = \sqrt{6}$
nonzero rational $\times$ irrational	irrational	Contradiction
rational$^{\text{rational}}$	rational or irrational	Examples $1^1 = 1$ and $2^{1/2} = \sqrt{2}$

Session 5: Proof techniques

Proof

Proof by contradiction.
Negation. Suppose there are positive real numbers $r$ and $s$ such that $\sqrt{r+s} = \sqrt{r} + \sqrt{s}$. \begin{align*} & \sqrt{r+s} = \sqrt{r} + \sqrt{s} \\ & \implies r + s = r + 2\sqrt{r}\sqrt{s} + s && \text{(squaring on both sides)}\\ & \implies 0 = 2\sqrt{r}\sqrt{s} && \text{(subtracting } r + s \text{ from both sides)}\\ & \implies \sqrt{r}\sqrt{s} = 0 && \text{(dividing by 2)}\\ & \implies \sqrt{r} = 0 \text{ or } \sqrt{s} = 0 && \text{(a product is zero only if a factor is zero)}\\ & \implies r = 0 \text{ or } s = 0 && \text{(squaring)}\\ \end{align*} Contradiction! Both $r$ and $s$ are positive. Hence, the proposition is true.

Proof 2

Proof by contraposition.
Contrapositive. If $\sqrt{r+s} = \sqrt{r} + \sqrt{s}$, then $r$ and $s$ are not both positive. \begin{align*} & \sqrt{r+s} = \sqrt{r} + \sqrt{s} \\ & \implies r + s = r + 2\sqrt{r}\sqrt{s} + s && \text{(squaring on both sides)}\\ & \implies \sqrt{r}\sqrt{s} = 0 && \text{(subtracting } r + s \text{ and dividing by 2)}\\ & \implies r = 0 \text{ or } s = 0 && \text{(a product is zero only if a factor is zero)}\\ & \implies r \text{ and } s \text{ are not both positive} && \text{(} 0 \text{ is not positive)}\\ \end{align*} Hence, the proposition is true.

Proof

Proof by contradiction.
Negation. Suppose $n^2 + 3n - 7$ is even and $n$ is even. \begin{align*} & n \text{ is even} \\ & \implies n = 2k && \text{(defn. of even, } k \in \mathbb{Z} \text{)}\\ & \implies n^2 + 3n - 7 = 4k^2 + 6k - 7 && \text{(substitute } n = 2k \text{)}\\ & \implies n^2 + 3n - 7 = 2(2k^2 + 3k - 4) + 1 && \text{(take 2 common)}\\ & \implies n^2 + 3n - 7 \text{ is odd} && \text{(defn. of odd, } 2k^2 + 3k - 4 \in \mathbb{Z} \text{)}\\ \end{align*} Contradiction! $n^2 + 3n - 7$ is even, but an integer cannot be both even and odd. Hence, the proposition is true.

Proof 2

Proof by contraposition.
Contrapositive. If $n$ is even, then $n^2 + 3n - 7$ is odd. \begin{align*} & n \text{ is even} \\ & \implies n = 2k && \text{(defn. of even, } k \in \mathbb{Z} \text{)}\\ & \implies n^2 + 3n - 7 = 4k^2 + 6k - 7 && \text{(substitute } n = 2k \text{)}\\ & \implies n^2 + 3n - 7 = 2(2k^2 + 3k - 4) + 1 && \text{(take 2 common)}\\ & \implies n^2 + 3n - 7 \text{ is odd} && \text{(defn. of odd, } 2k^2 + 3k - 4 \in \mathbb{Z} \text{)}\\ \end{align*} Hence, the contrapositive is true, and so the proposition is true.

Proof

Proof by contraposition and division into cases.
Contrapositive. For integers $a$, $b$, $c$, if $a$ and $b$ are odd, then $a^2 + b^2 \ne c^2$.
Suppose $a$ and $b$ are odd. Consider \begin{align*} & a^2 + b^2 \\ &= (2m+1)^2 + (2n+1)^2 && \text{(defn. of odd; } a = 2m+1, b = 2n+1 \text{)}\\ &= 4m^2 + 4n^2 + 4m + 4n + 2 && \text{(expand)}\\ &= 4(m^2 + n^2 + m + n) + 2 && \text{(take common factor)}\\ &\equiv 2 \bmod 4 && \text{(remainder is 2 when divided by 4)}\\ \end{align*} Now let $c$ be any integer. We know $c = 2k$ or $c = 2k+1$ (quotient-remainder theorem). So we have two cases:

• Case 1. $c$ is even. \begin{align*} & c = 2k && \text{(defn. of even)}\\ & \implies c^2 = 4k^2 && \text{(squaring)}\\ & \implies c^2 \equiv 0 \bmod 4 && \text{(remainder is 0 when divided by 4)}\\ \end{align*}
• Case 2. $c$ is odd. \begin{align*} & c = 2k+1 && \text{(defn. of odd)}\\ & \implies c^2 = 4(k^2 + k) + 1 && \text{(squaring and taking common factor)}\\ & \implies c^2 \equiv 1 \bmod 4 && \text{(remainder is 1 when divided by 4)}\\ \end{align*}

In both cases, $c^2 \not\equiv 2 \bmod 4$ (remainder is never 2 when divided by 4). But $a^2 + b^2 \equiv 2 \bmod 4$. So $a^2 + b^2 \ne c^2$. Hence, the contrapositive is true, and so the proposition is true.

Proof

Direct proof.
Formal statement. $\forall$ nonnegative real numbers $a$ and $b$, $\frac{a+b}{2} \ge \sqrt{ab}.$
Since $a,b \ge 0$, the expression $(\sqrt{a} - \sqrt{b})^2$ is well-defined and nonnegative. Thus, $(\sqrt{a} - \sqrt{b})^2 \ge 0.$
We have

\begin{align*} &(\sqrt{a} - \sqrt{b})^2 \ge 0\\ &\implies a - 2\sqrt{ab} + b \ge 0 && \text{(expand)}\\ &\implies a + b \ge 2\sqrt{ab} && \text{(rewrite)}\\ &\implies \frac{a+b}{2} \ge \sqrt{ab} && \text{(divide by 2)} \end{align*}

Therefore, the arithmetic mean of two nonnegative real numbers is never smaller than the geometric mean.

Proof 2

Proof by contradiction.
Negation: Suppose that there exist nonnegative real numbers $a$ and $b$ such that $\frac{a+b}{2} < \sqrt{ab}.$ Then \begin{align*} &\frac{a+b}{2} < \sqrt{ab} && \text{(supposition of negation)}\\ &\implies a + b < 2\sqrt{ab} && \text{(multiply by 2)}\\ &\implies a + b - 2\sqrt{ab} < 0 && \text{(rewrite)}\\ &\implies (\sqrt{a} - \sqrt{b})^2 < 0 && \text{(simplify)} \end{align*} However, for all real numbers, a square is always nonnegative, so $ (\sqrt{a} - \sqrt{b})^2 \ge 0, $ which is a contradiction. Therefore, our assumption is false, and it must be that $ \frac{a+b}{2} \ge \sqrt{ab} $ for all nonnegative real numbers $a$ and $b$.

Proof

Proof by division into cases.
Let $n$ be any integer. By the quotient-remainder theorem, when $n$ is divided by $3$, exactly one of the following three cases occurs:

• Case 1. $n \equiv 0 \pmod 3$. \begin{align*} & n = 3k && \text{(definition of congruence)}\\ & \implies 3 \mid n && \text{(definition of divisibility)}\\ & \implies 3 \mid n(n+1)(n+2) \end{align*}
• Case 2. $n \equiv 1 \pmod 3$. \begin{align*} & n = 3k+1 && \text{(definition of congruence)}\\ & \implies n+2 = 3k+3 = 3(k+1) && \text{(algebra)}\\ & \implies 3 \mid (n+2) && \text{(definition of divisibility)}\\ & \implies 3 \mid n(n+1)(n+2) \end{align*}
• Case 3. $n \equiv 2 \pmod 3$. \begin{align*} & n = 3k+2 && \text{(definition of congruence)}\\ & \implies n+1 = 3k+3 = 3(k+1) && \text{(algebra)}\\ & \implies 3 \mid (n+1) && \text{(definition of divisibility)}\\ & \implies 3 \mid n(n+1)(n+2) \end{align*}

Therefore, in every case, one of the integers $n$, $n+1$, and $n+2$ is divisible by $3$.
Next, by the quotient-remainder theorem, every integer is either even or odd. So we consider two cases:

• Case 1. $n$ is even. \begin{align*} & n = 2m && \text{(definition of even)}\\ & \implies 2 \mid n && \text{(definition of divisibility)}\\ & \implies 2 \mid n(n+1)(n+2) \end{align*}
• Case 2. $n$ is odd. \begin{align*} & n = 2m+1 && \text{(definition of odd)}\\ & \implies n+1 = 2m+2 = 2(m+1) && \text{(algebra)}\\ & \implies 2 \mid (n+1) && \text{(definition of divisibility)}\\ & \implies 2 \mid n(n+1)(n+2) \end{align*}

We have, $ 2 \mid n(n+1)(n+2) \text{ and } 3 \mid n(n+1)(n+2). $ Since $\gcd(2,3)=1$, it follows that $ 6 \mid n(n+1)(n+2). $ Therefore, the product of three consecutive integers is divisible by $6$.

Session 6: Sequences

Proof

Let $P(n)$ denote ''$\displaystyle\sum_{i=1}^{n-1} i(i+1) = \frac{n(n-1)(n+1)}{3}$.''

• Basis step. $P(2)$ is true because $\displaystyle\sum_{i=1}^{1} i(i+1) = 1 \cdot 2 = 2 = \frac{2 \cdot 1 \cdot 3}{3}$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 2$. We want to show that $P(k+1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= \sum_{i=1}^{k} i(i+1) \\ &= \sum_{i=1}^{k-1} i(i+1) + k(k+1) \\ &= \frac{k(k-1)(k+1)}{3} + k(k+1) && (\because P(k) \text{ is true}) \\ &= k(k+1) \left( \frac{k-1}{3} + 1 \right) && (\because \text{distributive law}) \\ &= \frac{(k+1)k(k+2)}{3} && (\because \text{simplify}) \\ &= \text{RHS of } P(k+1) \end{align*}

Proof

Let $P(n)$ denote ''$\displaystyle\sum_{i=1}^n i(i!) = (n+1)! - 1$.''

• Basis step. $P(1)$ is true because $1 \cdot 1! = 1 = 2! - 1$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 1$. We want to show that $P(k+1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= \sum_{i=1}^{k+1} i(i!) \\ &= \sum_{i=1}^{k} i(i!) + (k+1)(k+1)! \\ &= \left[ (k+1)! - 1 \right] + (k+1)(k+1)! && (\because P(k) \text{ is true}) \\ &= (k+1)! \left[ 1 + (k+1) \right] - 1 && (\because \text{distributive law}) \\ &= (k+2)! - 1 && (\because \text{factorial recursive definition}) \\ &= \text{RHS of } P(k+1) \end{align*}

Proof

Let $P(n)$ denote $\displaystyle \sum_{i=1}^n \frac{1}{i^2} < 2 - \frac{1}{n}$ for $n \ge 2$.

• Basis step. $P(2)$ is true. Because $\displaystyle \frac{1}{1^2} + \frac{1}{2^2} = 1 + \frac{1}{4} = 1.25 < 1.5 = 2 - \frac{1}{2}$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 2$. We need to prove that $P(k + 1)$ is true.
\begin{align*} & \text{LHS of } P(k+1) \\ &= \left( \frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{k^2} \right) + \frac{1}{(k+1)^2} \\ &< \left( 2 - \frac{1}{k} \right) + \frac{1}{(k+1)^2} && (\because P(k) \text{ is true}) \\ &= 2 - \frac{(k+1)^2 - k}{k(k+1)^2} && (\because \text{taking common denominator}) \\ &= 2 - \frac{k(k+1) + 1}{k(k+1)^2} && (\because \text{simplify}) \\ &< 2 - \frac{k(k+1)}{k(k+1)^2} && (\because \text{decrease 1 in the numerator}) \\ &= 2 - \frac{1}{k+1} && (\because \text{canceling common factors}) \\ &= \text{RHS of } P(k+1) \end{align*}

Proof

Let $P(n)$ denote ''$5^{n} - 1$ is divisible by $4$.''

• Basis step. $P(0)$ is true because $5^0 - 1 = 0 = 4 \cdot 0$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 0$. We want to show that $P(k+1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= 5^{k+1} - 1 \\ &= 5 \cdot 5^k - 1 && (\because a^{b+c}=a^b \cdot a^c) \\ &= 5 (4r + 1) - 1 && (\because P(k) \text{ is true, } 5^k - 1 = 4r \text{ for some integer } r) \\ &= 20r + 4 && (\because \text{simplify}) \\ &= 4 (5r + 1) && (\because \text{distributive law}) \\ &= 4 \cdot \text{integer} && (\because \times, + \text{ are closed on integers}) \\ &= \text{RHS of } P(k+1) \end{align*}

Proof

Let $P(n)$ denote ''$x^{n} - y^{n}$ is divisible by $x - y$, s.t. $x \ne y$.''

• Basis step. $P(0)$ is true because $x^0 - y^0 = 1 - 1 = 0 = (x-y) \cdot 0$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 0$. We want to show that $P(k+1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= x^{k+1} - y^{k+1} \\ &= x^{k+1} - x \cdot y^k + x \cdot y^k - y^{k+1} && (\because \text{subtract and add}) \\ &= x \cdot (x^k - y^k) + y^k (x-y) && (\because \text{distributive law}) \\ &= x \cdot (x-y) r + y^k (x-y) && (\because P(k) \text{ is true}) \\ &= (x-y)(xr + y^k) && (\because \text{distributive law}) \\ &= (x-y) \cdot \text{integer} && (\because +, \times, \text{expo are closed on integers}) \\ &= \text{RHS of } P(k+1) \end{align*}

Proof

Let $P(n)$ denote ''$n^{3} - n$ is divisible by $6$.''

• Basis step. $P(0)$ is true because $0^3 - 0 = 0 = 6 \cdot 0$.
• Induction step. Suppose that $P(k)$ is true for some $k \ge 0$. We want to show that $P(k+1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= (k+1)^3 - (k+1) \\ &= (k^3 - k) + (3k^2+3k) && (\because \text{expand and regroup}) \\ &= (k^3 - k) + 3k(k+1) && (\because \text{factor}) \\ &= 6r + 3k(k+1) && (\because P(k) \text{ is true, } k^3 - k = 6r \text{ for some integer } r) \\ &= 6r + 3(2s) && (\because k(k+1) = 2s \text{ for some integer } s\text{; one of two consecutive integers is even}) \\ &= 6(r+s) && (\because \text{distributive law}) \\ &= 6 \cdot \text{integer} && (\because + \text{ is closed on integers}) \\ &= \text{RHS of } P(k+1) \end{align*}

Session 7: Sequences

Proof

Let $P(n)$ denote ''$e_n = 5 \cdot 3^n + 7 \cdot 2^n$.''

• Basis step. $P(0)$ and $P(1)$ are true, because $e_0 = 12 = 5 \cdot 3^0 + 7 \cdot 2^0$ and $e_1 = 29 = 5 \cdot 3^1 + 7 \cdot 2^1$.
• Induction step. Suppose that $P(i)$ is true for some $k \ge 1$ and any $i \in [0, k]$. We want to show that $P(k + 1)$ is true. \begin{align*} & \text{LHS of } P(k+1) \\ &= e_{k+1} \\ &= 5 e_k - 6 e_{k-1} && (\because \text{recursive definition}) \\ &= 5 (5 \cdot 3^k + 7 \cdot 2^k) - 6 (5 \cdot 3^{k-1} + 7 \cdot 2^{k-1}) && (\because P(k), P(k-1) \text{ are true}) \\ &= 5 \cdot 3^{k+1} + 7 \cdot 2^{k+1} && (\because \text{simplify}) \\ &= \text{RHS of } P(k+1) \end{align*}

Solution

Let $P(n)$ denote $(x^n + 1/x^n) \in \mathbb{Z}$ for $n \ge 1$.

• Basis step. $P(1)$ is true. Because $x^1 + 1/x^1 = x + 1/x$, which is an integer by hypothesis.
• Induction step. Suppose that $P(i)$ is true for all $i \in [1, k]$, for some $k \ge 1$. We need to prove that $P(k + 1)$ is true.
  Observation: $\left( x^k + 1/x^k \right) \left( x + 1/x \right) = \left( x^{k+1} + 1/x^{k+1} \right) + \left( x^{k-1} + 1/x^{k-1} \right)$. So, we have \begin{align*} & \text{LHS of } P(k+1) \\ &= \left( x^{k+1} + 1/x^{k+1} \right) \\ &= \left( x^k + 1/x^k \right) \left( x + 1/x \right) - \left( x^{k-1} + 1/x^{k-1} \right) \\ &= \text{integer} \times \text{integer} - \text{integer} && (\because P(k), P(1), P(k-1) \text{ are true}) \\ &= \text{integer} && (\because \times, - \text{ are closed on integers}) \\ &= \text{RHS of } P(k+1) \end{align*}

Solution

Let $P(n)$ denote ''Breaking a chocolate bar with $n$ pieces into individual pieces requires $n - 1$ breaks''.

• Basis step. $P(1)$ is true. A bar with $1$ piece is already a single, individual piece, so no breaks are needed, and $1 - 1 = 0$.
• Induction step. Suppose that $P(i)$ is true for all $i \in [1, k]$ for some $k \ge 1$. We need to prove that $P(k + 1)$ is true.
Bar with $k + 1$ pieces is split into two parts using 1 break.
First part has $j \in [1, k]$ pieces and second part has $k+1-j$ pieces. \begin{align*} & \text{LHS of } P(k+1) \\ &= \text{#Breaks for chocolate bar with } k + 1 \text{ pieces} \\ &= 1 + \text{#Breaks for the first part } + \text{#Breaks for the second part} \\ &= 1 + (j - 1) + (k - j) && (\because P(j), P(k+1-j) \text{ are true}) \\ &= k\\ &= \text{RHS of } P(k+1) \end{align*} Hence, $P(k + 1)$ is true.

Solution

Let $k \ge 1$ be an integer. By the given formula, $c_{k-1} = 2^{k-1} - 1$. Then, \begin{align*} & 2 c_{k-1} + 1 \\ &= 2 (2^{k-1} - 1) + 1 && (\because \text{substitute } c_{k-1} = 2^{k-1}-1) \\ &= 2^{k} - 2 + 1 && (\because \text{simplify}) \\ &= 2^k - 1 \\ &= c_k && (\because \text{by the given formula}) \end{align*} So $c_k = 2c_{k-1}+1$ for every integer $k \ge 1$, and the sequence satisfies the given recurrence relation.

Solution

• First, compute a few terms. \begin{align*} h_0 &= 1 \\ h_1 &= 2^1 - h_0 = 2 - 1 = 1 \\ h_2 &= 2^2 - h_1 = 4 - 1 = 3 \\ h_3 &= 2^3 - h_2 = 8 - 3 = 5 \\ h_4 &= 2^4 - h_3 = 16 - 5 = 11 \\ h_5 &= 2^5 - h_4 = 32 - 11 = 21 \end{align*}
• Solving the recurrence by the method of iteration — substitute for $h_{k-1}$, then $h_{k-2}$, and so on: \begin{align*} h_k &= 2^k - h_{k-1} \\ &= 2^k - (2^{k-1} - h_{k-2}) && (\because h_{k-1} = 2^{k-1}-h_{k-2}) \\ &= 2^k - 2^{k-1} + h_{k-2} \\ &= 2^k - 2^{k-1} + (2^{k-2} - h_{k-3}) && (\because h_{k-2} = 2^{k-2}-h_{k-3}) \\ &= 2^k - 2^{k-1} + 2^{k-2} - h_{k-3} \\ &\ \ \vdots \\ &= \underbrace{2^k - 2^{k-1} + 2^{k-2} - \cdots + (-1)^{k-1}2^1}_{\text{geometric sum}} + (-1)^k h_0 && (\because \text{after } k \text{ substitutions})\\ &= \frac{2^{k+1} - 2(-1)^k}{3} + (-1)^k && (\because \text{sum of a geometric sequence, } h_0 = 1) \\ &= \frac{2^{k+1} + (-1)^k}{3} && (\because \text{simplify}) \end{align*}
• Solving the recurrence by the method of iteration, we get
  $\fbox{$h_k = \dfrac{2^{k+1} + (-1)^k}{3}$}$
  Checking against the terms above: $h_0 = \frac{3}{3}=1$, $h_1=\frac{3}{3}=1$, $h_2=\frac{9}{3}=3$, $h_3=\frac{15}{3}=5$, $h_4=\frac{33}{3}=11$, $h_5=\frac{63}{3}=21$. All match.

Session 8: Midterm

Cover the common mistakes from all topics for the midterm from Common Mistakes file.

Session 9: Sets

Session 10: Functions

Session 11: Functions

Session 12: Relations

Session 13: Final

Cover the common mistakes from all topics for the final from Common Mistakes file.