Definition 85. A function f is a rule that takes a whole number n as operand and yields a complex number, written f(n). "f is defined for n ≦ p" means the rule yields a number for each of 1, 2, up to p. So what is given is a finite series of numbers in order, by a rule. Two rules that differ are two functions, even when they yield the same for each n ≦ p; then they are equivalent for n ≦ p. "Exactly one" below means: any two are equivalent.
In this section k, m, n, p, q are positive whole numbers unless said otherwise, and ∗ stands throughout for + or throughout for •. All that is used of ∗ is that it is commutative and associative.
A correspondence between the n ≦ p and the m ≦ q is a function s that yields for each n ≦ p some s(n) ≦ q, different for different n, such that each m ≦ q is s(n) for some n.
Theorem 406 (Landau 274). If p < q, there is no correspondence between the m ≦ p and the n ≦ q.
Proof: By induction on p.
For p = 1 and q > 1: the one m = 1 corresponds to one n, and 1 and q are two.
Let it hold for p, and let q > p + 1, so q − 1 > p. Suppose a correspondence s between the m ≦ p + 1 and the n ≦ q. If s(p + 1) = q, then s for m ≦ p is a correspondence with the n ≦ q − 1, which is impossible. If s(p + 1) = n₀ < q, let s(m₀) = q, so m₀ ≦ p. Let t be as s for m ≦ p except t(m₀) = n₀. Then t is a correspondence between the m ≦ p and the n ≦ q − 1, which is impossible.
So no multitude has two counts.
Theorem 407 (Landau 275). Let f be defined for n ≦ p. Then there is exactly one g, defined for n ≦ p, such that
g(1) = f(1), and g(n + 1) = g(n) ∗ f(n + 1) for n < p.
It is written gₚ where p must be shown.
Proof: (1) Any two are equivalent. Let g and h both serve. g(1) = f(1) = h(1). If g(n) = h(n) and n < p, then g(n + 1) = g(n) ∗ f(n + 1) = h(n) ∗ f(n + 1) = h(n + 1). So g(n) = h(n) for each n ≦ p, by induction on n.
(2) There is one, by induction on p. For p = 1, let g₁(1) = f(1); the second condition asks nothing. Let it hold for p, and let f be defined for n ≦ p + 1. Then f is defined for n ≦ p, and there is gₚ. Let gₚ₊₁(n) = gₚ(n) for n ≦ p, and gₚ₊₁(p + 1) = gₚ(p) ∗ f(p + 1). Then gₚ₊₁(1) = f(1); for n < p the second condition holds as it did for gₚ; and for n = p it holds by construction.
Theorem 408 (Landau 276). If f is defined for n ≦ p + 1, then gₚ₊₁(p + 1) = gₚ(p) ∗ f(p + 1).
From the construction in Theorem 407 (2), and (1).
Definition 86 (Landau 69). If f is defined for n ≦ p, then ∗[1..p] f(n) = gₚ(p). When ∗ is +, it is written Σ[1..p] f(n), the sum. When ∗ is •, it is written Π[1..p] f(n), the product.
By Theorem 407 (1), equivalent functions have the same sum and the same product.
Theorem 409 (Landau 277). ∗[1..1] f(n) = f(1).
g₁(1) = f(1).
Theorem 410 (Landau 278). If f is defined for n ≦ p + 1, then ∗[1..p+1] f(n) = ∗[1..p] f(n) ∗ f(p + 1).
Theorem 408.
Theorem 411 (Landau 279). If f(n) = x for each n ≦ p, then Σ[1..p] f(n) = x • [p, 0].
Proof: By induction on p. For p = 1: x = x • e = x • [1, 0]. If it holds for p, then Σ[1..p+1] f(n) = x • [p, 0] + x • [1, 0] = x • ([p, 0] + [1, 0]) = x • [p + 1, 0].
This is multiplication by a whole number recovered as repeated addition, which is where the account began.
Theorem 412 (Landau 280). ∗[1..2] f(n) = f(1) ∗ f(2).
Theorems 410 and 409.
Theorem 413 (Landau 281). If f is defined for n ≦ p + q, then ∗[1..p+q] f(n) = ∗[1..p] f(n) ∗ ∗[1..q] f(p + n).
Proof: Fix p. By induction on q. For q = 1: Theorems 410 and 409. If it holds for q, then
∗[1..p+(q+1)] f(n) = ∗[1..p+q] f(n) ∗ f((p + q) + 1) = (∗[1..p] f(n) ∗ ∗[1..q] f(p + n)) ∗ f(p + (q + 1)) = ∗[1..p] f(n) ∗ (∗[1..q] f(p + n) ∗ f(p + (q + 1))) = ∗[1..p] f(n) ∗ ∗[1..q+1] f(p + n).
Theorem 414 (Landau 282). If f and g are defined for n ≦ p, then ∗[1..p] (f(n) ∗ g(n)) = ∗[1..p] f(n) ∗ ∗[1..p] g(n).
Proof: By induction on p. For p = 1: both sides are f(1) ∗ g(1). For the step, since (a ∗ b) ∗ (c ∗ d) = (a ∗ c) ∗ (b ∗ d),
∗[1..p+1] (f(n) ∗ g(n)) = (∗[1..p] f(n) ∗ ∗[1..p] g(n)) ∗ (f(p + 1) ∗ g(p + 1)) = (∗[1..p] f(n) ∗ f(p + 1)) ∗ (∗[1..p] g(n) ∗ g(p + 1)).
Lemma (exchange). Let h and h′ be defined for n ≦ p and yield the same for each n ≦ p except perhaps for n = j. Then ∗[1..p] h(n) ∗ h′(j) = ∗[1..p] h′(n) ∗ h(j).
Proof: By induction on p. For p = 1: h(1) ∗ h′(1) = h′(1) ∗ h(1). Let it hold for p, and take h, h′ for n ≦ p + 1.
If j = p + 1: h and h′ are equivalent for n ≦ p, so they have the same ∗[1..p], call it a. Then (a ∗ h(p + 1)) ∗ h′(p + 1) = (a ∗ h′(p + 1)) ∗ h(p + 1).
If j ≦ p: h(p + 1) = h′(p + 1) = c. Then (∗[1..p] h(n) ∗ c) ∗ h′(j) = (∗[1..p] h(n) ∗ h′(j)) ∗ c = (∗[1..p] h′(n) ∗ h(j)) ∗ c = (∗[1..p] h′(n) ∗ c) ∗ h(j).
Theorem 415 (Landau 283). Let s be a correspondence between the n ≦ p and the m ≦ p, and let f be defined for n ≦ p. Then ∗[1..p] f(s(n)) = ∗[1..p] f(n).
Proof: By induction on p. For p = 1: s(1) = 1. Let it hold for p, for any s and f, and let s be a correspondence between the n ≦ p + 1 and the m ≦ p + 1.
(1) If s(p + 1) = p + 1, then s for n ≦ p is a correspondence with the m ≦ p, and ∗[1..p+1] f(s(n)) = ∗[1..p] f(s(n)) ∗ f(p + 1) = ∗[1..p] f(n) ∗ f(p + 1).
(2) If s(p + 1) = k ≦ p, let s(j) = p + 1, so j ≦ p. Let t(n) = s(n) for n ≦ p other than j, and t(j) = k. Then t is a correspondence between the n ≦ p and the m ≦ p: its values are ≦ p; they differ, since k is s(n) for no n ≦ p; and each m ≦ p is reached, k by j and any other by the n with s(n) = m. Let h(n) = f(s(n)) and h′(n) = f(t(n)) for n ≦ p. They differ only at j, where h(j) = f(p + 1) and h′(j) = f(k). By the Lemma,
∗[1..p+1] f(s(n)) = ∗[1..p] h(n) ∗ f(k) = ∗[1..p] h′(n) ∗ f(p + 1) = ∗[1..p] f(n) ∗ f(p + 1) = ∗[1..p+1] f(n).
In Definition 87 and Theorems 416 to 418, the letters k, p, q, v stand for any whole numbers, positive, 0 or negative.
Definition 87 (Landau 70). Let q ≦ p, and let f be defined for q ≦ n ≦ p. Then ∗[q..p] f(n) = ∗[1.. (p+1)−q] f((n + q) − 1).
Here (p + 1) − q is positive, and q ≦ (n + q) − 1 ≦ p for 1 ≦ n ≦ (p + 1) − q. For q = 1 this agrees with Definition 86.
Theorem 416 (Landau 284). Let q ≦ k < p, and let f be defined for q ≦ n ≦ p. Then ∗[q..p] f(n) = ∗[q..k] f(n) ∗ ∗[k+1..p] f(n).
Proof: ((k + 1) − q) + (p − k) = (p + 1) − q. So by Definition 87 and Theorem 413,
∗[q..p] f(n) = ∗[1..(k+1)−q] f((n + q) − 1) ∗ ∗[1..p−k] f(((((k + 1) − q) + n) + q) − 1).
The first is ∗[q..k] f(n). In the second, (((k + 1) − q) + n) + q = n + (k + 1), so it is ∗[1..(p+1)− (k+1)] f((n + (k + 1)) − 1) = ∗[k+1..p] f(n).
Theorem 417 (Landau 285). Let q ≦ p, and let f be defined for q ≦ n ≦ p. Then ∗[q..p] f(n) = ∗[q+v..p+v] f(n − v).
By Definition 87 the right side is ∗[1..((p+v)+1)−(q+v)] f(((n + (q + v)) − 1) − v) = ∗[1.. (p+1)−q] f((n + q) − 1).
Theorem 418 (Landau 286). Let q ≦ p, let f be defined for q ≦ n ≦ p, and let s be a correspondence between the n with q ≦ n ≦ p and the m with q ≦ m ≦ p. Then ∗[q..p] f(s(n)) = ∗[q..p] f(n).
Proof: s₁(n) = s((n + q) − 1) − (q − 1) is a correspondence between the positive n ≦ (p + 1) − q and the positive m ≦ (p + 1) − q. By Theorem 415,
∗[q..p] f(s(n)) = ∗[1..(p+1)−q] f(s₁(n) + (q − 1)) = ∗[1..(p+1)−q] f(n + (q − 1)) = ∗[q..p] f(n).
From here on the letters stand again for positive whole numbers.
Theorem 419 (Landau 287). If f is defined for n ≦ p, there is a Ξ such that |Σ[1..p] f(n)| ≦ Ξ and Σ[1..p] [|f(n)|, 0] = [Ξ, 0].
Proof: By induction on p. For p = 1, Ξ = |f(1)|. If Ξ serves for p, then Ξ + |f(p + 1)| serves for p + 1: by Theorem 403, |Σ[1..p+1] f(n)| ≦ |Σ[1..p] f(n)| + |f(p + 1)| ≦ Ξ + |f(p + 1)|; and [Ξ, 0] + [|f(p + 1)|, 0] = [Ξ + |f(p + 1)|, 0].
Theorem 420 (Landau 288). If f is defined for n ≦ p, then [|Π[1..p] f(n)|, 0] = Π[1..p] [|f(n)|, 0].
Proof: By induction on p. For p = 1, both sides are [|f(1)|, 0]. For the step, by Theorem 400,
Π[1..p+1] [|f(n)|, 0] = [|Π[1..p] f(n)|, 0] • [|f(p + 1)|, 0] = [|Π[1..p] f(n)| • |f(p + 1)|, 0] = [| Π[1..p+1] f(n)|, 0].
Theorem 421 (Landau 289). If f is defined for n ≦ p, then Π[1..p] f(n) = o if and only if f(n) = o for some n ≦ p.
Proof: By induction on p. For p = 1, obvious. For the step, Π[1..p] f(n) • f(p + 1) = o if and only if Π[1..p] f(n) = o or f(p + 1) = o, by Theorem 353; that is, if and only if f(n) = o for some n ≦ p or for n = p + 1.