Discrete mathematics, probability and numerical methods
Introduced| English | Meaning |
|---|---|
| recurrence/rɪˈkʌrəns/ | A rule that expresses terms of a sequence using earlier terms. |
| complement/ˈkɒmplɪmənt/ | The event that the given event does not happen. |
| bisection/baɪˈsekʃn/ | A root-finding method that repeatedly halves an interval retaining a root. |
A committee or three different roles?
- Choosing 3 of 10 students for a committee gives $\binom{10}{3}=120$ groups. Choosing a president, secretary and treasurer gives $10\cdot9\cdot8=720$ assignments: the roles distinguish outcomes.
- Before calculating, decide what one outcome records and whether repetition is allowed. This lesson connects counting and probability with recurrences 递推关系, graph reasoning and numerical approximation.
Count outcomes with the stated rules
- From $n$ distinct objects, selecting $r$ without repetition gives $n(n-1)\cdots(n-r+1)$ ordered lists or $\binom nr$ unordered subsets, for $0\le r\le n$. With repetition allowed, an ordered list has $n^r$ possibilities.
- For example, a three-letter code using five available letters has $5^3=125$ outcomes if letters can repeat, but $5\cdot4\cdot3=60$ if they cannot. A probability is favourable outcomes divided by all outcomes only when those outcomes are equally likely.
A three-letter code uses A, B, C, D or E in each position. Repetition is allowed. How many codes are possible?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
There are five choices independently for each of three positions: 5³ = 125. Dividing by 3! would incorrectly merge different ordered codes.
Graphs and lines need their own assumptions
- In a simple undirected graph, edges join distinct vertices, with no repeated edges. The complete graph $K_n$ has one edge per unordered vertex pair, hence $\binom n2$ edges. A tree is connected and has no cycles; with $n\ge1$ vertices, it has $n-1$ edges.
- For $n$ distinct lines in the plane, general position means no parallel pair and no three through one point. The $k$th line then meets earlier lines at $k-1$ distinct points, adding $k$ regions. Starting with one region gives $1+n(n+1)/2$ regions.
Ordered or unordered?
Decide whether positions or roles distinguish outcomes; check repetition separately.
How many edges does the complete graph $K_7$ have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Each edge joins a pair of distinct vertices, and K₇ joins every pair: C(7, 2) = 7 · 6 / 2 = 21.
Into how many regions do 5 lines in general position divide the plane?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The n-th line in general position crosses the earlier n − 1 lines and so adds n regions. Starting from 1 region: 1 + (1 + 2 + 3 + 4 + 5) = 1 + 15 = 16.
Use the complement for a repeated value
- The complement 补事件 is the event that the given event does not happen. Thus $P(A^c)=1-P(A)$. For $r$ independent uniform picks from $n$ values, the ordered sample space has $n^r$ equally likely outcomes.
- For $r\le n$, the all-distinct outcomes number $n(n-1)\cdots(n-r+1)$. With 3 picks from 10 values, their probability is $720/1000=0.72$, so at least one repeat has probability $0.28$. If $r>n$, a repeat is certain.
Three values are picked independently and uniformly from ten possible values, with replacement. What is the probability of at least one repeated value?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The all-distinct probability is (10·9·8)/10³ = 0.72. Its complement, at least one repeat, has probability 1 − 0.72 = 0.28.
Independent does not mean disjoint
- Independence means $P(A\cap B)=P(A)P(B)$. When $P(B)>0$, conditional probability is $P(A\mid B)=P(A\cap B)/P(B)$; independence then says learning $B$ does not change the probability of $A$.
- Mutually exclusive events have empty intersection, so $P(A\cap B)=0$. If both probabilities are positive, their product is positive and they cannot be independent. On one fair die roll, “even” and “greater than 4” are independent: their intersection is $\{6\}$, with probability $1/6=(1/2)(1/3)$.
Two mutually exclusive events with positive probabilities cannot be independent.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
True. Exclusive means $P(A \cap B) = 0$, but independence needs $P(A \cap B) = P(A)P(B) > 0$.
On one fair six-sided die roll, let A be “even” and B be “greater than 4”. These events are
Difficulty 1/5 · 100 coins + a small bonus on first completion today
P(A) = 1/2, P(B) = 1/3 and P(A ∩ B) = P({6}) = 1/6. The product test holds, but the intersection is not empty.
Check the binomial model before its formula
- $X\sim\operatorname{Binomial}(N,p)$ counts successes in a fixed number $N$ of independent trials, each with two outcomes and the same success probability $p$. Its mean is $Np$ and variance is $Np(1-p)$; for $N=10$, $p=0.3$, these are 3 and 2.1.
- In this model, no successes has probability $(1-p)^N$, so at least one has probability $1-(1-p)^N$. Sampling objects without replacement generally changes the next success probability; a fixed trial count and an initial success rate alone do not establish a binomial model.
A binomial variable has $N = 10$, $p = 0.3$. Its variance is
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$10 \times 0.3 \times 0.7$.
Four independent trials each succeed with probability 0.5. What is the probability of at least one success?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The complement is four failures, with probability (0.5)⁴ = 1/16. Hence at least one success has probability 15/16 = 0.9375.
A bag contains 4 red and 6 blue counters. Draw two uniformly at random without replacement. A student models the red count as Binomial(2, 0.4). Assess the model and find the probability of two reds.
The two draws are dependent: after a red, the next red probability is $3/9$, not $4/10$. Thus the stated binomial model is not exact. The probability of two reds is $(4/10)(3/9)=2/15$, whereas the binomial model would give $0.4^2=0.16$. Equivalently, there are $\binom42=6$ favourable unordered pairs among $\binom{10}2=45$ equally likely pairs.
A recurrence also needs initial values
- A recurrence is a rule that expresses terms of a sequence using earlier terms. For $a_n=2a_{n-1}$, $n\ge1$, the initial value $a_0=3$ gives $3,6,12,\ldots$ and the closed form $a_n=3\cdot2^n$.
- A second-order rule can require two starting values. For $a_n=a_{n-1}+a_{n-2}$, $n\ge2$, specifying only $a_0$ leaves $a_1$ free. State both the range of the recurrence and enough initial data to determine every term.
Verify a formula, not just a few terms
- For $b_n=2b_{n-1}+1$, $n\ge1$, with $b_0=0$, try $b_n=2^n-1$. It has the right initial value, and substitution gives $2(2^{n-1}-1)+1=2^n-1$. The recurrence then determines the same sequence by induction.
- Matching finitely many terms does not prove a formula for every $n$. A proposed answer must satisfy all initial values and the recurrence throughout its stated range; changing an initial value can change the entire sequence.
$b_0=0$ and $b_n=2b_{n-1}+1$ for $n\ge1$. Find $b_5$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The verified closed form is bₙ = 2ⁿ − 1. Thus b₅ = 32 − 1 = 31. Direct iteration gives 0, 1, 3, 7, 15, 31.
For $a_n=3a_{n-1}-2a_{n-2}$, $n\ge2$, with $a_0=0$ and $a_1=1$, prove $a_n=2^n-1$. Explain why only specifying $a_0=0$ would not determine this sequence.
The formula gives $a_0=0$ and $a_1=1$. Substitution yields $3(2^{n-1}-1)-2(2^{n-2}-1)=2^n-1$, so induction proves the formula for all $n\ge0$. If only $a_0=0$ were given, the all-zero sequence would also satisfy the recurrence and that initial value, but it has a different $a_1$. Both initial values matter.
Newton's method uses a tangent
- To approximate a root of a differentiable $f$, use $x_{k+1}=x_k-f(x_k)/f'(x_k)$ whenever $f'(x_k)\ne0$. The next value is where the tangent at $x_k$ meets the horizontal axis.
- For $f(x)=x^2-2$, starting at $x_0=1$ gives $x_1=3/2$ and $x_2=17/12\approx1.4167$, near $\sqrt2\approx1.4142$. Starting at 0 instead makes the formula undefined because $f'(0)=0$.

Apply one Newton step to $f(x) = x^2 - 3$ from $x_0 = 2$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
x₁ = x₀ − f(x₀)/f′(x₀) = 2 − (4 − 3)/(2 · 2) = 2 − 1/4 = 1.75, already close to √3 ≈ 1.732.
A defined Newton step need not converge
- Nonzero derivatives at the iterates make the updates possible; they do not guarantee convergence. The starting value and the function's behaviour matter. An iteration can move away from a root or enter a cycle.
- For $f(x)=x^3-2x+2$, start at 0. Then $f(0)=2$, $f'(0)=-2$, so the next value is 1. At 1, $f(1)=1$, $f'(1)=1$, so the next value is 0. The sequence cycles $0,1,0,1,\ldots$ even though both derivatives are nonzero.
For $f(x)=x^3-2x+2$, Newton iteration starts at 0. It alternates between 0 and 1. What does this show?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The derivatives are −2 at 0 and 1 at 1, so both updates are defined. Neither point is a root, and the two-cycle does not converge.
Bisection keeps a certified bracket
- Bisection 二分法 is a root-finding method that repeatedly halves an interval retaining a root. Require $f$ continuous on $[a,b]$ and $f(a)f(b)<0$; the intermediate value theorem guarantees at least one root. If an endpoint is already a root, return it.
- Test $c=(a+b)/2$. If $f(c)=0$, stop; otherwise retain the half with opposite signs at its endpoints. Continuity matters: $1/x$ has opposite signs at $-1$ and 1, but is undefined at 0 and has no root.
Turn interval width into an error bound
- If the initial bracket has length $L$, after $k$ retained halvings its width is $L/2^k$. The midpoint of that current bracket is within $L/2^{k+1}$ of a retained root. This midpoint need not be the last point already tested.
- For $x^2-2$ on $[1,2]$, the first retained brackets are $[1,1.5]$ and $[1.25,1.5]$. After two halvings, the current midpoint is $1.375$ with error at most $0.125$. After four halvings, the midpoint error bound is $1/32=0.03125$.
An initial continuous sign-change bracket has length 1. After four retained bisection halvings, what is the guaranteed absolute error bound for the midpoint of the current bracket?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The current width is 1/2⁴ = 1/16. Its midpoint is at most half that width from a retained root: 1/32 = 0.03125. The question asks about the current midpoint, not the last tested midpoint.
For $f(x)=x^3-x-1$, justify bisection on $[1,2]$, find the first retained half, and find the least number of retained halvings needed to bound the current midpoint error by 0.01. Explain why the same sign argument cannot be used for $1/x$ on $[-1,1]$.
The polynomial is continuous, with $f(1)=-1$ and $f(2)=5$. At $1.5$, $f(1.5)=0.875>0$, so retain $[1,1.5]$. The original length is 1, and after k retained halvings the current midpoint error is at most $1/2^{k+1}$. Five halvings give $1/64>0.01$; six give $1/128<0.01$, so six suffice and are the least number certified by this bound. The function $1/x$ is not continuous on $[-1,1]$ and has no root; opposite signs alone do not meet the theorem’s hypotheses.
Do not reverse a theorem without checking
- A tree has $n-1$ edges, but that edge count alone does not make a graph a tree. A triangle plus an isolated vertex has 4 vertices and 3 edges, yet is disconnected and has a cycle. For a simple undirected graph, connectivity together with $n-1$ edges does imply a tree.
- A sign change across a continuous function guarantees a root; a root need not give a sign change. The function $x^2$ has a root at 0 but positive values at both endpoints of $[-1,1]$. Failure of the sign-change test is not proof that no root exists.
What does the stated test establish?
Distinguish a bisection root certificate, a defined Newton step and a missing method condition.
Keep the model and the guarantee separate
- State order, repetition and equal-likelihood assumptions before counting a probability. Check independence and constant success probability before using a binomial model. Verify recurrence formulas against both the rule and its initial values.
- A Newton update needs a nonzero derivative but can still cycle. Bisection needs a continuous sign-change bracket; its retained width gives a rigorous midpoint error bound. Distinguish sufficient conditions from necessary ones.
Assess these claims with counterexamples: (i) Every simple undirected graph with n vertices and n − 1 edges is a tree. (ii) If a continuous function has a root in an interval, its endpoint values have opposite signs.
(i) A triangle plus an isolated vertex is a simple graph with 4 vertices and 3 edges. It is disconnected and contains a cycle, so it is not a tree. Connectivity is an additional sufficient condition with that edge count. (ii) The continuous function $f(x)=x^2$ on $[-1,1]$ has root 0 but both endpoint values equal 1. A sign change is sufficient for a continuous function to have a root, but is not necessary.