Stepnumbers: Chapter 2 — The Binary Number System and the Binomial Coefficients — Antal Fekete

The binary number system and the binomial coefficients

Before we proceed with the introduction of the stepnumber system let us review the binary number system in this Chapter and Cantor’s, using infinitely many digits, in the next.

In enumerating binary numbers we are doing more than simply putting the natural numbers into binary code. We are also counting the number of finite subsets, as well as constructing them. For example, if we want to count the number of subsets of a set of four elements, we turn to the up-front-0 representation of binary numbers:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Not only have we counted the number of subsets of a set of four elements (and found it to be 16) but we have also constructed every one of them, e.g., 0000 is the trivial subset and 1111 is the universal subset. The construction uses the idea of a characteristic function and the convention that the places which the digits occupy constitute the elements of an ordered set. In our example that set has four elements, namely, the four places we need to write a 4-digit number. A characteristic function is defined by postulating that the digit 1 indicates that the place in apposition is included in the subset; the digit 0 indicates that it is not. Thus 0101 represents the two-element subset consisting of the second and fourth elements of the 4-set. In this way every subset of the 4-set has been accounted for once, and only once. It is clear that we can also set up a one-to-one correspondence between the subsets of an n-set and binary numbers of at most n digits for all n.

In view of the foregoing discussion on representing subsets by binary numbers, we can give an equivalent definition of the binomial coefficients as follows. Given n and k, 0 ≤ k ≤ n ,

⎛n⎞

⎜ k ⎟ is the number of binary numbers of at most n digits of which exactly k are valuable.

⎝ ⎠

We proceed to review the basic properties of the binomial coefficients here in order to establish the language and pattern that we shall be using in treating factorial coefficients in relation to Cantor’s number system, and spectral coefficients in relation to the stepnumber system, as well as Stirling numbers of either kind. The equivalence of the two definitions of the binomial coefficients is a simple consequence of the fact that counting subsets can be done by counting characteristic functions, which in turn can be done by counting binary numbers in up-front-0 representation.

⎛n⎞

It is immediate that ⎜ ⎟ = 1 and ⎜ ⎟ = 1, as there is only one binary number with no

⎝ 0⎠

⎝1⎠ valuable digits, namely 0, and there is only one of exactly n digits all of which are valuable, namely 1n .We also have the

Symmetry Property

⎛n⎞ ⎛ n ⎞

⎜k ⎟ = ⎜n − k ⎟

⎝ ⎠ ⎝

⎠

This property has no counterpart for factorial coefficients of Cantor’s number system, for spectral coefficients of the stepnumber system, or for Stirling numbers. To prove it we may observe that, given a binary number a of k valuable digits, the equation x + a = 1n has a unique solution which, as a binary number, has exactly n − k valuable digits.

Recursion Formula

⎛ n ⎞ ⎛ n − 1⎞ ⎛ n − 1⎞

⎜ k ⎟ = ⎜ k − 1⎟ + ⎜ k ⎟

⎝ ⎠ ⎝

⎠ ⎝

⎠

It is, in fact, a difference equation which, under the

Initial Condition

⎛n⎞

⎜1⎟ = 1

⎝ ⎠ yields a unique solution, conveniently tabulated in the form proposed by Blaise Pascal (1623-1662), with ⎛n⎞ th th

⎜ k ⎟ standing in the k place of the n row (the counting of places and rows starts with 0).

⎝ ⎠

Binomial coefficients in Pascal's triangle

715 1287 1716

1716 1287 715

78 13

A more extensive table can be found at the end of the book. Pascal’s innovation in tabulating the binomial coefficients in this format has become the source of a wealth of information.

Summation Formula

⎛n⎞ ⎛n⎞ ⎛n⎞

⎛n⎞ n

⎜ 0 ⎟ + ⎜ 1 ⎟ + ⎜ 2 ⎟ + ... + ⎜ n ⎟ = 2

⎝ ⎠ ⎝ ⎠ ⎝ ⎠

⎝ ⎠

The familiar identity (1 + 2 + 22 + ... + 2n) + 1 = 2n+1 furnishes the

Overflow Formula

1n + 1 = 10n

To prove the Recursion Formula let us distinguish one place by calling it ‘zero place’, and survey the binary numbers according as they have the digit 0 or the digit 1 in the zero place. In this manner we have considered every binary number of at most n digits of which exactly k are valuable once and only once. This completes the proof. The binomial coefficients earn their name by the role they play in the

Binomial Theorem

⎛n⎞

(1 + x ) n = 1 + ⎜ ⎟ x + ⎜ ⎟ x 2 + ... + ⎜ ⎟ x n

⎝1⎠

⎝2⎠

⎝n⎠

Sierpinski’s Triangles (mod p)

If we blot out the entries of Pascal’s triangle and replace them with dummies ○, ●, ●, ●,…, ● according as the entry in question is congruent to 0, 1, 2, 3, ..., p − 1 (mod p), then we get what is known as the (colored) Sierpinski triangle. Like Pascal’s, it is infinite.

Let p be an odd prime number. The binomial coefficients in row pn between entries 1 and n p − 1 inclusive, in row pn + 1 between entries 2 and pn − 2 inclusive, in row pn + 3 between entries 3 and pn − 3 inclusive, etc.,..., are divisible by p, for n = 1, 2, 3,... The pattern continues all the way down to row ⎛ 2 pn − 2 ⎞

2pn − 2 wherein the (pn − 1)st entry ⎜ n

⎟ is divisible by p. This is the low vertex of an inverted p

−

⎝

⎠ n equilateral triangle of height p − 1 consisting of entries congruent to 0 (mod p). Further scrutiny reveals that they occur in other places as well throughout Pascal’s triangle. Each inverted triangle is uniquely determined by its apex at

⎛ 3 p n − 2 ⎞ ⎛ 3 p n − 1 ⎞ ⎛ 4 p n − 1⎞ ⎛ 4 p n − 1⎞ ⎛ 4 p n − 1⎞ ⎛ 5 p n − 1⎞ ⎛ 5 p n − 1 ⎞ ⎛ 5 p n − 1⎞ ⎛ 5 p n − 1 ⎞ ⎟,⎜ n

⎟,⎜ n

⎟;

⎜ n

⎟,⎜ n

⎟; ⎜ n

⎟,⎜ n

⎟; ⎜ n

−

− p p p p p p p p p

−

⎠ ⎝

⎠

⎝

⎠ ⎝

(n = 1, 2, 3,...), making up an intriguing, repetitive, fractal pattern that was discovered by the Polish mathematician Waclaw Sierpinski (1882-1969). The fractal homothety ratios are: p, p2, p3..., pn,... with center at the apex of Pascal’s triangle. It is important to realize that this is true for prime numbers only. It fails for composite numbers, e.g., there are odd numbers in row 6 other than entry 0 and 6 (mod 6), divisible by 6.

Sierpinski’s Triangle for Binomial Coefficients (mod 2)

Code: ○ ≡ 0, ● ≡ 1 (mod 2)

● ●●

●○●

●●●●

●○○○●

●●○○●●

●●●○●●●

●●●●●●●●

●○○○○○○○●

●●○○○○○○●●

●○●○○○○○●○●

●●●●○○○○●●●●

●○○○●○○○●○○○●

●●○○●●○○●●○○●●

●○●○●○●○●○●○●○●

●●●●●●●●●●●●●●●●

●○○○○○○○○○○○○○○○●

●●○○○○○○○○○○○○○○●●

●○●○○○○○○○○○○○○○●○●

●●●●○○○○○○○○○○○○●●●●

●○○○●○○○○○○○○○○○●○○○●

●●○○●●○○○○○○○○○○●●○○●●

●○●○●○●○○○○○○○○○●○●○●○●

●●●●●●●●○○○○○○○○●●●●●●●●

●○○○○○○○●○○○○○○○●○○○○○○○●

●●○○○○○○●●○○○○○○●●○○○○○○●●

●○●○○○○○●○●○○○○○●○●○○○○○●○●

●●●●○○○○●●●●○○○○●●●●○○○○●●●●

●○○○●○○○●○○○●○○○●○○○●○○○●○○○●

●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●

●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●

●○●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●○●

●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●

●○○○●○○○○○○○○○○○○○○○○○○○○○○○○○○○●○○○●

●●○○●●○○○○○○○○○○○○○○○○○○○○○○○○○○●●○○●●

●○●○●○●○○○○○○○○○○○○○○○○○○○○○○○○○●○●○●○●

●●●●●●●●○○○○○○○○○○○○○○○○○○○○○○○○●●●●●●●●

●○○○○○○○●○○○○○○○○○○○○○○○○○○○○○○○●○○○○○○○●

●●○○○○○○●●○○○○○○○○○○○○○○○○○○○○○○●●○○○○○○●●

●○●○○○○○●○●○○○○○○○○○○○○○○○○○○○○○●○●○○○○○●○●

●●●●○○○○●●●●○○○○○○○○○○○○○○○○○○○○●●●●○○○○●●●●

●○○○●○○○●○○○●○○○○○○○○○○○○○○○○○○○●○○○●○○○●○○○●

●●○○●●○○●●○○●●○○○○○○○○○○○○○○○○○○●●○○●●○○●●○○●●

●○●○●○●○●○●○●○●○○○○○○○○○○○○○○○○○●○●○●○●○●○●○●○●

●●●●●●●●●●●●●●●●○○○○○○○○○○○○○○○○●●●●●●●●●●●●●●●●

●○○○○○○○○○○○○○○○●○○○○○○○○○○○○○○○●○○○○○○○○○○○○○○○●

●●○○○○○○○○○○○○○○●●○○○○○○○○○○○○○○●●○○○○○○○○○○○○○○●●

●○●○○○○○○○○○○○○○●○●○○○○○○○○○○○○○●○●○○○○○○○○○○○○○●○●

●●●●○○○○○○○○○○○○●●●●○○○○○○○○○○○○●●●●○○○○○○○○○○○○●●●●

●○○○●○○○○○○○○○○○●○○○●○○○○○○○○○○○●○○○●○○○○○○○○○○○●○○○●

●●○○●●○○○○○○○○○○●●○○●●○○○○○○○○○○●●○○●●○○○○○○○○○○●●○○●●

●○●○●○●○○○○○○○○○●○●○●○●○○○○○○○○○●○●○●○●○○○○○○○○○●○●○●○●

●●●●●●●●○○○○○○○○●●●●●●●●○○○○○○○○●●●●●●●●○○○○○○○○●●●●●●●●

●○○○○○○○●○○○○○○○●○○○○○○○●○○○○○○○●○○○○○○○●○○○○○○○●○○○○○○○●

●●○○○○○○●●○○○○○○●●○○○○○○●●○○○○○○●●○○○○○○●●○○○○○○●●○○○○○○●●

●○●○○○○○●○●○○○○○●○●○○○○○●○●○○○○○●○●○○○○○●○●○○○○○●○●○○○○○●○●

●●●●○○○○●●●●○○○○●●●●○○○○●●●●○○○○●●●●○○○○●●●●○○○○●●●●○○○○●●●●

●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●○○○●

●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●○○●●

●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●○●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

. .

Sierpinski’s Triangle for Binomial Coefficients (mod 3)

Code: ○ ≡ 0, ● ≡ 1, ● ≡ 2 (mod 3)

● ●●

●●●

●○○●

●●○●●

●●●●●●

●○○●○○●

●●○●●○●●

●●●●●●●●●

●○○○○○○○○●

●●○○○○○○○●●

●●●○○○○○○●●●

●○○●○○○○○●○○●

●●○●●○○○○●●○●●

●●●●●●○○○●●●●●●

●○○●○○●○○●○○●○○●

●●○●●○●●○●●○●●○●●

●●●●●●●●●●●●●●●●●●

●○○○○○○○○●○○○○○○○○●

●●○○○○○○○●●○○○○○○○●●

●●●○○○○○○●●●○○○○○○●●●

●○○●○○○○○●○○●○○○○○●○○●

●●○●●○○○○●●○●●○○○○●●○●●

●●●●●●○○○●●●●●●○○○●●●●●●

●○○●○○●○○●○○●○○●○○●○○●○○●

●●○●●○●●○●●○●●○●●○●●○●●○●●

●●●●●●●●●●●●●●●●●●●●●●●●●●●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●●○○○○○○○○○○○○○○○○○○○○○○○○○○●●

●●●○○○○○○○○○○○○○○○○○○○○○○○○○●●●

●○○●○○○○○○○○○○○○○○○○○○○○○○○○●○○●

●●○●●○○○○○○○○○○○○○○○○○○○○○○○●●○●●

●●●●●●○○○○○○○○○○○○○○○○○○○○○○●●●●●●

●○○●○○●○○○○○○○○○○○○○○○○○○○○○●○○●○○●

●●○●●○●●○○○○○○○○○○○○○○○○○○○○●●○●●○●●

●●●●●●●●●○○○○○○○○○○○○○○○○○○○●●●●●●●●●

●○○○○○○○○●○○○○○○○○○○○○○○○○○○●○○○○○○○○●

●●○○○○○○○●●○○○○○○○○○○○○○○○○○●●○○○○○○○●●

●●●○○○○○○●●●○○○○○○○○○○○○○○○●●●○○○○○○●●●

●○○●○○○○○●○○●○○○○○○○○○○○○○○●○○●○○○○○●○○●

●●○●●○○○○●●○●●○○○○○○○○○○○○○●●○●●○○○○●●○●●

●●●●●●○○○●●●●●●○○○○○○○○○○○○●●●●●●○○○●●●●●●

●○○●○○●○○●○○●○○●○○○○○○○○○○○●○○●○○●○○●○○●○○●

●●○●●○●●○●●○●●○●●○○○○○○○○○○●●○●●○●●○●●○●●○●●

●●●●●●●●●●●●●●●●●●○○○○○○○○○●●●●●●●●●●●●●●●●●●

●○○○○○○○○●○○○○○○○○●○○○○○○○○●○○○○○○○○●○○○○○○○○●

●●○○○○○○○●●○○○○○○○●●○○○○○○○●●○○○○○○○●●○○○○○○○●●

●●●○○○○○○●●●○○○○○○●●●○○○○○○●●●○○○○○○●●●○○○○○○●●●

●○○●○○○○○●○○●○○○○○●○○●○○○○○●○○●○○○○○●○○●○○○○○●○○●

●●○●●○○○○●●○●●○○○○●●○●●○○○○●●○●●○○○○●●○●●○○○○●●○●●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sierpinski’s Triangle for Binomial Coefficients (mod 5)

Code:

○ ≡ 0, ● ≡ 1, ● ≡ 2, ● ≡ 3, ● ≡ 4 (mod 5)

● ●●

●●●

●●●●

●●●●●

●○○○○●

●●○○○●●

●●●○○●●●

●●●●○●●●●

●●●●●●●●●●

●○○○○●○○○○●

●●○○○●●○○○●●

●●●○○●●●○○●●●

●●●●○●●●●○●●●●

●●●●●●●●●●●●●●●

●○○○○●○○○○●○○○○●

●●○○○●●○○○●●○○○●●

●●●○○●●●○○●●●○○●●●

●●●●○●●●●○●●●●○●●●●

●●●●●●●●●●●●●●●●●●●●

●○○○○●○○○○●○○○○●○○○○●

●●○○○●●○○○●●○○○●●○○○●●

●●●○○●●●○○●●●○○●●●○○●●●

●●●●○●●●●○●●●●○●●●●○●●●●

●●●●●●●●●●●●●●●●●●●●●●●●●

●●○○○○○○○○○○○○○○○○○○○○○○●●

●●●○○○○○○○○○○○○○○○○○○○○○●●●

●●●●○○○○○○○○○○○○○○○○○○○○●●●●

●●●●●○○○○○○○○○○○○○○○○○○○●●●●●

●○○○○●○○○○○○○○○○○○○○○○○○●○○○○●

●●○○○●●○○○○○○○○○○○○○○○○○●●○○○●●

●●●○○●●●○○○○○○○○○○○○○○○○●●●○○●●●

●●●●○●●●●○○○○○○○○○○○○○○○●●●●○●●●●

●●●●●●●●●●○○○○○○○○○○○○○○●●●●●●●●●●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Binomial coefficients in Sierpinski’s triangle (mod 7)

Code: ○ ≡ 0, ● ≡ 1, ● ≡ 2, ● ≡ 3, ● ≡ 4, ● ≡ 5, ● ≡ 6 (mod 7)

● ●●

●●●

●●●●

●●●●●

●●●●●●

●●●●●●●

●○○○○○○●

●●○○○○○●●

●●●○○○○●●●

●●●●○○○●●●●

●●●●●○○●●●●●

●●●●●●○●●●●●●

●●●●●●●●●●●●●●

●○○○○○○●○○○○○○●

●●○○○○○●●○○○○○●●

●●●○○○○●●●○○○○●●●

●●●●○○○●●●●○○○●●●●

●●●●●○○●●●●●○○●●●●●

●●●●●●○●●●●●●○●●●●●●

●●●●●●●●●●●●●●●●●●●●●

●○○○○○○●○○○○○○●○○○○○○●

●●○○○○○●●○○○○○●●○○○○○●●

●●●○○○○●●●○○○○●●●○○○○●●●

●●●●○○○●●●●○○○●●●●○○○●●●●

●●●●●○○●●●●●○○●●●●●○○●●x●●

●●●●●●○●●●●●●○●●●●●●○●●●●●●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●

●○○○○○○●○○○○○○●○○○○○○●○○○○○○●

●●○○○○○●●○○○○○●●○○○○○●●○○○○○●●

●●●○○○○●●●○○○○●●●○○○○●●●○○○○●●●

●●●●○○○●●●●○○○●●●●○○○●●●●○○○●●●●

●●●●●○○●●●●●○○●●●●●○○●●●●●○○●●●●●

●●●●●●○●●●●●●○●●●●●●○●●●●●●○●●●●●●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

●○○○○○○●○○○○○○●○○○○○○●○○○○○○●○○○○○○●

●●○○○○○●●○○○○○●●○○○○○●●○○○○○●●○○○○○●●

●●●○○○○●●●○○○○●●●○○○○●●●○○○○●●●○○○○●●●

●●●●○○○●●●●○○○●●●●○○○●●●●○○○●●●●○○○●●●●

●●●●●○○●●●●●○○●●●●●○○●●●●●○○●●●●●○○●●●●●

●●●●●●○●●●●●●○●●●●●●○●●●●●●○●●●●●●○●●●●●●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

●○○○○○○●○○○○○○●○○○○○○●○○○○○○●○○○○○○●○○○○○○●

●●○○○○○●●○○○○○●●○○○○○●●○○○○○●●○○○○○●●○○○○○●●

●●●○○○○●●●○○○○●●●○○○○●●●○○○○●●●○○○○●●●○○○○●●●

●●●●○○○●●●●○○○●●●●○○○●●●●○○○●●●●○○○●●●●○○○●●●●

●●●●●○○●●●●●○○●●●●●○○●●●●●○○●●●●●○○●●●●●○○●●●●●

●●●●●●○●●●●●●○●●●●●●○●●●●●●○●●●●●●○●●●●●●○●●●●●●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●

●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●

●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●

●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●

●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●

●●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●●

●●●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●●●

●○○○○○○●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●○○○○○○●

●●○○○○○●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●○○○○○●●

●●●○○○○●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●○○○○●●●

●●●●○○○●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●○○○●●●●

●●●●●○○●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●○○●●●●●

●●●●●●○●●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●●○●●●●●●

●●●●●●●●●●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●●●●●●●●●●

●○○○○○○●○○○○○○●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●○○○○○○●○○○○○○●

●●○○○○○●●○○○○○●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●○○○○○●●○○○○○●●

●●●○○○○●●●○○○○●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●○○○○●●●○○○○●●●

●●●●○○○●●●●○○○●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●○○○●●●●○○○●●●●

●●●●●○○●●●●●○○●●●●●○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○●●●●●○○●●●●●○○●●●●●

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

The Generalized Little Fermat Theorem

The Little Fermat Theorem states that a p ≡ a (mod p) where p is prime. If, in addition, p does not divide a then by the Cancellation Law we also have a p −1 ≡ 1 (mod p). The proof is by mathematical induction. For a = 2 there is a proof without words. Behold Sierpinski’s triangle (mod p) and see that there are only two non-zero dummies in row p, the first and the last, each equal to 1. On the other hand, by the Summation Formula, the sum of entries in the pth row is 2 p . We conclude that 2 p ≡ 2 (mod p).

To extend this to a we need the mod p version of the Binomial Formula: ( a + b) p ≡ a p + b p

(mod p) that can also be proved without words, just by beholding Sierpinski’s triangle. Now we can start the induction: 3 p = (2 + 1) p ≡ 2 p + 1 ≡ 2 + 1 = 3 (mod p); 4 p = (3 + 1) p ≡ 3 p + 1 ≡ 3 + 1 = 4 (mod p); etc., and the result follows. n

This is just a special case, for n = 1, of a more general result: a p −1 ≡ 1 (mod p), n = 1, 2, 3, … The proof of the full strength of the Little Fermat Theorem is left as an exercise. There are many other proofs of the type “behold!” They are all relegated to the Exercises.

Newton’s First and Second Formula

It is curious that authors, among them pioneers such as the American mathematician Eric Temple Bell, were blind to the fact that the Binomial Theorem is valid not only for numbers but operators as well.

Their blindness might have been due to a notational stumbling block: they had thought that they were obliged to invent a new symbol (e.g., I or ι) for the identity operator, bypassing the obvious choice of 1. In this treatise we shall be concerned with several operators that apply to sequences, some of which we introduce right now. The shift operator E is defined such that for every sequence an we have Ean = an+1 (E ‘shifts’ the members of the sequence by one slot to the right). The powers of the shift operator E2, E 3,... called higher order shift operators will also be used. They make a right shift by 2, 3,... slots. The difference operator Δ is defined such that Δan = an+1 − an , and the identity operator 1 such that 1an = an for every sequence an. The fact that 1 has another meaning also, that of the number one, is not disturbing. The powers of Δ: Δ2, Δ3,... are called higher order difference operators. For example it is easy to show that, for the geometric progression an = 2n, we have Δk2n = 2n for k = 1, 2, 3,...

Indeed, Δ2n = 2n+1 − 2n = 2n(2 −1) = 2n (for this reason the sequence 2n plays the same role with respect to the difference operator Δ as the exponential function ex does with respect to the differential operator d/dx). One can also consider the inverse shift operator E–1 defined by the formula E–1(an) = an – 1 where an is a sequence with values for n = ...−2, −1, 0, 1, 2,... It satisfies E–1E = 1 = EE–1, where 1 is the identity operator.

The next two results are not usually treated in the context of the Binomial Theorem, even though that is where they properly belong. Correctly understood, they are not a formula but an algorithm.

Newton’s first formula

⎛n⎞

E n = 1 + ⎜ ⎟ Δ + ⎜ ⎟ Δ 2 + ... + ⎜ ⎟ Δ n

⎝1⎠

⎝ 2⎠

⎝n⎠

Newton’s second formula

⎛n⎞

Δ n = E n − ⎜ ⎟ E n −1 + ⎜ ⎟ E n −2 − +... + ( −1)n ⎜ ⎟

⎝1⎠

⎝ 2⎠

⎝n⎠

For example we calculate Ek2n via Newton’s first formula (even though manual calculation is

⎛k ⎞

⎛k ⎞ ⎛k ⎞ quicker). Ek 2n = (1 + Δ)k2n = [1 + ⎜ ⎟ Δ + ⎜ ⎟ Δ2 + ... + ⎜ ⎟ Δk] 20.2n = [1 + ⎜ ⎟ + ⎜ ⎟ + ... + ⎜ ⎟ ] ⎝k ⎠

⎝k ⎠

⎝1⎠

⎝ 2⎠

⎝1⎠ ⎝ 2⎠ n

2 =

(1 + 1)k2n = 2n+k . As another example, we re-calculate Δk2n via Newton’s second:

⎛k ⎞

Δk2n = (E − 1)k 2n = [Ek − ⎜ ⎟ Ek-1 + − ... + (−1)k ⎜ ⎟ ] 20.2n = [2k − ⎜ ⎟ 2k-1 + − ... + (−1)k] 2n = ⎝1⎠

⎝1⎠

⎝k ⎠ k n n

(2 −1) 2 = 2 for k = 1, 2, 3,...

Newton’s formulas can be proved by observing that E = 1 + Δ, Δ = E − 1 and expanding

(1 + Δ)n, (E − 1)n via the binomial formula under the convention that Δ0 = E0 = 1, the identity operator. We can calculate the nth term of an arbitrary sequence via Newton’s first. For example, let us continue the entries in the slanting row a0 = 1, 4, 10, 20, 35,..., an,... of Pascal’s triangle and calculate 7th term. The higher differences are:

35 . . .

15 . . .

5...

1...

The third difference sequence is constant, so the fourth and each subsequent higher difference is the zero sequence. Hence in Newton’s first formula we have to write the first four terms only: a7 = E7a0 = (1 + 7Δ + 21Δ2 + 35Δ3)a0 = 1 + 7(3) + 21(3) + 35(1) = 120. To check, we continue the sequence an manually using the fact that Δ3an = 1 is constant. The sums 6 + 1 = 7, 21 + 7 = 28, 56 + 29 = 84 = a6 we enter in the 6th slanting row of slope +1, and continue to a7 :

120 . . .

36 . . .

8...

1...

Ours is an example of an arithmetic progression of order 3. More generally, members of a sequence ak are said to be in arithmetic progression of order n if the nth difference sequence is constant ≠ 0 (hence, all higher difference sequences are equal to the zero sequence). An ordinary arithmetic progression is of the first order. Pascal’s triangle furnishes an example of an nth order arithmetic progressions for every n, namely, entries in the nth slanting row. Furthermore, earlier slanting rows are exactly the higher order difference sequences, revealing that the nth difference sequence is constant equal to 1. In fact, Pascal’s triangle can be used as a ‘ready reckoner’ for the higher differences of binomial coefficients standing in a slanting row. They are the binomial coefficients standing in earlier slanting rows. In fact, rotation of Pascal’s triangle in the counter-clockwise sense through 135° will put these rows in the customary horizontal position. A most important arithmetic progressions of order n is the sequence of the nth powers: 0n, 1n, 2n, 3n,...,kn,... The nth difference sequence is constant and is equal to n!

It is not hard to prove the theorem that members of a sequence ak are in arithmetic progression of order n if, and only if, ak is a polynomial of degree n in the variable k.

As an application of Newton’s formulas we shall prove the following

Theorem. The solution of the system of linear equations with infinitely many unknowns x0, x1, x2,... 1x0 = y0

1x0 + 1x1 = y1

1x0 + 2x1 + 1x2 = y2

1x0 + 3x1 + 3x2 + 1x3 = y3

. . . . . where on the left-hand side we have the binomial coefficients, and constants, is: x0 = 1y0 y0, y1, y2,... are arbitrary x1 = −1y0 + 1y1 x2 = 1y0 − 2y1 + 1y2 x3 = −1y0 + 3y1 − 3y2 + 1y3

. . . . . where on the right-hand sides we have the binomial coefficients with alternating signature.

Proof. By Newton’s first we may write the proposed solution in the form: xn

= En x0 = (E − 1)n y0

⇒ En x0 = Δn y0 for n = 0, 1, 2, 3, ... Therefore

⎛n⎞

⎛ n ⎞

⎛n⎞

(E + 1)n x0 = En x0 + ⎜ ⎟ E n - 1x0 + ... + ⎜

E x0 + ⎜ ⎟ x 0

⎟

⎝1⎠

⎝n⎠

⎝ n − 1⎠

⎛n⎞

⎛ n ⎞

⎛n⎞

Δy0 + ⎜ ⎟ y0

= Δn y0 + ⎜ ⎟ Δn - 1 y0 + ... + ⎜

⎟

⎝1⎠

⎝n⎠

⎝ n − 1⎠ n

= (Δ + 1) y0

= En y0 = yn by Newton’s second.

It follows that the values xn = (E − 1)n y0 satisfy the system, completing the proof.

The converse is also true: if the roles of the unknowns and constants are interchanged, then solution to the second system for the unknowns yk is furnished in terms of the constants xk by the first. As an example, consider the system of linear equations with infinitely many unknowns

1x1 = 0n

1x1 + 1x2 = 1n

1x1 + 2x2 + 1x3 = 2n

1x1 + 3x2 + 3x3 + 1x4 = 3n

. . . . . . . . . .

The solution is: x1 = 1(0n) x2 = 1(1n) − 1(0n) x3 = 1(2n) − 2(1n) + 1(0n) x4 = 1(3n) − 3(2n) + 3(1n) − 1(0n)

. . . . . . . . .

In order to interpret this result we note that 0n, 1n, 2n, 3n,... are in arithmetic progression of order n and Newton’s second formula applies:

⎛k ⎞

Δk0n = (E − 1)k0n = [Ek − ⎜ ⎟ Ek-1 + ⎜ ⎟ Ek-2 − + ... + (−1)k ⎜ ⎟ ] 0n

⎝1⎠

⎝2⎠

⎝k ⎠

We conclude that the solution to the above infinite system of linear equations is:

⎛k ⎞

⎛ k ⎞ n xk = Δk0n = kn − ⎜ ⎟ (k − 1)n + ⎜ ⎟ (k − 2)n − + ... + (−1)k-1 ⎜

⎟1

⎝1⎠

⎝ 2⎠

⎝ k − 1⎠

The numbers Δk0n have an important (albeit little recognized) interpretation:

Implicit formula for the number of surjective functions

Surj(n, k) = Δk0n where Surj(n, k) stands for the number of surjective functions from an n-set to a k-set (alternatively, the number of distributions of n unlike balls into k unlike cells with no cell to remain empty). Again, this is not so much a formula than an algorithm. (The properties of injective, surjective, and bijective functions will be discussed in Volume II, Chapter 15 on duality.)

For example, let n = 3 and calculate Surj(3, 2). Δ243 = (E − 1)2 43 = (E2 − 2E + 1) 43 =

E243 − 2E43 + 43 = 63 − 2(53) + 43 = 216 − 2(125) + 64 = 280 − 250 = 30 = Surj(3, 2). To check, we may calculate the higher order difference sequences of the cubes manually. Note that we can calculate the consecutive cubes (and, for that matter, the consecutive nth powers, for any n) using addition only, to the exclusion of subtraction and multiplication. Starting with the cubes 03 = 0, 1, 8, 27 and their differences

0 1

8 27

1 7 19

6 12

6 ... we enter the sums 12 + 6 = 18, 19 + 18 = 37, 27 + 37 = 64 = 43 in the 4th slanting row with slope +1 (counting starts with slanting row 0). Similarly, in the next slanting row we enter the sums 18 + 6 = 24, 37 + 24 = 61, 64 + 61 = 125 = 53, etc. We get:

216 . . . n3 . . .

91 . . .

30 . . .

6 ...

Thus we can find Δ243 = 30 in row 2, entry 4 (counting starts with row 0, entry 0).

As another example let us calculate Surj(6, 3). We only need the sixth powers 0, 1, 64, 729:

Surj(6, 3) = 729 − 3(64) + 3 = 732 − 192 = 540. To check, we may calculate the sixth powers using addition only (just as we did in calculating the cubes above):

4096 15625 46656 117649 . . . k6 . . .

3367 11529 31031 70993 . . .

602 2702 8162 19502 39962 . . .

540 2100 5460 11340 20460 . . .

1560 3360 5880 9120 . . .

1800 2520 3240 . . .

720 720 . . .

From the slanting row printed in red we also see that Surj(6, 2) = Δ206 = 62; Surj(6, 4) = Δ406 = 1560; Surj(6, 5) = Δ506 = 1800; Surj(6, 6) = Δ606 = 720 = 6! We also have the

Explicit formula for the number of surjective functions

⎛k ⎞

⎛ k ⎞ n

Surj(n, k) = kn − ⎜ ⎟ (k − 1)n + ⎜ ⎟ (k − 2)n − + ... + (−1)k-1 ⎜

⎟1

⎝1⎠

⎝ 2⎠

⎝ k − 1⎠

Clearly, Surj(n, 0) = 0. We also have Surj(n, 1) = 1 for n ≥ 1 because, in this case, there is only one function (the constant function). Recall that the number of all functions from an n-set to a k-set is kn. We may survey them according to the number k of elements in the image, to find that

⎛k ⎞

⎛ k ⎞

⎛k ⎞

⎛k ⎞ n

⎜ k ⎟ Surj(n, k) + ⎜ k − 1⎟ Surj(n, k −1) +. . . + ⎜ 1 ⎟ Surj(n, 1) + ⎜ 0 ⎟ Surj(n, 0) = k

⎝ ⎠

⎝

⎠

⎝ ⎠

This pleasantly transparent formula can be checked through direct counting:

1 Surj(n, 1) = 1n

1 Surj(n, 2) + 2 Surj(n, 1) = 2n

1 Surj(n, 3) + 3 Surj(n, 2) + 3 Surj(n, 1) = 3n

1 Surj(n, 4) + 4 Surj(n, 3) + 6 Surj(n, 2) + 4 Surj(n, 1) = 4n

. . . . . . . . . .

For example, if n = 3, we have 1(6) + 3(6) + 3(1) + 1(0) = 27 = 33.

As an example, let n = 5 and find Surj(5, 3). We only need the fifth powers 0, 1, 32, 243.

Surj(5,3) = 243 − 3(32) + 3 = 246 − 96 = 150. We also have Surj(5, 2) = 32 − 2(1) = 30. Let us continue the calculation of the fifth powers beyond 243 = 35:

1024 3125 7776 . . . k5 . . .

2101 4651 . . .

180 570

1320 2550 . . .

150 390

1230 . . .

240 360

480 . . .

...

From the slanting row printed in red we find that Surj(5, 4) = Δ405 = 240, and Surj(5, 5) = Δ505 =

120 = 5!.

It is important to note that the pattern exhibited by the Sierpinski’s triangles is a consequence of Newton’s formulas and of the fact that the slanting rows of Pascal’s triangle are in arithmetic progression (see Exercises).

In Chapter 6 we shall see the dual of Newton’s First and Second Formulas under the name

Vertical and Horizontal Exchange Formulas. They are dual in the same sense as the lattice of quotient sets is dual to the lattice of subsets. In passing we draw attention to the fact that the Theorem above on the solution of the infinite system of linear equations with the binomial coefficients as coefficients can be formulated as follows. The solution of the matrix equation

⎛1

⎜1

⎜

⎜1

⎜

⎜1

⎜.

⎝

. ⎞ ⎛ x1 ⎞ ⎛ y1 ⎞

. ⎟⎟ ⎜⎜ x2 ⎟⎟ ⎜⎜ y2 ⎟⎟

. ⎟ ⎜ x3 ⎟ = ⎜ y3 ⎟

⎟⎜ ⎟ ⎜ ⎟

. ⎟ ⎜ x4 ⎟ ⎜ y 4 ⎟

. ⎟⎠ ⎜⎝ . ⎟⎠ ⎜⎝ . ⎟⎠ can be obtained by the formula

⎛ x1 ⎞ ⎛ 1 0 0

⎜ x ⎟ ⎜ −1 1 0

⎜ 2⎟ ⎜

⎜ x3 ⎟ = ⎜ 1 −2 1

⎜ ⎟ ⎜

⎜ x 4 ⎟ ⎜ − 1 3 −3

⎜ . ⎟ ⎜ .

⎝ ⎠ ⎝

. ⎞ ⎛ y1 ⎞

. ⎟⎟ ⎜⎜ y2 ⎟⎟

. ⎟ ⎜ y3 ⎟

⎟⎜ ⎟

. ⎟ ⎜ y4 ⎟

. ⎟⎠ ⎜⎝ . ⎟⎠ where in the first infinite square matrix we have the binomial coefficients, in the second, the binomial coefficients with alternating signature. In other words, the product of the infinite square matrices ⎛1 0 0

⎜ −1 1 0

⎜

⎜ 1 −2 1

⎜

⎜ −1 3 −3

⎜ .

⎝

. ⎞ ⎛1

. ⎟⎟ ⎜⎜ 1

. ⎟ ⎜1

⎟⎜

. ⎟ ⎜1

. ⎟⎠ ⎜⎝ .

. is the unit square matrix.

.⎞ ⎛ 1

. ⎟⎟ ⎜⎜ 0

.⎟ = ⎜ 0

⎟ ⎜

.⎟ ⎜ 0

. ⎟⎠ ⎜⎝ .

.⎞

. ⎟⎟

.⎟

⎟

.⎟

. ⎟⎠

Exercises

Calculate Surj(7, 5) in three different ways.

Calculate the seventh powers of integers up to 107 using addition only.

In how many different ways can we distribute eight unlike balls into five unlike cells in such a way that no cell shall remain empty?

In how many ways can we have a street of ten houses painted with two, three, four, five, six, seven, eight, nine, ten given colors in such a way that, in each case, every color is represented?

Show, in at least two different ways, that Surj(n, n) = n!

For which values of k does the equality Surj(n, k) = 0 hold?

⎛n⎞

Prove n n − ⎜ ⎟ ( n − 1)n + ⎜ ⎟ ( n − 2) n − +... + ( −1) n −1 ⎜ ⎟ 1n = n ! in at least two different ways. ⎝1⎠

⎝2⎠

⎝n⎠

⎛k ⎞

For which values of k is the formula kn − ⎜ ⎟ (k −1)n + ⎜ ⎟ (k −2)n − + ... = 0 valid?

⎝1⎠

⎝2⎠

Prove the Binomial Theorem in at least three different ways.

Show that the entries in the nth slanting row with slope ±1 of Pascal’s triangle are in arithmetic progression of order k. Find k in terms of n. Calculate the kth difference sequence.

Show that the binomial coefficients in row p of Pascal’s triangle, with the exception of the first and last, are divisible by p provided that p is a prime number.

Prove the formula (1 + 2 + 22 + ... + 2n) + 1 = 2n+1 in at least two different ways.

Prove that the numbers ak are in arithmetic progression of order n if, and only if, the function

A(k) = ak is a polynomial of degree n in the variable k.

Construct the first 40 rows of the Sierpinski triangle (mod 7) for the binomial coefficients.

Prove the Summation Formula for binomial coefficients in at least two different ways.

Prove the following version of the Binomial Theorem: for p prime, n = 1, 2, 3,…, n n n

( a + b) p ≡ a p + b p (mod p)

Prove the Little Fermat Theorem stating that a p −1 ≡ 1 (mod p), provided that p is a prime number that does not divide a, in at least three different ways.

Prove the Generalized Little Fermat Theorem stating that for a prime number p that n doesn’t divide a, a p −1 ≡ 1 (mod p), for n = 1, 2, 3,…

Show that the binomial coefficients in row pn of Pascal’s triangle, with the exception of the first and the last, are divisible by p provided that p is a prime number and n = 1, 2, 3,...

Are the previous statements true of false for composite numbers? If false, provide counter examples.

(a) Show that in an arithmetic progression of order k, if a member an is divisible by the prime number p, then so is an + p.

(b) What can you say about an + 2p, an + 3p, an + 4p,... under the same assumption?

Let a1, a2, a3,..., an ,... be an arithmetic progression of order k. Suppose that an = p < k is an odd prime number. Show that Δpan + 1 ≡ 0 (mod p).

(a) Show that Surj(p, k) is divisible by p, provided that p is a prime number and k > 1.

(b) Investigate the validity of the above statement for Surj(pn, k), n = 1, 2, 3,... n

Show that 2 p −1 ≡ 1 (mod p) where p is a prime number, for n = 1, 2, 3,.... Is this statement valid for a composite number?

Prove the Theorem on the solution of the system of linear equations with infinitely many unknowns in another way: express x1, x2, x3,… from the 1st, 2nd, 3rd,… equation, substituting these values into subsequent equations.

Solve numerically the system of linear equations with infinitely many unknowns, and check:

(a)

1x1 = 0

1x1 + 1x2 = 1

1x1 + 2x2 + 1x3 = 2

1x1 + 3x2 + 3x3 + 1x4 = 3

. . . . . . . . . .

(b)

1x1 = 1

1x1 − 1x2 = 1

1x1 − 2x2 + 1x3 = 1

1x1 − 3x2 + 3x3 − 1x4 = 1

. . . . . . . . . .

(c)

1x1 = 0

1x1 + 1x2 = 1

1x1 + 2x2 + 1x3 = 4

1x1 + 3x2 + 3x3 + 1x4 = 9

. . . . . . . . . . where on the right-hand side we have the square numbers.

(d)

1x1 = 0

1x1 + 1x2 = 1

1x1 + 2x2 + 1x3 = 8

1x1 + 3x2 + 3x3 + 1x4 = 27

. . . . . . . . . . where on the right-hand side we have the cubes.

(e)

1x1 = 1

1x1 + 1x2 = 10

1x1 + 2x2 + 1x3 = 100

1x1 + 3x2 + 3x3 + 1x4 = 1000

. . . . . . . . . . where on the right-hand side we have the powers of 10.

1x1 = y1

1x1 − 1x2 = y2

1x1 − 2x2 + 1x3 = y3

1x1 − 3x2 + 3x3 − 1x4 = y4

. . . . . . . . . .

(f) where on the left-hand side we have the binomial coefficients with alternating signature, and y1, y2, y3, … are arbitrary constants.

Calculate (mod p) where p is prime, the following sums:

⎛ k + p − 1⎞

∑0 ⎜ p − 1 ⎟ ,

⎝

⎠

⎛ p +k⎞

∑0 ⎜ p ⎟ ,

⎝

⎠ n n

(a)

(b)

⎛ k + p − 1⎞

⎟. k

0 ⎝

⎠ n

(d)

∑⎜

(c) n

⎛ p +k⎞

⎝

∑⎜ k ⎟ ,

⎠

Solve the matrix equation

⎛1

⎜1

⎜

⎜1

⎜

⎜1

⎜.

⎝

. ⎞ ⎛ x1 ⎞ ⎛ 1 ⎞

. ⎟⎟ ⎜⎜ x2 ⎟⎟ ⎜⎜ 2 ⎟⎟

. ⎟ ⎜ x3 ⎟ = ⎜ 3 ⎟

⎟⎜ ⎟ ⎜ ⎟

. ⎟ ⎜ x4 ⎟ ⎜ 4 ⎟

. ⎟⎠ ⎜⎝ . ⎟⎠ ⎜⎝ . ⎟⎠ where the entries in the infinite square matrix are the binomial coefficients. Write the matrix equation as a system of linear equations with infinitely many unknowns, and check your solution by substitution.

Complete the coloring of Sierpinski’s triangles on p 23, 24.