Discrete Structures

The recurrence is $a_n=5a_{n-1}-6a_{n-2}$, a linear homogeneous recurrence of order 2.

Characteristic equation

$r^2-5r+6=0 \Rightarrow (r-2)(r-3)=0 \Rightarrow r=2,\ 3$

The roots are distinct, so the general solution is $a_n=A\cdot 2^n+B\cdot 3^n.$

Using the initial conditions

$a_0=A+B=1,\qquad a_1=2A+3B=2$

From the first, $A=1-B$. Substituting: $2-2B+3B=2\Rightarrow B=0$, so $A=1$.

$\boxed{a_n=2^n}$

Check: $a_2=5(2)-6(1)=4=2^2$ and $a_3=5(4)-6(2)=8=2^3$.

We solve $x\equiv 1 \pmod 5$ and $x\equiv 2 \pmod 7$. The moduli 5 and 7 are coprime, so the Chinese remainder theorem applies.

Step 1. $M=5\times 7=35$, $M_1=M/5=7$, $M_2=M/7=5$.

Step 2. Inverses

• $y_1$ with $7y_1\equiv 1 \pmod 5$: $7\equiv 2$, and $2\cdot 3=6\equiv 1$, so $y_1=3$.
• $y_2$ with $5y_2\equiv 1 \pmod 7$: $5\cdot 3=15\equiv 1$, so $y_2=3$.

Step 3. Combine

$x = a_1M_1y_1+a_2M_2y_2 = 1(7)(3)+2(5)(3)=21+30=51$

$x\equiv 51 \pmod{35}\Rightarrow x\equiv 16 \pmod{35}$

Check: $16=5\cdot 3+1$ and $16=7\cdot 2+2$.

Hence $x=16$ (the general solution is $x=16+35k$, $k\in\mathbb{Z}$).

We solve $x\equiv1\ (\bmod 3),\quad x\equiv1\ (\bmod 4),\quad x\equiv1\ (\bmod 5),\quad x\equiv0\ (\bmod 7).$

The moduli $3,4,5,7$ are pairwise coprime, so the Chinese remainder theorem applies.

$M=3\cdot4\cdot5\cdot7=420$.

$x=\sum a_iM_iy_i=1(140)(2)+1(105)(1)+1(84)(4)+0=280+105+336=721$

$x\equiv721 \pmod{420}\Rightarrow x\equiv301 \pmod{420}$

Check: $301=3\cdot100+1$, $301=4\cdot75+1$, $301=5\cdot60+1$, $301=7\cdot43$.

So $x=301$ (general solution $x=301+420k$).

The recurrence $a_n = 5a_{n-1} - 6a_{n-2}$ is linear, homogeneous, with constant coefficients.

Characteristic equation:

$r^2 - 5r + 6 = 0 \implies (r-2)(r-3)=0 \implies r = 2,\ 3$

The roots are distinct, so the general solution is

$a_n = \alpha\,2^n + \beta\,3^n$

Using the initial conditions:

• $a_0 = 1$: $\alpha + \beta = 1$
• $a_1 = 4$: $2\alpha + 3\beta = 4$

Subtracting twice the first equation from the second gives $\beta = 2$, so $\alpha = -1$.

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

Check: $a_1 = 6 - 2 = 4$. From the recurrence $a_2 = 5(4) - 6(1) = 14$, and the formula gives $2(9) - 4 = 14$. ✓

Solve $x\equiv 0 \pmod 2$, $x\equiv 2 \pmod 3$, $x\equiv 3 \pmod 5$.

The moduli 2, 3, 5 are pairwise coprime, so the Chinese Remainder Theorem applies.

$M = 2\cdot3\cdot5 = 30$

For each modulus $m_i$ let $M_i = M/m_i$ and find $y_i$ with $M_i y_i \equiv 1 \pmod{m_i}$.

$x \equiv \sum a_i M_i y_i = 0(15)(1) + 2(10)(1) + 3(6)(1) = 38 \equiv 8 \pmod{30}$

$\boxed{x \equiv 8 \pmod{30}}$

Check: $8 \bmod 2 = 0$, $8 \bmod 3 = 2$, $8 \bmod 5 = 3$. ✓

Recurrence: $a_n=a_{n-1}+2a_{n-2}$, $a_0=2$, $a_1=7$.

This is a linear homogeneous recurrence with constant coefficients. The characteristic equation is

$r^2-r-2=0 \;\Rightarrow\; (r-2)(r+1)=0 \;\Rightarrow\; r=2,\ -1.$

The general solution is

$a_n=\alpha\,2^n+\beta\,(-1)^n.$

Use the initial conditions:

$a_0=\alpha+\beta=2,\qquad a_1=2\alpha-\beta=7.$

Adding: $3\alpha=9$, so $\alpha=3$ and $\beta=-1$.

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

Check: $a_2=a_1+2a_0=7+4=11$, and the formula gives $3\cdot4-1=11$. ✓

Pigeonhole principle

If $k+1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects.

Generalised form: if $N$ objects are placed into $k$ boxes, some box contains at least $\lceil N/k\rceil$ objects. Example: among any 13 people, at least two were born in the same month (13 objects, 12 boxes).

Solving the recurrence

$a_n=3a_{n-1}-3a_{n-2}+a_{n-3},\quad a_0=1,\ a_1=3,\ a_2=7.$

Characteristic equation: $r^3-3r^2+3r-1=0\Rightarrow (r-1)^3=0,$ so $r=1$ is a root of multiplicity 3. The general solution is $a_n=(A+Bn+Cn^2)\,1^n=A+Bn+Cn^2.$

Initial conditions:

• $n=0$: $A=1$.
• $n=1$: $A+B+C=3\Rightarrow B+C=2$.
• $n=2$: $A+2B+4C=7\Rightarrow 2B+4C=6\Rightarrow B+2C=3$.

Subtracting gives $C=1$, then $B=1$.

$\boxed{a_n=n^2+n+1}$

Check: $a_3=3(7)-3(3)+1=13$ and $3^2+3+1=13$.

Find $\gcd(24,32)$ and express it as a linear combination of 24 and 32.

Euclidean algorithm (forward):

$32 = 1\cdot 24 + 8$ $24 = 3\cdot 8 + 0$

The last non-zero remainder is 8, so $\gcd(24,32)=8$.

Back substitution: from the first line,

$8 = 32 - 1\cdot 24 = 1\cdot 32 + (-1)\cdot 24.$

So $s=-1$ (coefficient of 24) and $t=1$ (coefficient of 32) satisfy $24s + 32t = 8$.

$\boxed{\gcd(24,32)=8 = (-1)(24) + (1)(32)}$

Check: $-24 + 32 = 8$. ✓

(a) Pigeonhole principle. If $k+1$ or more objects (pigeons) are placed into $k$ boxes (pigeonholes), then at least one box contains at least two objects.

Generalised form: if $N$ objects are placed into $k$ boxes, then some box contains at least $\lceil N/k\rceil$ objects.

Example: among any 13 people, at least two were born in the same month, because $13>12$.

(b) Recurrence $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0=1$, $a_1=3$.

Characteristic equation:

$r^2-5r+6=0 \Rightarrow (r-2)(r-3)=0 \Rightarrow r=2,3.$

General solution: $a_n = \alpha\,2^n + \beta\,3^n$.

• $a_0=1$: $\alpha+\beta=1$.
• $a_1=3$: $2\alpha+3\beta=3$.

From the first, $\alpha = 1-\beta$, so $2 - 2\beta + 3\beta = 3 \Rightarrow \beta=1$ and $\alpha=0$.

$\boxed{a_n = 3^n}$

Check: $a_2 = 5(3)-6(1)=9 = 3^2$. ✓

GCD of 12 and 16 by the Extended Euclidean Algorithm.

Euclidean steps:

$16 = 1\cdot 12 + 4$ $12 = 3\cdot 4 + 0$

The last non-zero remainder is 4, so $\gcd(12,16)=4$.

Back-substitution: from the first line,

$4 = 16 - 1\cdot 12 = (-1)\cdot 12 + 1\cdot 16.$

So $\gcd(12,16)=4 = 12s+16t$ with $s=-1,\ t=1$.

Check: $-12+16=4$. ✓

Computer representation of the set

The universal set is $U=\{1,2,\dots,10\}$. A subset is stored as a bit string of length 10, where bit $i$ is 1 if element $i$ belongs to the set and 0 otherwise.

The multiples of 3 not exceeding 6 are $3$ and $6$, so $S=\{3,6\}$.

$S = 0010010000$

With this representation union is bitwise OR, intersection is bitwise AND and complement is bitwise NOT.

Types of functions (let $f:A\to B$)

Injective (one-to-one): different elements of $A$ have different images, i.e. $f(a_1)=f(a_2)\Rightarrow a_1=a_2$. Example: $f:\mathbb{Z}\to\mathbb{Z}$, $f(x)=2x+1$. If $2x_1+1=2x_2+1$ then $x_1=x_2$. It is not onto, because even numbers are never obtained.

Surjective (onto): every element of $B$ is the image of at least one element of $A$, i.e. range = codomain. Example: $f:\mathbb{R}\to\mathbb{R}_{\ge 0}$, $f(x)=x^2$ is onto, since every $y\ge 0$ equals $(\sqrt y)^2$. It is not injective because $f(2)=f(-2)=4$.

Bijective: the function is both injective and surjective, so each element of $B$ has exactly one pre-image. Example: $f:\mathbb{R}\to\mathbb{R}$, $f(x)=3x-5$. For any $y$, $x=(y+5)/3$ is the unique pre-image. A bijection has an inverse function, here $f^{-1}(y)=(y+5)/3$.

(a) Values of mod

The remainder $r$ in $a=dq+r$ always satisfies $0\le r<d$.

• $3 \bmod 4 = 3$, since $3=4\cdot 0+3$.
• $7 \bmod 5 = 2$, since $7=5\cdot 1+2$.
• $-5 \bmod 3 = 1$, since $-5=3\cdot(-2)+1$.
• $11 \bmod 5 = 1$, since $11=5\cdot 2+1$.
• $-8 \bmod 6 = 4$, since $-8=6\cdot(-2)+4$.

(b) Recursive algorithm for $b^n$

procedure power(b, n)      // b real, n non-negative integer
    if n = 0 then
        return 1
    else
        return b * power(b, n - 1)

Proof of correctness by induction on $n$

Claim: $\text{power}(b,n)=b^n$ for all $n\ge 0$.

Basis ($n=0$): the algorithm returns $1=b^0$.

Inductive step: assume $\text{power}(b,k)=b^k$ for some $k\ge 0$ (inductive hypothesis). For $n=k+1>0$ the algorithm returns $b\cdot \text{power}(b,k)=b\cdot b^k=b^{k+1}.$

So the claim holds for $k+1$. By mathematical induction the algorithm correctly computes $b^n$ for every $n\ge 0$. It makes $n$ multiplications, so it runs in $O(n)$ time.

Claim: $P(n): 5^n-1$ is divisible by 4 for every integer $n\ge 1$.

Basis step ($n=1$): $5^1-1=4$, which is divisible by 4. So $P(1)$ is true.

Inductive step: assume $P(k)$ is true for some $k\ge 1$, i.e. $5^k-1=4m$ for some integer $m$. Then $5^k=4m+1$, and $5^{k+1}-1=5\cdot 5^k-1=5(4m+1)-1=20m+4=4(5m+1).$

Since $5m+1$ is an integer, $5^{k+1}-1$ is divisible by 4, so $P(k+1)$ is true.

By the principle of mathematical induction, $5^n-1$ is divisible by 4 for all $n\ge 1$. $\blacksquare$

Let $A$ = "Aldo is Italian" and $B$ = "Bob is English".

1. Aldo isn't Italian: $\neg A$
2. Aldo is Italian while Bob is English ("while" means "and"): $A\wedge B$
3. If Aldo is Italian then Bob is not English: $A\rightarrow \neg B$
4. Aldo is Italian or, if Aldo isn't Italian, then Bob is English: $A\vee(\neg A\rightarrow B)$ This simplifies to $A\vee(A\vee B)\equiv A\vee B$.
5. Either Aldo is Italian and Bob is English, or neither is: $(A\wedge B)\vee(\neg A\wedge \neg B)$ This is equivalent to the biconditional $A\leftrightarrow B$.

Euler path: a path in a graph that uses every edge exactly once. If it starts and ends at the same vertex it is an Euler circuit. A connected graph has an Euler circuit iff every vertex has even degree, and an Euler path (not circuit) iff exactly two vertices have odd degree. Example: the "envelope" graph, or a triangle $a$-$b$-$c$-$a$, which has the Euler circuit $a,b,c,a$. For the graph with edges $ab, bc, cd, bd$, the degrees are $a=1, b=3, c=2, d=2$, so exactly two odd vertices ($a$, $b$), and $a\,b\,c\,d\,b$ is an Euler path.

Hamilton path: a path that visits every vertex exactly once. If it returns to the start it is a Hamilton circuit. Example: in the square (cycle $C_4$) with vertices $1,2,3,4$ and edges $12,23,34,41$, the path $1\to2\to3\to4$ is a Hamilton path and $1\to2\to3\to4\to1$ is a Hamilton circuit.

Hasse diagram of divisibility on $\{1,2,5,8,16,32\}$

Divisibility relations: $1$ divides everything; $2\mid 8,16,32$; $8\mid 16,32$; $16\mid 32$; $5$ divides only itself and nothing else in the set. The covering pairs are $1\!-\!2,\ 1\!-\!5,\ 2\!-\!8,\ 8\!-\!16,\ 16\!-\!32$.

        32
         |
        16
         |
         8
         |
         2      5
          \    /
            1

• Maximal elements: $32$ and $5$ (nothing above them).
• Minimal element: $1$.
• Greatest element: none, because $5$ and $32$ are not comparable, so no single element is above all.
• Least element: $1$, since $1$ divides every element.

Primality testing means deciding whether a given integer $n>1$ is prime (has no divisors other than 1 and $n$) or composite. For large $n$ (as in RSA key generation) trial division is too slow, so fast tests such as Fermat's test are used.

Fermat's Little Theorem: if $p$ is prime and $a$ is an integer not divisible by $p$, then $a^{p-1}\equiv 1 \pmod p.$

Test: to test $n$, pick a base $a$ with $1<a<n$ and $\gcd(a,n)=1$, and compute $a^{n-1}\bmod n$ by fast modular exponentiation.

• If the result is not 1, then $n$ is definitely composite.
• If the result is 1, then $n$ is probably prime. Repeat with other bases to raise confidence.

Example 1 ($n=15$, $a=2$): $2^4=16\equiv 1 \pmod{15}$, so $2^{14}=(2^4)^3\cdot 2^2\equiv 4 \pmod{15}$. This is not 1, so 15 is composite.

Example 2 ($n=11$, $a=3$): $3^5=243=22\cdot 11+1\equiv 1$, so $3^{10}\equiv 1 \pmod{11}$. It passes, and 11 is indeed prime.

Limitation: the converse of the theorem is false. Composite numbers that pass the test for a base $a$ are pseudoprimes (e.g. $341$ for $a=2$), and Carmichael numbers such as $561$ pass for every base coprime to them. So a pass shows only "probably prime".

Two applications of conditional probability

1. Medical diagnosis: the probability that a patient has a disease given a positive test result, $P(\text{disease}\mid\text{positive})$, is found using Bayes' theorem, which is built on conditional probability.
2. Spam filtering: the probability that an email is spam given that it contains certain words, $P(\text{spam}\mid\text{word})$ (naive Bayes classifier).

(Others: quality control in manufacturing, weather forecasting, risk assessment in insurance.)

Number of invitation sets

Choosing which 6 of the 9 families to invite is a combination (order does not matter):

$\binom{9}{6}=\frac{9!}{6!\,3!}=\frac{9\cdot 8\cdot 7}{3\cdot 2\cdot 1}=84.$

So 84 different sets of invitations can be written.

Spanning tree: for a connected graph $G$, a spanning tree is a subgraph that contains all the vertices of $G$, is connected, and has no cycles (so it is a tree). A graph with $n$ vertices has a spanning tree with exactly $n-1$ edges.

Minimum spanning tree (MST): for a connected weighted graph, the spanning tree whose total edge weight is the smallest among all spanning trees. It is found by Kruskal's or Prim's algorithm.

Isomorphic graphs: $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there is a bijection $f:V_1\to V_2$ such that $u,v$ are adjacent in $G_1$ iff $f(u),f(v)$ are adjacent in $G_2$.

Necessary conditions (if any fails, the graphs are not isomorphic):

1. The same number of vertices.
2. The same number of edges.
3. The same degree sequence.
4. The same number of cycles of each length and the same connectivity.

These conditions are necessary but not sufficient, so finally an explicit adjacency-preserving bijection must be exhibited.

Example: $G_1$ has edges $ab, bc, cd, da$ and $G_2$ has edges $13, 32, 24, 41$. Both have 4 vertices, 4 edges and all degrees 2. The map $a\to1,\ b\to3,\ c\to2,\ d\to4$ sends $ab\to13,\ bc\to32,\ cd\to24,\ da\to41$, so every edge maps to an edge. Hence $G_1\cong G_2$ (both are the cycle $C_4$).

Claim: for integers $x,y$, the product $xy$ is odd if and only if both $x$ and $y$ are odd.

($\Rightarrow$) If $xy$ is odd then $x$ and $y$ are both odd. We prove the contrapositive: if $x$ or $y$ is even, then $xy$ is even. Suppose $x$ is even, $x=2k$. Then $xy=2(ky)$, which is even. The case $y$ even is the same by symmetry. So if $xy$ is odd, neither can be even, so both are odd.

($\Leftarrow$) If $x$ and $y$ are both odd then $xy$ is odd. Let $x=2a+1$ and $y=2b+1$. Then $xy=(2a+1)(2b+1)=4ab+2a+2b+1=2(2ab+a+b)+1,$ which has the form $2m+1$, so $xy$ is odd.

Both directions hold, so $xy$ is odd iff both $x$ and $y$ are odd. $\blacksquare$

Claim: $P(n): n^2+n$ is even for every integer $n\ge1$.

Basis ($n=1$): $1^2+1=2$, which is even.

Inductive step: assume $k^2+k$ is even for some $k\ge1$, say $k^2+k=2m$. Then $(k+1)^2+(k+1)=k^2+2k+1+k+1=(k^2+k)+2(k+1)=2m+2(k+1)=2(m+k+1),$ which is even.

By mathematical induction, $n^2+n$ is even for all $n\ge1$. $\blacksquare$

Predicates: $OS(x)$: $x$ is over smart; $S(x)$: $x$ is stupid; $C(x,y)$: $x$ is a child of $y$; $N(x)$: $x$ is naughty.

Statements in FOPL

1. All over smart people are stupid: $\forall x\,(OS(x)\rightarrow S(x))$
2. Children of stupid people are naughty: $\forall x\,\forall y\,\big((C(x,y)\wedge S(y))\rightarrow N(x)\big)$
3. John is a child of Jane: $C(John, Jane)$
4. Jane is over smart: $OS(Jane)$

Proof that $N(John)$

Hence John is naughty. $\blacksquare$

A poset $(S,R)$ needs $R$ to be reflexive, antisymmetric and transitive on $S$.

$(\mathbb{Z},=)$: reflexive ($a=a$), antisymmetric ($a=b$ and $b=a$ imply $a=b$) and transitive. It is a poset.

$(\mathbb{Z},\neq)$: not reflexive, since $a\neq a$ is false. It is also not antisymmetric: $1\neq2$ and $2\neq1$ both hold, yet $1\ne2$. It is not a poset.

$(\mathbb{Z},\subseteq)$: the relation $\subseteq$ is defined between sets, and integers are not sets, so $\subseteq$ is not a relation on $\mathbb{Z}$ and the structure is not a poset. (If the intended structure were the power set $(P(S),\subseteq)$, it would be a poset, since $\subseteq$ is reflexive, antisymmetric and transitive.)

Reflexive closure: the reflexive closure of a relation $R$ on a set $A$ is the smallest reflexive relation containing $R$: $R\cup\Delta,\quad \Delta=\{(a,a)\mid a\in A\}.$ Example: $A=\{1,2,3\}$, $R=\{(1,2),(2,3)\}$. The reflexive closure is $\{(1,2),(2,3),(1,1),(2,2),(3,3)\}$.

Symmetric closure: the smallest symmetric relation containing $R$: $R\cup R^{-1},\quad R^{-1}=\{(b,a)\mid (a,b)\in R\}.$ For the same $R$, the symmetric closure is $\{(1,2),(2,1),(2,3),(3,2)\}$.

Remainder theorem: when a polynomial $f(x)$ is divided by $x-c$, the remainder is $f(c)$.

Here $f(x)=4x^2-x+3$ and the divisor is $x+2=x-(-2)$, so $c=-2$: $f(-2)=4(4)-(-2)+3=16+2+3=21.$

The remainder is $21$.

Euler path: a path that uses every edge of the graph exactly once. If it begins and ends at the same vertex it is an Euler circuit. A connected graph has an Euler circuit iff all vertices have even degree, and an Euler path that is not a circuit iff exactly two vertices have odd degree.

Example: the graph with vertices $a,b,c,d$ and edges $ab, bc, cd, bd$ has degrees $a=1,b=3,c=2,d=2$. Exactly two vertices are odd, so it has an Euler path: $a\to b\to c\to d\to b$ (all four edges used once). A triangle $a,b,c$ has the Euler circuit $a\to b\to c\to a$.

Hamilton path: a path that visits every vertex exactly once (edges may be left unused). If it returns to its start it is a Hamilton circuit.

Example: in the cycle $C_5$ with vertices $1,2,3,4,5$ and edges $12,23,34,45,51$, the path $1\to2\to3\to4\to5$ is a Hamilton path, and adding the edge $5\to1$ gives a Hamilton circuit. In the graph above, $a\to b\to c\to d$ is a Hamilton path.

We form 3-digit numbers from the digits $1,2,3,4,5$ (5 digits), using the multiplication principle on the three positions.

(a) Repetition allowed: each of the 3 positions can be filled in 5 ways. $5\times5\times5=125.$

(b) Repetition not allowed: the first position has 5 choices, the second 4, the third 3. $5\times4\times3={}^5P_3=\frac{5!}{2!}=60.$

So there are 125 numbers with repetition and 60 without.

Minimum spanning tree (MST): for a connected, weighted, undirected graph, a spanning tree (connected, acyclic, containing all vertices) whose total edge weight is minimum among all spanning trees.

Kruskal's algorithm (greedy, edge-based)

1. Sort all edges in non-decreasing order of weight.
2. Start with an empty forest $T$ (each vertex is its own component).
3. Take the next smallest edge. If it joins two different components (adding it creates no cycle), add it to $T$; otherwise discard it.
4. Stop when $T$ has $n-1$ edges (for $n$ vertices).

KRUSKAL(G):
    T = empty set
    sort edges of G by weight
    for each edge (u, v) in sorted order:
        if find(u) != find(v):      // different components
            T = T + {(u, v)}
            union(u, v)
    return T

Cycle detection is done efficiently with the union-find structure. Time complexity is $O(E\log E)$, dominated by sorting.

Example: vertices $A,B,C,D,E$; edges $AB=1,\ BC=2,\ AC=3,\ CD=4,\ BD=5,\ DE=6,\ CE=7$.

• $AB(1)$: accept.
• $BC(2)$: accept.
• $AC(3)$: rejected, forms the cycle $A,B,C$.
• $CD(4)$: accept.
• $BD(5)$: rejected, forms a cycle.
• $DE(6)$: accept. Now 4 edges $=n-1$, so stop.

MST edges: $AB, BC, CD, DE$ with total weight $1+2+4+6=13$.

Two applications of graph colouring

1. Scheduling / timetabling: vertices are exams (or classes), an edge joins two that share a student, and colours are time slots. The chromatic number is the minimum number of slots needed.
2. Register allocation in compilers: vertices are variables, an edge joins variables live at the same time, and colours are CPU registers.

(Others: map colouring, frequency assignment for radio/mobile towers, Sudoku.)

Theorem: a tree with $n$ vertices has $n-1$ edges.

Proof by induction on $n$.

Basis: $n=1$. A tree with one vertex has $0=n-1$ edges.

Inductive step: assume every tree with $k$ vertices has $k-1$ edges, and let $T$ be a tree with $k+1\ge2$ vertices. A tree with at least 2 vertices has a leaf (take a longest path; its end vertex has degree 1, otherwise the path could be extended or a cycle would exist). Remove a leaf $v$ and its one edge. The result $T'$ is still connected and acyclic, so it is a tree with $k$ vertices, and by the hypothesis it has $k-1$ edges. Adding $v$ and its edge back gives $(k-1)+1=k=(k+1)-1$ edges for $T$.

By induction, every tree with $n$ vertices has $n-1$ edges. $\blacksquare$

Floor and ceiling functions

• The floor $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$. Example: $\lfloor 3.7\rfloor=3$, $\lfloor -2.3\rfloor=-3$.
• The ceiling $\lceil x\rceil$ is the least integer greater than or equal to $x$. Example: $\lceil 3.2\rceil=4$, $\lceil -2.3\rceil=-2$.

Why we need the inclusion-exclusion principle

When counting the elements in a union of sets that overlap, simply adding the sizes counts the common elements more than once. Inclusion-exclusion corrects for this: $|A\cup B|=|A|+|B|-|A\cap B|$ $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Example: how many integers from 1 to 100 are divisible by 2 or 5?

• $|A|$ (divisible by 2) $=\lfloor100/2\rfloor=50$
• $|B|$ (divisible by 5) $=\lfloor100/5\rfloor=20$
• $|A\cap B|$ (divisible by 10) $=\lfloor100/10\rfloor=10$

$|A\cup B|=50+20-10=60.$

Adding without the correction would give 70, wrongly counting the 10 multiples of 10 twice.

(a) If $x^2+y^2$ is even then $x+y$ is even

Proof by contrapositive. Suppose $x+y$ is odd. Then one of $x,y$ is even and the other is odd; say $x=2a$ and $y=2b+1$. Then $x^2+y^2=4a^2+4b^2+4b+1=2(2a^2+2b^2+2b)+1,$ which is odd. So if $x+y$ is odd then $x^2+y^2$ is odd. By the contrapositive, if $x^2+y^2$ is even then $x+y$ is even. $\blacksquare$

(b) $1^3+2^3+\dots+n^3=\dfrac{n^2(n+1)^2}{4}$ by induction

Basis ($n=1$): LHS $=1$, RHS $=\dfrac{1\cdot4}{4}=1$. True.

Inductive step: assume it holds for $n=k$: $1^3+\dots+k^3=\frac{k^2(k+1)^2}{4}.$ Then for $n=k+1$, $\sum_{i=1}^{k+1}i^3=\frac{k^2(k+1)^2}{4}+(k+1)^3=\frac{(k+1)^2\left[k^2+4(k+1)\right]}{4}=\frac{(k+1)^2(k+2)^2}{4},$ since $k^2+4k+4=(k+2)^2$. This is the formula for $n=k+1$.

By mathematical induction the formula holds for all $n\ge1$. $\blacksquare$