Division and Remainder Algorithm + Quantifier Expansion

Part 1: Division and Remainder Algorithm (The Division Algorithm)

Statement

Division Algorithm: Let a be an integer and d a positive integer. Then there exist unique integers q and r with 0 ≤ r < d such that:

a = d·q + r

Where:

• d is called the divisor
• a is called the dividend
• q is called the quotient → written as q = a div d
• r is called the remainder → written as r = a mod d

Procedure (div-mod algorithm from notes)

procedure div-mod(a ∈ Z, d ∈ Z⁺)
  q := 0
  r := |a|
  while r ≥ d begin
    r := r - d
    q := q + 1
  end
  if a < 0 and r > 0 then
    q := -(q + 1)
    r := d - r
  return q, r

Working principle: When a is positive, we subtract d from a repeatedly until what remains is less than d. The number of subtractions performed is the quotient q, and what remains is the remainder r.

Example

What is the quotient and remainder when 101 is divided by 11?

101 = 11 × 9 + 2

So: q = 101 div 11 = 9 and r = 101 mod 11 = 2

Part 2: Expanding Quantified Propositions

Given: Domain of P(x) = {0, 1, 2, 3, 4}

The key rules used are:

a. ∃x P(x)

"There exists at least one x in the domain such that P(x) is true."

$$\exists x, P(x) \equiv P(0) \lor P(1) \lor P(2) \lor P(3) \lor P(4)$$

b. ∀x P(x)

"P(x) is true for every x in the domain."

$$\forall x, P(x) \equiv P(0) \land P(1) \land P(2) \land P(3) \land P(4)$$

c. ∃x ¬P(x)

"There exists at least one x for which P(x) is false."

$$\exists x, \neg P(x) \equiv \neg P(0) \lor \neg P(1) \lor \neg P(2) \lor \neg P(3) \lor \neg P(4)$$

d. ∀x ¬P(x)

"P(x) is false for every x in the domain."

$$\forall x, \neg P(x) \equiv \neg P(0) \land \neg P(1) \land \neg P(2) \land \neg P(3) \land \neg P(4)$$

e. ¬∃x P(x)

"There is no x for which P(x) is true."

By De Morgan's Law for quantifiers: ¬∃x P(x) ≡ ∀x ¬P(x)

$$\neg \exists x, P(x) \equiv \neg P(0) \land \neg P(1) \land \neg P(2) \land \neg P(3) \land \neg P(4)$$

Note: This is logically equivalent to part (d).

f. ¬∀x P(x)

"It is not the case that P(x) is true for all x."

By De Morgan's Law for quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x)

$$\neg \forall x, P(x) \equiv \neg P(0) \lor \neg P(1) \lor \neg P(2) \lor \neg P(3) \lor \neg P(4)$$

Note: This is logically equivalent to part (c).

Summary Table

Conclusion

Over a finite domain a quantifier is only a compact way of writing a long connective: the existential quantifier unfolds into a disjunction and the universal quantifier unfolds into a conjunction, one term for each element of the domain. The two De Morgan laws for quantifiers, $\neg \exists x, P(x) \equiv \forall x, \neg P(x)$ and $\neg \forall x, P(x) \equiv \exists x, \neg P(x)$, are visible directly in the table above, since (e) matches (d) and (f) matches (c). The division algorithm plays the same role for integers: it guarantees that for any integer $a$ and any positive divisor $d$ the pair $(q, r)$ with $a = dq + r$ and $0 \le r < d$ exists and is unique, which is what makes div and mod well defined operations.

Solution of Recurrence Relation

Step 1 - Given Data

$$a_n = 5a_{n-1} - 6a_{n-2}, \quad a_0 = 1,\ a_1 = 4$$

Step 2 - Solve

Characteristic equation. Assume $a_n = r^n$:

$$r^2 = 5r - 6 \implies r^2 - 5r + 6 = 0$$

Roots:

$$(r-2)(r-3) = 0 \implies r_1 = 2,\ r_2 = 3$$

Distinct roots, so the general solution is:

$$a_n = \alpha_1 \cdot 2^n + \alpha_2 \cdot 3^n$$

Apply initial conditions:

$n=0$: $\alpha_1 + \alpha_2 = 1 \quad (i)$

$n=1$: $2\alpha_1 + 3\alpha_2 = 4 \quad (ii)$

From $(i)$: $\alpha_1 = 1 - \alpha_2$. Substitute into $(ii)$:

$$2(1 - \alpha_2) + 3\alpha_2 = 4 \implies 2 + \alpha_2 = 4 \implies \alpha_2 = 2$$

$$\alpha_1 = 1 - 2 = -1$$

Final solution:

$$\boxed{a_n = 2\cdot 3^n - 2^n}$$

Verification:

Pigeonhole Principle and Pascal's Triangle

Given Data

• Number of students = 30
• Number of letters in the English alphabet = 26

Part 1: At Least Two Students Have Names Beginning with the Same Letter

Principle Used: Pigeonhole Principle

Statement: If $n$ objects are placed into $k$ boxes and $n > k$, then at least one box contains two or more objects.

More generally, if $n$ objects are placed into $k$ boxes, then at least one box contains at least $\left\lceil \dfrac{n}{k} \right\rceil$ objects.

Proof

Set up the correspondence:

• Pigeonholes (boxes): the 26 letters of the alphabet that a name can begin with. So $k = 26$.
• Pigeons (objects): the 30 students, each classified by the first letter of their name. So $n = 30$.

Since

$$n = 30 > 26 = k,$$

csc165-pascal-triangle

by the Pigeonhole Principle at least one letter (box) must be assigned to more than one student.

Using the generalized form, the most crowded letter contains at least

$$\left\lceil \frac{30}{26} \right\rceil = \lceil 1.153\ldots \rceil = 2 \text{ students.}$$

Conclusion: At least two students have names beginning with the same letter. (Proved)

Worst case reasoning: Even if the first 26 students all get distinct starting letters, the remaining $30 - 26 = 4$ students must reuse letters already taken, forcing a repetition.

Part 2: Pascal's Triangle

Definition

Pascal's Triangle is a triangular array of the binomial coefficients $\binom{n}{r}$, where each interior entry equals the sum of the two entries directly above it.

Construction Rule

$$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$

with boundary conditions

$$\binom{n}{0} = 1, \qquad \binom{n}{n} = 1 \quad \text{for all } n \ge 0.$$

The Triangle (First 6 rows)

Row 0:            1
Row 1:          1   1
Row 2:        1   2   1
Row 3:      1   3   3   1
Row 4:    1   4   6   4   1
Row 5:  1   5  10  10   5   1

Key Properties

Application: Binomial Theorem

$$(x+y)^n = \sum_{r=0}^{n}\binom{n}{r} x^{n-r} y^{r}$$

Using Row 3:

$$(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$$

Verification of the addition rule

$$\binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3 = 6,$$

which matches the middle entry of Row 4.

Summary: With 30 students and only 26 possible initial letters, the Pigeonhole Principle guarantees at least two students share a starting letter. Pascal's Triangle arranges the binomial coefficients so each value is the sum of the two above it, encoding the coefficients of $(x+y)^n$.