Discrete Structure

Claim: $1 + 3 + 5 + \dots + (2n - 1) = n^2$ for all $n \ge 1$.

Basis ($n=1$): LHS $= 1 = 1^2$.

Inductive step: assume the statement holds for $n = k$: $1 + 3 + \dots + (2k-1) = k^2$. Then for $n = k+1$:

$1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1 = (k+1)^2$

So it holds for $k+1$. By mathematical induction the sum of the first $n$ odd positive integers is $n^2$. $\blacksquare$

Claim: $1 + 3 + 5 + \dots + (2N-1) = N^2$ for all integers $N \ge 1$.

Basis ($N = 1$): the sum is $1 = 1^2$.

Inductive hypothesis: assume that for some $k \ge 1$, $1 + 3 + \dots + (2k-1) = k^2$.

Inductive step: for $N = k+1$, the sum of the first $k+1$ odd integers is

$\big[1 + 3 + \dots + (2k-1)\big] + (2k+1) = k^2 + 2k + 1 = (k+1)^2.$

Thus the statement holds for $k+1$. By the principle of mathematical induction it holds for all $N \ge 1$. $\blacksquare$

Claim: $P(N):\ 1+3+5+\cdots+(2N-1)=N^2$ for all $N\ge1$.

Basis step: $N=1$: LHS $=1$, RHS $=1^2=1$. True.

Inductive step: Assume $P(k)$: $1+3+\cdots+(2k-1)=k^2$. Then

$1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2,$

which is $P(k+1)$.

By the principle of mathematical induction, the sum of the first $N$ odd integers is $N^2$ for every $N\ge1$. $\blacksquare$

Claim: $P(n)$: $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all positive integers $n$.

Basis step: for $n = 1$, LHS $= 1$ and RHS $= \frac{1 \cdot 2}{2} = 1$. So $P(1)$ is true.

Inductive step: assume $P(k)$ is true for some $k \ge 1$:

$1 + 2 + \dots + k = \frac{k(k+1)}{2}.$

Add $k + 1$ to both sides:

$1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$

This is $P(k+1)$. Since the basis and inductive steps hold, by mathematical induction $P(n)$ is true for all positive integers $n$. $\blacksquare$

Dijkstra's algorithm finds the shortest path from a source vertex $s$ to all other vertices (or a target $t$) in a weighted graph with non-negative weights.

Dijkstra(G, w, s, t):
    for each vertex v:
        dist[v] = infinity
        prev[v] = undefined
    dist[s] = 0
    S = empty set                  // finalised vertices
    Q = all vertices               // priority queue keyed by dist
    while Q is not empty:
        u = vertex in Q with minimum dist[u]
        remove u from Q; add u to S
        if u == t: break
        for each neighbour v of u in Q:
            if dist[u] + w(u, v) < dist[v]:
                dist[v] = dist[u] + w(u, v)
                prev[v] = u
    // path: follow prev[] from t back to s

Idea: repeatedly pick the unvisited vertex with the smallest tentative distance, fix it as final, and relax its outgoing edges. With a binary heap the running time is $O((V + E)\log V)$; with an array it is $O(V^2)$.

Example: edges $a$-$b$ 4, $a$-$c$ 1, $c$-$b$ 2, $b$-$d$ 5. From $a$: $dist(c) = 1$, $dist(b) = 3$ (via $c$), $dist(d) = 8$. Shortest path $a \to c \to b \to d$ has length 8.

Claim: the square of an even number is even, and so the sum of squares of even numbers is even.

Direct proof. Let $a$ and $b$ be even integers: $a = 2m$ and $b = 2n$ for integers $m, n$. Then

$a^2 = 4m^2 = 2(2m^2), \qquad b^2 = 4n^2 = 2(2n^2)$

so each square is even. Their sum is

$a^2 + b^2 = 2(2m^2) + 2(2n^2) = 2(2m^2 + 2n^2)$

which is 2 times an integer, hence even. The same argument works for any number of even terms, since $\sum (2m_i)^2 = 2\sum 2m_i^2$. $\blacksquare$

Claim: the sum of an odd integer and an even integer is odd.

Direct proof: Let $m$ be odd and $n$ be even. By definition, $m=2a+1$ and $n=2b$ for some integers $a,b$. Then

$m+n=2a+1+2b=2(a+b)+1.$

Since $a+b$ is an integer, $m+n$ has the form $2k+1$ with $k=a+b$, so it is odd. $\blacksquare$

Dijkstra's algorithm: keep a distance label $d(v)$ for every vertex ($d(a)=0$, others $\infty$). Repeatedly pick the unvisited vertex with the smallest label, mark it permanent, and relax its neighbours: $d(v)=\min\{d(v),\,d(u)+w(u,v)\}$. Stop when $z$ is permanent.

Applying it to the graph with edges $ab=4,\ ac=2,\ bc=1,\ bd=5,\ cd=8,\ ce=10,\ de=2,\ dz=6,\ ez=3$:

Tracing predecessors back from $z$: $z\leftarrow e\leftarrow d\leftarrow b\leftarrow c\leftarrow a$.

Shortest path: $a\to c\to b\to d\to e\to z$ with length $2+1+5+2+3=13$.

Direct proof: to prove $p \rightarrow q$, assume $p$ is true and, using definitions, axioms and known theorems, show directly that $q$ is true.

Indirect proof (proof by contraposition): to prove $p \rightarrow q$, prove the equivalent contrapositive $\neg q \rightarrow \neg p$: assume $q$ is false and show $p$ is false.

Proof by contradiction: to prove $p$, assume $\neg p$ and derive a contradiction $r \wedge \neg r$ (or an impossible statement). For $p \rightarrow q$, assume $p \wedge \neg q$ and derive a contradiction. Hence $p$ must be true.

Direct proof: if $n$ is odd, then $n^2$ is odd.

Let $n$ be odd, so $n = 2k + 1$ for some integer $k$. Then

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$

Since $2k^2 + 2k$ is an integer, $n^2$ is of the form $2m + 1$, so $n^2$ is odd. $\blacksquare$

Indirect proof: if $n^2$ is odd, then $n$ is odd.

The contrapositive is: if $n$ is not odd (even), then $n^2$ is not odd (even). Let $n$ be even, so $n = 2k$. Then

$n^2 = 4k^2 = 2(2k^2),$

which is even. Thus the contrapositive is true, so the original statement holds: if $n^2$ is odd then $n$ is odd. $\blacksquare$

Definition: a linear nonhomogeneous recurrence relation of degree $k$ with constant coefficients has the form

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} + F(n),$

where $c_1, \dots, c_k$ are real constants, $c_k \ne 0$, and $F(n) \ne 0$ is a function of $n$ only. The solution is $a_n = a_n^{(h)} + a_n^{(p)}$: the general solution of the associated homogeneous relation plus a particular solution.

Solve $a_n = 4a_{n-1} + n$.

Homogeneous part: $a_n = 4a_{n-1}$ has characteristic equation $r - 4 = 0$, so $a_n^{(h)} = \alpha\, 4^n$.

Particular solution: since $F(n) = n$ is linear, try $a_n^{(p)} = cn + d$. Substituting:

$cn + d = 4(c(n-1) + d) + n = (4c + 1)n + (4d - 4c).$

Comparing coefficients: $c = 4c + 1$, so $c = -\tfrac13$; and $d = 4d - 4c$, so $3d = 4c = -\tfrac43$, giving $d = -\tfrac49$.

$a_n^{(p)} = -\frac{n}{3} - \frac{4}{9}.$

All solutions:

$a_n = \alpha\, 4^n - \frac{n}{3} - \frac{4}{9}.$

With $a_0 = 1$: $1 = \alpha - \tfrac49$, so $\alpha = \tfrac{13}{9}$.

$a_n = \frac{13}{9}\,4^n - \frac{n}{3} - \frac{4}{9}.$

Check: $a_1 = 4(1) + 1 = 5$ and the formula gives $\frac{52}{9} - \frac{3}{9} - \frac{4}{9} = 5$.

Spanning tree: a spanning tree of a connected graph $G$ is a subgraph that is a tree and contains all vertices of $G$. For $n$ vertices it has exactly $n - 1$ edges and no cycle.

Minimum spanning tree (MST): in a connected weighted graph, a spanning tree whose total edge weight is minimum.

Example: for a triangle with vertices $a, b, c$ and edges $ab = 1$, $bc = 2$, $ac = 3$, the spanning trees are $\{ab, bc\}$ (weight 3), $\{ab, ac\}$ (4), $\{bc, ac\}$ (5). The MST is $\{ab, bc\}$ with weight 3.

Kruskal's algorithm:

1. Sort the edges in non-decreasing order of weight.
2. Take the smallest edge; add it to the tree if it does not form a cycle with edges already chosen; otherwise discard it.
3. Repeat until $n - 1$ edges are chosen.

Illustration on a graph with vertices $a, b, c, d, e$ and edges $bc = 1$, $ab = 2$, $ac = 3$, $bd = 4$, $cd = 5$, $ce = 6$, $de = 7$:

MST edges: $bc, ab, bd, ce$ with total weight $1 + 2 + 4 + 6 = 13$.

A tautology is a compound proposition that is true for all possible truth values of its component propositions.

Show $(p \wedge q) \rightarrow (p \vee q)$ is a tautology.

The last column is always true, so it is a tautology.

Algebraic check: $(p \wedge q) \rightarrow (p \vee q) \equiv \neg(p \wedge q) \vee (p \vee q) \equiv (\neg p \vee \neg q) \vee p \vee q \equiv (\neg p \vee p) \vee (\neg q \vee q) \equiv T$.

Cartesian product: for sets $A$ and $B$, the Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$:

$A \times B = \{(a, b) \mid a \in A,\ b \in B\}.$

In general $A_1 \times A_2 \times \dots \times A_n$ is the set of ordered $n$-tuples $(a_1, \dots, a_n)$ with $a_i \in A_i$, and $A^3 = A \times A \times A$.

For $A = \{a, b, c\}$, $|A^3| = 3^3 = 27$ ordered triples:

$A^3 = \{(a,a,a), (a,a,b), (a,a,c), (a,b,a), (a,b,b), (a,b,c), (a,c,a), (a,c,b), (a,c,c),$ $(b,a,a), (b,a,b), (b,a,c), (b,b,a), (b,b,b), (b,b,c), (b,c,a), (b,c,b), (b,c,c),$ $(c,a,a), (c,a,b), (c,a,c), (c,b,a), (c,b,b), (c,b,c), (c,c,a), (c,c,b), (c,c,c)\}$

Representing relations by matrices: let $R$ be a relation from $A = \{a_1, \dots, a_m\}$ to $B = \{b_1, \dots, b_n\}$. The zero-one matrix $M_R = [m_{ij}]$ of size $m \times n$ has

$m_{ij} = \begin{cases} 1 & \text{if } (a_i, b_j) \in R \\ 0 & \text{if } (a_i, b_j) \notin R. \end{cases}$

Rows are indexed by elements of $A$ and columns by elements of $B$.

For $A = \{1,2,3\}$, $B = \{1,2\}$ and $R = \{(a,b) \mid a > b\}$:

$R = \{(2,1), (3,1), (3,2)\}$.

$M_R = \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 1 & 1 \end{bmatrix}$

Row 1 is $(1>1?, 1>2?)=(0,0)$, row 2 is $(2>1, 2>2)=(1,0)$, row 3 is $(3>1, 3>2)=(1,1)$.

Congruence modulo: let $a, b$ be integers and $m$ a positive integer. $a$ is congruent to $b$ modulo $m$, written $a \equiv b \pmod m$, if $m$ divides $a - b$. Equivalently, $a$ and $b$ leave the same remainder when divided by $m$.

(a) $20 - 8 = 12$, and $6 \mid 12$ ($12 = 6 \times 2$). So $20 \equiv 8 \pmod 6$: yes, congruent. (Both leave remainder 2.)

(b) $25 - 17 = 8$, and $5 \nmid 8$. So $25 \not\equiv 17 \pmod 5$: not congruent. (Remainders are 0 and 2.)

Trial division: to test whether a positive integer $n > 1$ is prime, divide it by every prime $p \le \sqrt{n}$. If none divides $n$, then $n$ is prime; if some prime divides it, $n$ is composite. This works because a composite number has a prime factor not exceeding $\sqrt{n}$.

Example: $91$. $\sqrt{91} \approx 9.5$; primes up to 9 are 2, 3, 5, 7. Since $91 = 7 \times 13$, it is composite.

Show 101 is prime: $\sqrt{101} \approx 10.05$, so test primes $2, 3, 5, 7$.

• $101 \div 2$: remainder 1.
• $101 \div 3$: $101 = 3 \times 33 + 2$, remainder 2.
• $101 \div 5$: remainder 1.
• $101 \div 7$: $101 = 7 \times 14 + 3$, remainder 3.

No prime up to $\sqrt{101}$ divides 101, so 101 is prime.

Product rule: if a procedure can be broken into two tasks (or a sequence of $k$ tasks), where there are $n_1$ ways to do the first and $n_2$ ways to do the second after the first is done, then there are $n_1 \times n_2$ ways to do the procedure (in general $n_1 n_2 \cdots n_k$).

Example: a license code with one letter (26 ways) followed by one digit (10 ways) can be formed in $26 \times 10 = 260$ ways.

Strings of four lowercase letters containing $x$:

Count all strings and subtract those with no $x$.

• Total strings of length 4: $26^4 = 456976$.
• Strings with no $x$ (letters from the other 25): $25^4 = 390625$.

$26^4 - 25^4 = 456976 - 390625 = 66351.$

There are $66351$ strings that contain the letter $x$ at least once.

A graph $G = (V, E)$ consists of a non-empty set $V$ of vertices (nodes) and a set $E$ of edges, each edge connecting a pair of vertices. Graphs model networks such as roads, computer networks and social links.

Simple graph: an undirected graph with no loops (an edge from a vertex to itself) and no multiple (parallel) edges. Each edge is an unordered pair $\{u, v\}$ of distinct vertices.

Example: $V = \{a, b, c, d\}$, $E = \{\{a,b\}, \{b,c\}, \{c,d\}, \{a,d\}\}$ is a simple graph (a 4-cycle).

Pseudograph: an undirected graph that may contain both multiple edges and loops. It is the most general type of undirected graph.

Example: $V = \{a, b, c\}$ with two parallel edges between $a$ and $b$, an edge $b$-$c$, and a loop at $c$. A loop adds 2 to the degree of its vertex, so $\deg(c) = 1 + 2 = 3$.

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.

Hamilton path: a path that visits every vertex exactly once (a Hamilton circuit also returns to the start).

Example: in the complete graph $K_4$ every vertex has degree 3 (four odd vertices), so it has no Euler path, but it has a Hamilton circuit.

Four statements that are not propositions (they are not definitely true or false):

1. What is your name? (question)
2. Close the door. (command)
3. $x + 3 = 7$ (truth depends on $x$)
4. How beautiful the Himalayas are! (exclamation)

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

Premises:

1. $\forall x\,(O(x) \to S(x))$
2. $\forall x\,\forall y\,(S(x) \wedge C(y, x) \to N(y))$
3. $O(\text{John})$
4. $C(\text{Sam}, \text{John})$

Proof:

Hence Sam is naughty.

Need for the principle of inclusion and exclusion (PIE): when counting elements in a union of sets that overlap, simply adding the sizes counts common elements more than once. PIE corrects 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|$

Counting words: the first three characters are distinct lowercase letters and the fourth is a digit (a digit can never equal a letter, so no repetition issue there).

$26 \times 25 \times 24 \times 10 = 156000$

There are 156000 such words.

Induction: prove $P(n)$: $3^n - 1$ is a multiple of 2 for $n \ge 1$.

Basis: $n = 1$: $3 - 1 = 2$, which is divisible by 2.

Inductive step: assume $3^k - 1 = 2m$ for some integer $m$. Then

$3^{k+1} - 1 = 3\cdot 3^k - 1 = 3(2m + 1) - 1 = 6m + 2 = 2(3m + 1)$

which is a multiple of 2. By induction, $3^n - 1$ is a multiple of 2 for all $n \ge 1$.

Euler circuit: a connected graph (ignoring isolated vertices) has an Euler circuit if and only if every vertex has even degree.

Euler path (not a circuit): a connected graph has an Euler path if and only if it has exactly two vertices of odd degree; the path starts at one odd vertex and ends at the other. (With zero odd vertices an Euler circuit exists, which is also an Euler path.)

GCD of 12 and 18 by the Extended Euclidean Algorithm:

$18 = 1 \cdot 12 + 6$ $12 = 2 \cdot 6 + 0$

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

Back-substitute:

$6 = 18 - 1\cdot 12 = (-1)\cdot 12 + 1 \cdot 18$

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

Claim: the sum of two even numbers is even.

Direct proof: let $a$ and $b$ be even integers. By definition, $a = 2m$ and $b = 2n$ for some integers $m, n$. Then

$a + b = 2m + 2n = 2(m + n)$

Since $m + n$ is an integer, $a + b$ is 2 times an integer, so it is even. $\blacksquare$

Power set: the power set $P(A)$ of a set $A$ is the set of all subsets of $A$, including the empty set and $A$ itself. If $|A| = n$ then $|P(A)| = 2^n$.

For $A = \{1, 2, 3, 4\}$, $|P(A)| = 2^4 = 16$:

$P(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}, \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\}\}$

One-to-one correspondence (bijection): a function $f: A \to B$ that is both one-to-one (injective: $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$) and onto (surjective: every $b \in B$ equals $f(a)$ for some $a$). Every element of $A$ is paired with exactly one element of $B$ and vice versa, so $|A| = |B|$ for finite sets.

Example: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 1$. If $2x_1 + 1 = 2x_2 + 1$ then $x_1 = x_2$ (one-to-one); for any $y$, $x = (y-1)/2$ gives $f(x) = y$ (onto). So $f$ is a bijection. By contrast $f(x) = x^2$ on $\mathbb{R}$ is neither.

Identity function: $I_A : A \to A$ defined by $I_A(x) = x$ for all $x \in A$. It is a bijection and is its own inverse.

A recursively defined function is defined in terms of its own values at smaller arguments: a basis step gives the value(s) at the starting point(s), and a recursive step gives a rule to compute later values from earlier ones.

Given $f(0) = 3$ and $f(n+1) = 2f(n) + 3$:

$f(1) = 2(3) + 3 = 9$ $f(2) = 2(9) + 3 = 21$ $f(3) = 2(21) + 3 = 45$ $f(4) = 2(45) + 3 = 93$

Arithmetic modulo $m$: on $\mathbb{Z}_m = \{0, 1, \dots, m-1\}$, addition and multiplication are defined by

$a +_m b = (a + b) \bmod m, \qquad a *_m b = (a \cdot b) \bmod m$

i.e. the remainder after division by $m$.

For $m = 11$:

$7 +_{11} 9 = 16 \bmod 11 = 5$ $7 *_{11} 9 = 63 \bmod 11 = 63 - 55 = 8$

A relation $R$ on a set $A$ is an equivalence relation if it is

1. Reflexive: $(a, a) \in R$ for all $a \in A$,
2. Symmetric: $(a, b) \in R \Rightarrow (b, a) \in R$,
3. Transitive: $(a, b) \in R$ and $(b, c) \in R \Rightarrow (a, c) \in R$.

Example: on $\mathbb{Z}$, define $a R b$ iff $a \equiv b \pmod 3$ (i.e. $3 \mid a - b$).

• Reflexive: $a - a = 0$ is divisible by 3.
• Symmetric: if $3 \mid a - b$ then $3 \mid b - a$.
• Transitive: if $3 \mid a - b$ and $3 \mid b - c$ then $3 \mid (a-b)+(b-c) = a - c$.

So $R$ is an equivalence relation; it partitions $\mathbb{Z}$ into three equivalence classes (remainders 0, 1, 2).

Generalized pigeonhole principle: if $N$ objects are placed into $k$ boxes, then at least one box contains at least $\lceil N/k \rceil$ objects.

Application: 24 students, with $k$ possible grades. At least two students share a grade when $\lceil 24/k \rceil \ge 2$, i.e. when $k < 24$. If there were 24 or more grades, all students could have different grades. Hence the number of distinct grades must be at most $k = 23$; with 23 grades (the maximum), $\lceil 24/23 \rceil = 2$, so at least two students are guaranteed the same grade.

Set operations with Venn diagrams: the universal set $U$ is drawn as a rectangle and each set as a circle inside it. Shading shows the result:

• Union $A \cup B$: shade both circles entirely.
• Intersection $A \cap B$: shade only the overlapping region.
• Difference $A - B$: shade the part of $A$ outside $B$.
• Complement $\bar{A}$: shade everything in $U$ outside $A$.

Example: $U = \{1,\dots,8\}$, $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$. Then $A \cup B = \{1,\dots,6\}$, $A \cap B = \{3,4\}$, $A - B = \{1,2\}$, $\bar A = \{5,6,7,8\}$. In the diagram, 3 and 4 lie in the overlap, 1 and 2 in $A$ only, 5 and 6 in $B$ only, and 7 and 8 outside both circles.

Quantifier forms: let $G(x)$: $x$ is good, $H(x)$: $x$ is a hero, $P(x)$: $x$ is a person.

(a) Not all good people are heroes: $\neg\forall x\,\big(G(x) \to H(x)\big) \equiv \exists x\,\big(G(x) \wedge \neg H(x)\big)$

(b) Every person in our country is loyal (with $L(x)$: $x$ is loyal, domain = people of our country): $\forall x\, L(x)$

(c) Some people hate good people (with $Hate(x, y)$: $x$ hates $y$): $\exists x\,\exists y\,\big(P(x) \wedge G(y) \wedge P(y) \wedge Hate(x, y)\big)$

Floor function $\lfloor x \rfloor$: the greatest integer less than or equal to $x$. Examples: $\lfloor 3.7 \rfloor = 3$, $\lfloor -2.3 \rfloor = -3$, $\lfloor 5 \rfloor = 5$.

Ceiling function $\lceil x \rceil$: the least integer greater than or equal to $x$. Examples: $\lceil 3.2 \rceil = 4$, $\lceil -2.7 \rceil = -2$, $\lceil 5 \rceil = 5$.

Induction and recursive algorithms: a recursive algorithm solves a problem by calling itself on smaller inputs, with a base case. Its correctness is proved by induction on the input size: show the algorithm is correct for the base case (basis), then assume it is correct for all smaller inputs (inductive hypothesis) and show that the recursive step combines their results into a correct answer for the current input.

Example: recursive power function.

power(a, n):         // a != 0, n >= 0
    if n == 0: return 1
    return a * power(a, n - 1)

Claim: $power(a, n) = a^n$ for all $n \ge 0$.

Basis: $n = 0$ returns $1 = a^0$.

Inductive step: assume $power(a, k) = a^k$. Then $power(a, k+1) = a \cdot power(a, k) = a \cdot a^k = a^{k+1}$.

Hence the algorithm is correct for all $n \ge 0$ (and terminates since $n$ decreases each call).