COMP233 · Chapter 4 Interactive Companion

Number Theory and Methods of Proof

Direct proof, counterexample, rationals, divisibility, and the quotient-remainder theorem.

About this chapter

Chapter 4 is where the logic of Chapters 2 and 3 starts paying back: we use it to prove and disprove real claims about integers. The objects are familiar (even, odd, prime, rational, divisible), but the discipline is new. Every claim is either proved by the generic-particular method or disproved by a single counterexample.

Where it is used. Number theory is the foundation of cryptography (RSA, Diffie-Hellman), hashing, error-correcting codes, and modular arithmetic in every CPU. More immediately, the proof techniques here are the toolkit you will use in every later chapter: induction (Chapter 5), set theory (Chapter 6), functions and relations (Chapters 7 and 8).

Section 4.1Direct proof and counterexample: introduction

Two definitions to memorise word for word. Both directions of "if and only if" are used: the rightward direction tells you what to do when you see an even (or odd) integer; the leftward direction is what you conclude when you have produced the right form.

Definitions (Epp p. 147)

An integer n is even if and only if there exists an integer k such that n = 2k.
An integer n is odd if and only if there exists an integer k such that n = 2k + 1.

Definitions (Epp p. 148)

An integer n > 1 is prime iff for all positive integers r, s, if n = rs then r = 1 ∧ s = n, or r = n ∧ s = 1.
An integer n > 1 is composite iff there exist positive integers r, s with 1 < r < n and 1 < s < n such that n = rs.

Watch. To show n is prime, you must rule out every non-trivial factorisation (a universal claim). To show n is composite, you need to exhibit one non-trivial factorisation (an existential claim). By convention 1 is neither prime nor composite.

4.1.2 Conjecture lab: disproof by counterexample

Caution. Finding no counterexample in |n| ≤ N is not a proof. A larger N could still reveal one, and even searching all integers is impossible. A proof is required.

Conjecture: |n| ≤

4.1.3 Direct proof and the generic-particular method

Suppose x is a particular but arbitrarily chosen element of D for which P(x) holds.
Show, using definitions and known facts, that Q(x) follows.

Theorem 4.1.1 (Epp p. 154)

The sum of any two even integers is even.

Proof

Suppose m and n are particular but arbitrarily chosen even integers. [We must show that m + n is even.]

By definition of even, m = 2r and n = 2s for some integers r and s.

m + n = 2r + 2s = 2(r + s) by the distributive law.

Let t = r + s. Then t is an integer (sum of integers is an integer), and m + n = 2t.

Therefore m + n equals 2 times an integer, so by definition of even, m + n is even.

m = n =

Practice exercises · Section 4.1

Adapted from Epp Section 4.1, suggested questions: 12, 28, 36.

Exercise 4.1.A

Disprove by counterexample: For all integers n, if n is odd then (n − 1)/2 is odd. Use the conjecture lab to find a witness, then write a one-line justification.

Counterexample: n = 5.

Hypothesis: 5 is odd, since 5 = 2·2 + 1. ✓
Conclusion: (5 − 1)/2 = 2, and 2 = 2·1 is even. The conclusion is false. ✗

So n = 5 makes the hypothesis true and the conclusion false: one such case is enough to disprove the universal claim.

Other counterexamples in a small range: n = 1 ((1−1)/2 = 0, even), n = 9 ((9−1)/2 = 4, even).

Exercise 4.1.B

Prove directly: For all integers n, if n is odd then n² is odd.

Suppose n is a particular but arbitrarily chosen odd integer. [We must show n² is odd.]

By definition of odd, n = 2k + 1 for some integer k. Then

n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.

Let t = 2k² + 2k. Then t is an integer (products and sums of integers are integers). So n² = 2t + 1, hence odd by definition.

Exercise 4.1.C

Decide: There exists an integer n such that 6n² + 27 is prime. Prove or disprove.

False. The conjecture lab cannot settle this by failing to find a witness; we need an argument that no integer works.

Proof. Suppose, for contradiction, that 6n² + 27 is prime for some integer n. Notice 6n² + 27 = 3(2n² + 9). Since 2n² + 9 ≥ 9 > 1 is an integer, 6n² + 27 has 3 as a divisor different from itself, so it is composite. Contradiction. Hence no such n exists.

Sample values: n = 0 gives 27 = 3·9; n = 1 gives 33 = 3·11; n = 2 gives 51 = 3·17. All composite.

Exercise 4.1.D (Epp 4.1.24)

Prove directly: For all integers m and n, if m + n is even, then m − n is even.

Suppose m, n are particular but arbitrarily chosen integers with m + n even. [We must show m − n is even.]

By definition of even, m + n = 2k for some integer k. Then m = 2k − n, so

m − n = (2k − n) − n = 2k − 2n = 2(k − n).

Let t = k − n. Then t is an integer (difference of integers is an integer), and m − n = 2t. Therefore m − n is even by definition.

Exercise 4.1.E · Find the mistake (Epp 4.1.38-style)

The following proof of a true statement contains an error. Identify the mistake and write the correct proof.

Theorem. The sum of any two even integers is even.

"Proof". Suppose m and n are even integers. By definition of even, m = 2k and n = 2k for some integer k. Then m + n = 2k + 2k = 4k = 2(2k), which is even, with witness 2k.

The mistake. The flawed "proof" uses the same letter k for two independent witnesses. The definition of even says n = 2k for some integer k; the k that witnesses m need not be the same as the k that witnesses n.

For example, m = 2 has witness k = 1, but n = 6 has witness k = 3. Forcing both to use the same k shrinks the claim from "any two even integers" to "any two identical even integers", which is much weaker.

Correct proof. Suppose m and n are particular but arbitrarily chosen even integers. By definition of even, m = 2r and n = 2s for some integers r and s (possibly different).

m + n = 2r + 2s = 2(r + s).

Let t = r + s (an integer, sum of integers). Then m + n = 2t, so m + n is even.

Why we drill on this. "Find the mistake" exercises catch the most common error in proof writing: collapsing two independent existential witnesses into one. The slides flag these as high-value for the midterm.

Section 4.2Rational numbers

Definition (Epp p. 163)

A real number r is rational if and only if it can be written as a quotient of two integers with nonzero denominator: ∃ integers a, b such that r = a/b and b ≠ 0. A real number that is not rational is irrational.

The word "rational" contains "ratio". A rational number is, literally, a ratio of integers.

4.2.1 Rational or irrational?

Value	Classification	Witness
10 / 3	Rational	a = 10, b = 3
−5 / 39	Rational	a = −5, b = 39
0.281	Rational	281 / 1000 (any finite decimal is rational)
7	Rational	7 / 1 (every integer is rational, Theorem 4.2.1)
0	Rational	0 / 1
2 / 0	Not a number	Division by zero is undefined; not rational, not irrational, just undefined.
0.12121212…	Rational	12 / 99 (proved below)
π	Irrational	Cannot be written as a/b.
√2	Irrational	Proved by contradiction in Section 4.7.

Watch. 2/0 is not irrational. Irrational numbers are real numbers that are not rational; 2/0 is not a number at all.

4.2.3 Famous irrationals

Symbol	Approximation	Identity
π	3.14159 26535 89793…	Ratio of a circle's circumference to its diameter
√2	1.41421 35623 73095…	Diagonal of a unit square; proved irrational in Section 4.7
√3	1.73205 08075 68877…
√5	2.23606 79774 99790…
φ = (1 + √5) / 2	1.61803 39887 49895…	The golden ratio (النسبة الذهبية)
e	2.71828 18284 59045…	Euler's number (العدد النيبيري)

4.2.4 Closure theorems for rationals

a = b (≠ 0) = c = d (≠ 0) = Operation:

Theorem 4.2.2 (Epp p. 165)

The sum of any two rational numbers is rational.

Proof of Theorem 4.2.2

Suppose r and s are rational. [We must show r + s is rational.]

By definition of rational, r = a/b and s = c/d for some integers a, b, c, d with b ≠ 0 and d ≠ 0.

r + s = a/b + c/d = (ad + bc) / bd by basic algebra.

Let p = ad + bc and q = bd. Then p, q are integers, and q = bd ≠ 0 by the zero-product property (since b, d ≠ 0).

So r + s = p/q with p, q integers and q ≠ 0. Therefore r + s is rational.

Corollary 4.2.3 (Epp p. 168)

The double of a rational number is rational. (Cite Theorem 4.2.2 directly: 2r = r + r.)

4.2.5 Deriving new results from old: the seven even/odd properties

Sum, product, and difference of any two even integers are even.

Sum and difference of any two odd integers are even.

Product of any two odd integers is odd.

Product of any even integer and any odd integer is even.

Sum of any odd integer and any even integer is odd.

Difference of any odd integer minus any even integer is odd.

Difference of any even integer minus any odd integer is odd.

Worked sketch (Epp Example 4.2.3). If a is even and b is odd, then (a² + b² + 1)/2 is an integer.

a even ⇒ a² even (property 1). b odd ⇒ b² odd (property 3). a² + b² even + odd ⇒ odd (property 5). (a² + b²) + 1 odd + odd ⇒ even (property 2). So a² + b² + 1 = 2k for some integer k, hence (a² + b² + 1)/2 = k, an integer.

Practice exercises · Section 4.2

Adapted from Epp Section 4.2, suggested questions: 16, 17, 22.

Exercise 4.2.A

True or false: The difference of any two rational numbers is a rational number. Prove or disprove.

True.

Suppose r and s are rational. By definition, r = a/b and s = c/d for integers a, b, c, d with b ≠ 0 and d ≠ 0. Then

r − s = a/b − c/d = (ad − bc) / bd.

Let p = ad − bc and q = bd. Both are integers (differences and products of integers are integers), and q ≠ 0 by the zero-product property. Hence r − s = p/q is rational.

Exercise 4.2.B

Prove: The quotient of any two rational numbers, where the divisor is nonzero, is a rational number.

Suppose r and s are rational and s ≠ 0. By definition, r = a/b and s = c/d for integers a, b, c, d with b ≠ 0 and d ≠ 0. Since s ≠ 0, also c ≠ 0 (otherwise s = 0/d = 0). Then

r / s = (a/b) / (c/d) = (a · d) / (b · c) = ad / bc.

Let p = ad and q = bc. Both are integers; q = bc ≠ 0 by the zero-product property. Hence r/s = p/q with q ≠ 0, so r/s is rational.

Exercise 4.2.C

True or false: If a is any odd integer, then a² + a is even. Prove or disprove.

True. Suppose a is any odd integer. Then a = 2k + 1 for some integer k. So

a² + a = (2k + 1)² + (2k + 1) = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1).

Let t = 2k² + 3k + 1 (an integer). Then a² + a = 2t, hence even by definition.

Sharper insight. a² + a = a(a + 1) is the product of two consecutive integers, one of which is always even. The proof above only handles a odd; the general fact follows from Theorem 4.4.2 (Section 4.4).

Exercise 4.2.D (Epp 4.2.15)

Prove: The product of any two rational numbers is a rational number.

Suppose r and s are rational. By definition, r = a/b and s = c/d for some integers a, b, c, d with b ≠ 0 and d ≠ 0. Then

r · s = (a/b) · (c/d) = (a · c) / (b · d) = ac / bd.

Let p = ac and q = bd. Both are integers (products of integers are integers), and q = bd ≠ 0 by the zero-product property. Hence r · s = p/q with q ≠ 0, so r · s is rational.

Together with Exercises 4.2.A and 4.2.B: the rationals are closed under all four basic operations (with division requiring a nonzero divisor). This is the closure result that makes ℚ a field.

Exercise 4.2.E (Epp 4.2.22, uses Property 1 and Property 3)

Use the seven even/odd properties (Section 4.2.5) to prove: If m is any even integer and n is any odd integer, then 5m + 3n is odd.

Suppose m is even and n is odd.

5m is a product of an even and odd integer (5 is odd), so 5m is even by property 4.
3n is the product of two odd integers (3 and n), so 3n is odd by property 3.
5m + 3n is the sum of an even integer and an odd integer, so it is odd by property 5.

Therefore 5m + 3n is odd.

What this exercises. Citing pre-proved results by number, instead of re-expanding the definitions of even and odd. Once the seven properties are established, every later proof reads as a short chain of citations.

Section 4.3Divisibility

Definition (Epp p. 170)

If n and d are integers with d ≠ 0, then n is divisible by d iff n = dk for some integer k. Notation: d | n (read "d divides n"). Equivalent phrases: n is a multiple of d, d is a factor of n, d is a divisor of n.

Watch the distinction. a | b is a sentence (true or false). a / b is a number (may or may not be an integer). Example: 3 | 12 is true; 3 | 7 is false; 12 / 3 = 4; 7 / 3 ≈ 2.333.

4.3.2 Properties of divisibility

Theorem 4.3.1: a positive divisor is at most as large

For all integers a, b: if a, b > 0 and a | b, then a ≤ b.

Theorem 4.3.2: divisors of 1

The only integer divisors of 1 are 1 and −1.

Theorem 4.3.3: transitivity of divisibility

For all integers a, b, c: if a | b and b | c, then a | c.

Proof of Theorem 4.3.3 (transitivity)

Suppose a, b, c are integers with a | b and b | c. [We must show a | c.]

By definition, b = ar for some integer r, and c = bs for some integer s.

c = bs = (ar)s = a(rs).

Let k = rs. Then k is an integer, and c = ak, so a | c by definition.

Live demo. Pick three integers and watch the transitivity check.

a = b = c =

Theorem 4.3.4: every n > 1 has a prime divisor

Any integer n > 1 is divisible by some prime number.

4.3.4 The unique factorisation theorem

Theorem 4.3.5 (Gauss, 1801)

For any n > 1 there exist a positive integer k, distinct primes p₁ < p₂ < … < pₖ, and positive integers e₁, …, eₖ such that
n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ.

Worked example (Epp Example 4.3.9, p. 175)

Suppose m is an integer with 8·7·6·5·4·3·2·m = 17·16·15·14·13·12·11·10. Does 17 | m?

Yes. The prime 17 appears on the right (as 17 itself). By unique factorisation, it must also appear on the left. Each of 2, 3, 4, 5, 6, 7, 8 is less than 17, so none of their prime factors is 17. Hence 17 must appear in m: 17 | m.

Practice exercises · Section 4.3

Adapted from Epp Section 4.3, suggested questions: 13, 21, 29.

Exercise 4.3.A

Prove: For all integers a, b, c, if a | b and a | c, then a | (b − c).

Suppose a, b, c are integers with a | b and a | c. By definition, b = ar and c = as for some integers r, s. Then

b − c = ar − as = a(r − s).

Let t = r − s (an integer). Then b − c = at, so a | (b − c) by definition.

Exercise 4.3.B

Prove or disprove: For all integers a, b, if a | b then a | b².

True. Suppose a, b are integers with a | b. Then b = ak for some integer k. So

b² = (ak)² = a² k² = a · (ak²).

Let t = ak² (an integer). Then b² = at, hence a | b².

Exercise 4.3.C

Disprove by counterexample: For all integers a, b, c, if a | (b · c) then a | b or a | c.

False. Counterexample: a = 6, b = 4, c = 9.

b · c = 4 · 9 = 36 and 6 | 36 since 36 = 6·6. ✓ hypothesis
6 ∤ 4 (since 4 = 6·0 + 4) and 6 ∤ 9 (since 9 = 6·1 + 3). ✗ conclusion

The hypothesis is true and the conclusion is false, so the universal claim is disproved.

Why this happens. 6 = 2·3 splits its prime factors between b (which has a factor of 2) and c (which has a factor of 3). The product gathers both, but neither side alone has both. The statement does hold when a is prime (Euclid's lemma); composite a can fail.

Exercise 4.3.D (Epp 4.3.8)

Write 3,300 in standard factored form (primes in ascending order, each with its multiplicity).

Strip out one prime at a time.

3,300 = 100 · 33 = 4 · 25 · 3 · 11 = 2 · 2 · 5 · 5 · 3 · 11.

Sort the primes ascending and collect powers:

3,300 = 2² · 3 · 5² · 11.

Verify: 4 · 3 · 25 · 11 = 4 · 3 · 275 = 12 · 275 = 3,300. ✓

The factorisation explorer above produces the same result for any n ≥ 2. By the unique factorisation theorem, this representation is the only one.

Exercise 4.3.E (Epp 4.3 style, similar to Example 4.3.9)

Suppose m is an integer with 14 · 13 · 12 · 11 · 10 · m = 30 · 29 · 28 · 27 · 26 · 25. Does 29 | m?

Yes. Argue by unique factorisation.

29 is prime, and it appears on the right (as 29 itself).
By the unique factorisation theorem, 29 must also appear among the prime factors of the left side.
Each of 14, 13, 12, 11, 10 is strictly less than 29, so none of them has 29 as a factor.
Therefore 29 must appear in the factorisation of m, which means 29 | m.

Pattern. This is the same argument as Epp's 17 | m worked example. Whenever a prime p appears on one side of an equation but is "too large" to be hidden in any of the other factors on the other side, it must show up in the unknown.

Section 4.4Quotient-remainder theorem and division into cases

Long division from grade school, formalised. The theorem fixes unique integers q and r for any pair (n, d) with d > 0.

Theorem 4.4.1: the quotient-remainder theorem (نظرية القسمة)

Given any integer n and positive integer d, there exist unique integers q and r such that
n = dq + r and 0 ≤ r < d.

4.4.2 div and mod, with applications

(1) Day of the week, one year from today. Today is Tuesday; neither year is a leap year. What day is it 365 days from now?

365 div 75252 full weeks

365 mod 711 extra day

AnswerWednesday

(2) Solving with mod. Suppose m mod 11 = 6. What is 4m mod 11?

Solution (Epp Example 4.4.4)

Translate: m mod 11 = 6 ⇔ m = 11q + 6 for some integer q.

4m = 4(11q + 6) = 44q + 24 = 44q + 22 + 2 = 11(4q + 2) + 2.

4q + 2 is an integer, and 0 ≤ 2 < 11. Therefore 4m mod 11 = 2.

Watch (language note). In Python, % returns a non-negative remainder when the divisor is positive (matches Epp). In C, C++, and Java, % can return a negative result when n < 0. The companion uses Python-style mod throughout.

4.4.3 Parity property and proof by division into cases

Theorem 4.4.2: parity of consecutive integers (Epp p. 184)

Any two consecutive integers have opposite parity: one is even, the other is odd.

Proof (by division into cases, البرهان بالحالات)

Suppose m, m + 1 are two consecutive integers. By the parity property, either m is even or m is odd.

Case 1. m is even. Then m = 2k for some integer k. So m + 1 = 2k + 1, which is odd by definition.

Case 2. m is odd. Then m = 2k + 1 for some integer k. So m + 1 = (2k + 1) + 1 = 2(k + 1), which is even.

In both cases, exactly one of m, m + 1 is even and the other is odd.

Theorem 4.4.3: the square of any odd integer has the form 8m + 1 (Epp p. 186)

For every odd integer n, there exists an integer m such that n² = 8m + 1.

Proof (cases mod 4)

Every odd integer n has the form n = 4q + 1 or n = 4q + 3 for some integer q.

Case 1. n = 4q + 1:
n² = 16q² + 8q + 1 = 8(2q² + q) + 1. Let m = 2q² + q.

Case 2. n = 4q + 3:
n² = 16q² + 24q + 9 = 8(2q² + 3q + 1) + 1. Let m = 2q² + 3q + 1.

In both cases n² = 8m + 1.

4.4.6 Absolute value and the triangle inequality

Lemma 4.4.4 (Epp p. 190)

For all real numbers r: −|r| ≤ r ≤ |r|.

Theorem 4.4.6: the triangle inequality (Epp p. 191)

For all real numbers x, y: |x + y| ≤ |x| + |y|.

Live verification. Pick x and y; the panel computes both sides.

x = y =

Practice exercises · Section 4.4

Adapted from Epp Section 4.4, suggested questions: 4, 8, 22.

Exercise 4.4.A

Find q and r with 0 ≤ r < d such that n = dq + r:

n = 3, d = 11
n = −45, d = 11

(1) 3 = 11·0 + 3. So q = 0, r = 3. (Verify: 0 ≤ 3 < 11 ✓.)

(2) −45 = 11·(−5) + 10. So q = −5, r = 10. (Verify: 11·(−5) = −55, and −55 + 10 = −45 ✓. 0 ≤ 10 < 11 ✓.)

The quotient is −5, not −4. We "overshoot" below n so the remainder stays non-negative.

Exercise 4.4.B

Evaluate 50 div 7 and 50 mod 7.

50 div 7 = 7; 50 mod 7 = 1. Verify: 7·7 + 1 = 50 ✓; 0 ≤ 1 < 7 ✓.

Exercise 4.4.C

Prove: For every integer n, n² + n is even. (Use division into cases mod 2.)

Suppose n is any integer. By the quotient-remainder theorem with d = 2, either n = 2q or n = 2q + 1 for some integer q.

Case 1: n = 2q. n² + n = 4q² + 2q = 2(2q² + q). Let t = 2q² + q (an integer). Then n² + n = 2t, hence even.

Case 2: n = 2q + 1. n² + n = (2q+1)² + (2q+1) = 4q² + 4q + 1 + 2q + 1 = 4q² + 6q + 2 = 2(2q² + 3q + 1). Let t = 2q² + 3q + 1 (an integer). Then n² + n = 2t, hence even.

In both cases n² + n is even.

Quicker insight. n² + n = n(n + 1) is the product of two consecutive integers, one of which is even by Theorem 4.4.2.

Exercise 4.4.D (Epp Example 4.4.4 generalised)

Suppose a is an integer with a mod 7 = 3. What is 5a mod 7? (Show the derivation step by step.)

Translate the hypothesis using the quotient-remainder theorem:

a mod 7 = 3 ⇔ a = 7q + 3 for some integer q.

Multiply by 5:

5a = 5(7q + 3) = 35q + 15.

Rewrite 15 as a multiple of 7 plus a remainder in [0, 7): 15 = 7·2 + 1.

5a = 35q + 14 + 1 = 7(5q + 2) + 1.

5q + 2 is an integer, and 0 ≤ 1 < 7. So 5a mod 7 = 1.

Method. Same template as Epp Example 4.4.4 (the m mod 11 problem): translate the hypothesis to a = dq + r, do the algebra, then rewrite the constant term as d · (something) + (new remainder in [0, d)).

Exercise 4.4.E (Epp 4.4.22)

Prove: For every integer n, the product n(n + 1)(n + 2) is divisible by 3. Use division into cases mod 3.

Suppose n is any integer. By the quotient-remainder theorem with d = 3, exactly one of the following holds: n = 3q, n = 3q + 1, or n = 3q + 2, for some integer q.

Case 1: n = 3q. Then n itself is a multiple of 3, so n(n+1)(n+2) = 3q · (n+1)(n+2) = 3 · [q(n+1)(n+2)]. The bracket is an integer, so the product is divisible by 3.

Case 2: n = 3q + 1. Then n + 2 = 3q + 3 = 3(q + 1) is a multiple of 3, so n(n+1)(n+2) = n(n+1) · 3(q+1) = 3 · [n(n+1)(q+1)]. Divisible by 3.

Case 3: n = 3q + 2. Then n + 1 = 3q + 3 = 3(q + 1) is a multiple of 3, so n(n+1)(n+2) = n · 3(q+1) · (n+2) = 3 · [n(q+1)(n+2)]. Divisible by 3.

In every case 3 | n(n+1)(n+2).

Intuition. Three consecutive integers always include one multiple of 3. Cases mod 3 makes the argument formal.

Recap: Chapter 4

Memorise the definitions of even, odd, prime, composite, rational, irrational, and divisibility. Both directions of "if and only if" are used in proofs.
Identify the shape of each claim first: universal (∀) or existential (∃). The strategy depends on the shape.
To disprove a universal, exhibit one counterexample. The counterexample must satisfy the hypothesis and fail the conclusion.
To prove a universal, use the direct-proof template: suppose an arbitrary element, apply definitions and known results, conclude.
Cite Theorems 4.1.1 (sum of evens), 4.2.2 (sum of rationals), 4.3.3 (transitivity of divisibility), 4.3.5 (unique factorisation), and 4.4.1 (quotient-remainder) by number once they are proved. The seven even/odd properties are a reusable toolbox.
The quotient-remainder theorem partitions integers into classes by remainder. Pick the right modulus and use division into cases: prove the claim in each class, conclude for all integers.
Watch the language gap: a | b is a sentence; a / b is a number. Python's % matches Epp's mod for positive divisors; C and Java do not, when the dividend is negative.

What's next. Chapter 5: Sequences and Mathematical Induction. The same proof discipline scales to claims about every term of an infinite sequence, using a clean two-step template (base case + inductive step).