Stepnumbers: Chapter 4 — The Stepnumber System and the Spectral Coefficients

4. The stepnumber system and the spectral coefficients

The stepnumber system, in contrast with the binary, epitomizes form as opposed to substance. We refer to the table of the first three hundred stepnumbers in the Introduction. Just as in the case of Cantor numbers, an n-digit stepnumber may involve only digits up to and including n. But in contrast with Cantor’s, for a stepnumber no digit larger than k may enter the kth slot (counted from left to right). In solving the practical problem of creating infinitely many digits one must rely on mnemonic principles. Digits must be such that the human (as well as computer) memory be able to recognize, store and retrieve them as needed. In Chapter 1 we have solved the problem of creating infinitely many digits, the so-called rainbow digits. Here we shall work with examples for the representation of which the color black and the ten decimal digits suffice. We have the Bell numbers bn so named after the American mathematician Eric Temple Bell who was one of the pioneers studying them

(however, see Dobinski’s 1877 paper [5]):

1 = 1 = 100 = b1

10 = 2 = 101 = b2

100 = 5 = 102 = b3

1000 = 15 = 103 = b4

10000 = 52 = 104 = b5

100000 = 203 = 105 = b6

1000000 = 877 = 106 = b7

10000000 = 4,140 = 107 = b8

100000000 = 21,147 = 108 = b9

1000000000 = 115,975 = 109 = b10

10000000000 = 678,570 = 1010 = b11

100000000000 = 4,213,597 = 1011 = b12

1000000000000 = 27,644,437 = 1012 = b13

. . . . .

A table containing the values of the Bell numbers up to b100 is appended at the end of the book. We shall see numerous different methods to calculate the Bell numbers, five of them later in this Chapter.

The Bell number bn+1 counts the number of stepnumbers of at most n digits. This can be seen from the fact that 10n is the very first stepnumber of n + 1 digits as it succeeds n!, the last n-digit stepnumber. Stepnumbers up to and including n! have at most n digits. Often it is desirable to treat this set as if its members had the same number of digits. This can, of course, be accomplished by attaching one or more 0 digits as needed in front without affecting the values of stepnumbers, while causing them to have the same n + 1 number of digits (the first of which being 0). For example, in the case of n = 3, 103 = b4 = 15, meaning that there are 15 stepnumbers of at most 3 digits. We can convert them uniformly into 4-digit stepnumbers thus:

0 = 0000, 1 = 0001, 10 = 0010, 11 = 0011, 12 = 0012, 100 = 0100, 101 = 0101, 102 = 0102,

110 = 0110, 111 = 0111, 112 = 0112, 120 = 0120, 121 = 0121, 122 = 0122, 123 = 0123

We shall call this the up-front-0 representation, to distinguish it from the conventional up-front-1 representation of stepnumbers. Unless stipulated otherwise we use the latter.

The Bell numbers bn = 10n−1 are pure stepnumbers. More generally we define a pure stepnumber of n digits as one of the form k!0n − k = 123...k0n − k . Next we introduce the important concept of a block of consecutive stepnumbers. They turn out, in the true sense of the word, to be the building blocks of the stepnumber system. Given n and 1 ≤ k ≤ n, the kth block of n-digit stepnumbers consists of those from k!0n − k through n! inclusive.

Thus, for a fixed n, block 0 contains all stepnumbers of at most n digits from 0 through n!

The remaining blocks consist of stepnumbers of exactly n digits. Block 1 contains those from 10n−1 through n!, block 2 contains those from 120n − 2 through n!,..., block k contains those from

123...k0n − k through n!,..., block n − 1 contains those from 123...(n - 1)0 through n! The last, block n, has a single element: n! It is apparent that there are n + 1 blocks of n-digit stepnumbers, one for each value of k = 0, 1, 2,..., n. These blocks are in fact ‘nested sets’, that is to say, each block contains every subsequent block, and all of them contain the last one, block n, having a single element, 123...n. For example, for n = 4, the 5 blocks are as follows: block 0: {0,1,..., 1234} containing 52 stepnumbers; block 1:{1000, 1001,..., 1234} containing 37 stepnumbers; block 3: {1200, 1201, 1202,..., 1234} containing 17 stepnumbers; block 4: {1230, 1231, 1232, 1233, 1234}; finally, block 5: {1234}.

Block k of the n-digit stepnumbers is completely characterized by its first member, which will be used in naming it. A stepnumber belongs to the block of k!0n-k if, and only if, it is of the form 123...kxy...z (the dummy digits x, y, ... , z can independently run through all admissible values). Thus we have a one-to-one correspondence between blocks and pure stepnumbers which, to each block, assigns its first element.

We now introduce the concept of a spectral coefficient as the length of a block. We arrange spectral coefficients in Pascal’s triangle for easy inspection. Our key result below is the Blockbuster Formula which shows how to calculate a spectral-coefficient from those in the previous row of Pascal’s triangle. The justification for the terminology ‘blockbuster’ is the fact that this formula reveals how the block of stepnumbers between the first occurrence of stepdigits n and n +1 splits n into smaller blocks by further occurrences of n. In more details, let 0 ≤ k ≤ n. The symbol , called k spectral coefficient, denotes the number of stepnumbers from 123...k0n −k to 123...n, inclusive, that is, the length of the block of k!0n – k . We have: n

= 10n − 123...k0n – k k

In particular, n

= 10n = bn+1 are the Bell numbers counting the stepnumbers of at most n digits; n

= 10n − 10n −1 = bn+1 − bn counting the stepnumbers of exactly n digits. In other words, it shows how far forward we have to count from (n – 1)! to get to n! We also have: n

= n+1 n −1 because there are n+1stepnumbers from (n − 1)!0 to n!, namely, (n − 1)!0, (n − 1)!1, (n − 1)!2,..., (n − 1)!n = n! Finally, n

= 1 n because the last block has only one element, n! By convention,

= 1.

Recursion Formula n +1 n +1 n

−

= ( k + 1) k k +1 k

It can be used to calculate the spectral coefficients, see Exercises. Through repeated application we get: n +1 n +1 n n n n

−

= ( k + 1) + ( k + 2)

+ ( k + 3)

+ ... + ( k + j ) k k+ j k k +1 k+2 k + j −1

This for j = n − k + 1 leads to the

Blockbuster Formula for the spectral coefficients n +1 n n n n

= ( k + 1) + ( k + 2)

+ ( k + 3)

+ ... + ( n + 1) + 1 k k k +1 k +2 n

An important special case is that of k = 0:

Overflow Formula bn + 2 = 1 n

+2 n

+3 n

+ ... + ( n + 1) n

+1 n

Example. (Compare this with the survey of occurrences of the digit 0 among the stepnumbers from 0 through 1! in Chapter 1, p 14-15. In following this example, refer to the Table of Stepnumbers, p 5.)

We want to see how the first appearance and further occurrences of a new digit, 4, splits the block of 203 stepnumbers of at most 5 digits from 0 to 12345. The first occurrence is in 1234. From there we may count forward

= 104 – 103 = 52 −15 = 37 stepnumbers without encountering 4 again to 10234, the second occurrence of 4. From there we may count forward another 37 stepdigits without encountering 4 to 11234, the third occurrence of 4. From there we can count forward

= 104 − 1200 = 52 − 35 = 17 stepnumbers three times to 12034, 12134, 12234, that is, the 4th, 5th and 6th occurrence of 4. The 7th occurrence of 4 is only 5 stepdigits away at 12304. Indeed,

= 104 − 1230 = 52 − 47 = 5. The 8th, 9th and 10th occurrence of 4 follows at the same interval of length 5 to get to 12314, 12324, 12334. Thereafter 5 consecutive stepnumbers contain 4, namely 12340, 12341, 12342, 12343, 12344 showing that

= 104 − 1234 = 52 − 51 = 1. By way of checking we write:

• 2 + 3 + 4 + 5 = 52 + 2(37) + 3(17) + 4(5) + 5(1) = 202 = b6 − 1 .

The Overflow Formula earns its name by having the same content as n! + 1 = 10n = bn+1, as we shall see in Chapter 7 on the conversion of stepnumbers into decimals. This version lets us calculate the Bell numbers from the spectral coefficients, e.g., b5 = 1(15) + 2(10) + 3(4) + 4(1) + 1 = 52

The Recursion Formula is a difference equation which under the

Initial Condition n n

=1 yields a unique solution that can be presented in a format due to Pascal, with place of the n th row (counting rows and places starts with 0).

Spectral coefficients in Pascal’s triangle n standing at the kth k

203 151 77

877 674 372 141

4140 3263 1915 799 235 50

21147 17007 10481 4736 1540 365

115975 94828 60814 29371 10427 2727 537

678570 562595 372939 190497 73013 20878 4516 757 101

4213597 3535027 2409837 1291020 529032 163967 38699 7087 1031 122 12

. . . . . . . .

In Chapter 1 we have surveyed those stepnumbers which had exactly one red digit, 0. The length of blocks in that sequence correspond to the entries in row 10 (counting starts with 0) of Pascal’s triangle above. In fact, Pascal’s triangle gives the length of blocks indicating the frequency of every new digit. In the Example on the previous page, the length of blocks come from row 3.

The Recursion Formula can be verbalized as follows. The difference between any two adjacent entries in Pascal’s triangle is divisible by their neighboring entry in the previous row; moreover the complementary divisor is just the ordinal of the slanting row with slope +1 to which the larger belongs. For example, 77 and 26 are adjacent entries and their neighbor in the previous row is 17 and 77 − 26 = 51 = 3(17). Indeed, 77 is in the slanting row of ordinal 3. It is remarkable and important that entries in the slanting rows of slope −1 are in arithmetic progression of higher order (see Exercises).

In order to describe blocks in yet another way, we classify the digits of a stepnumber as either a stepdigit or a standstill digit. A digit is called a stepdigit if its left neighbor is exactly one higher than the highest digit that has previously occurred. Otherwise the digit is called a standstill digit.

Thus the immediate predecessor of a stepdigit surpasses all the digits standing to its left. By contrast, the left neighbor of a standstill digit is repeating a digit that has already occurred. For example, every digit of n! is a step-digit; all the digits of 10n , apart from the first two, are standstill, as are the digits of 1n . All the digits of the stepnumbers 1x, 12x, 123x, ... are step-digits (x stands for any admissible n counts the number of stepnumbers of exactly n digits of which at least dummy digit). For k ≥ 1, k the first k + 1 are step-digits.

Notice the ‘look-back’ feature of the concept: in finding out whether d is a stepdigit or a standstill digit we must look at the preceding digits to the left. It is not d per se that decides the issue.

For example, 0 is a stepdigit and 4 a standstill digit in 123045; the first 3 is a step-digit and the second is a standstill digit in 123123. The two leading digits (in up-front-0 representation, the three leading digits) of a stepnumber are invariably step-digits. The first k + 1 digits are stepdigits if, and only if, the n-digit stepnumber is of the form 123...kx...y (where x, ... , y are n − k admissible dummy digits).

Here is the proof of the Recursion Formula. For k = 0 the relation is obvious. Let k ≥ 1, the difference of two consecutive pure stepnumbers of n digits,

(k + 1)!0n−k−1 − k!0n-k = n +1 n +1

− k k +1 is the same as the number of stepnumbers of exactly n + 1 digits of which the first k + 1 are stepdigits and the rest standstill digits. In other words, the difference of two adjacent spectral coefficients in the same row of Pascal’s triangle is the same as the number of stepnumbers of the form 123...kx...x where all the dummy digits with the exception of the first are standstill. For example,

1230 − 1200 =

4 4

− = 17 − 5 = 12

2 3 is the number of stepnumbers of 4 digits of which the first 3 are stepdigits and the last is a standstill digit, namely, 1200, 1201, 1202, 1203, 1210, 1211, 1212, 1213, 1220, 1221, 1222, 1223 (the next, 1230, is discarded since its last digit is also a stepdigit).

4 4

The number of these stepnumbers, 12, is divisible by 3: − = 12 = 3(4) = 3. It is not hard

2 3 to see the reason for this. The set of 12 consecutive stepnumbers above splits into 3 sets each containing 4 stepnumbers: {1200, 1201, 1202, 1203}; {1210, 1211, 1212, 1213}; {1220, 1221, 1222, 1223}. They are just copies of the block of 120: {120, 121, 122, 123} in the sense that the last digits of corresponding members agree. It follows from the rule of lexicographic enumeration of stepnumbers that the same holds for any n and k. Thus we have proved the result that the number of stepnumbers of exactly n + 1 digits, of which the first k + 1 are stepdigits and the rest standstill digits, is divisible by k + 1; moreover, the complementary divisor is the length of the block of k!0n −k.

This completes the proof of the Recursion Formula.

The Blockbuster Formula can be used to calculate any spectral coefficient from those in the preceding row, e.g.,

= 2 + 3 + 4 + 1 = 37 ;

= 3 + 4 + 5 + 1 = 77 ;

This shows how the Blockbuster Formula earns its name: it reveals that a block in the row n + 1 of Pascal’s triangle splits into so many blocks of various sizes in row n.

There is another method of calculating spectral coefficients, namely, as the values of the socalled spectral polynomials that we shall now describe. Consider the spectral coefficients that stand along slanting rows of slope −1 in Pascal’s triangle. For example, slanting row 2 has entries 5, 10, 17, 26, 37, 50,... which are in arithmetic progression of order 2 (numbering starts with 0). We conjecture that, in general, entries in the nth slanting row are in arithmetic progression of order n, i.e., they are values assumed by a polynomial Bn(m) of degree n. We have, for n = 0, 1, 2, 3,... k row 0:

= 1 (constant) k row 1: k +1

= k+2 k row 2: k+2

= k2 + 2k + 2 = (k + 2)2 + 1 k k +3

= k 3 + 6k 2 + 15k + 15 = ( k + 2)3 + 3( k + 2) + 1 k

. . . . . . . . . . . . . . k+n row n:

= ( k + 2) n + ... k

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

The polynomials Bn(m) are called spectral polynomials. The calculation above suggests that we k +n should change the variable m to m = k + 2. Then

= Bn ( k + 2) . To see that, indeed, Bn(k) are k polynomials, we only need to re-write the Recursion Formula: row 3:

Recursion Formula for spectral polynomials

Bn+1(k) = (k − 1) Bn(k) + Bn(k +1)

Under the initial condition B0(k) = 1 (constant) this lets us calculate the

Table of spectral polynomials

B1(k) = k

B2(k) = k2 + 1

B3(k) = k3 + 3k + 1

B4(k) = k4 + 6k2 + 4k + 4

B5(k) = k5 + 10k3 + 10k2 + 20k + 11

B6(k) = k6 + 15k4 + 20k3 + 60k2 + 66k + 41

B7(k) = k7 + 21k5 + 35k4 + 140k3 + 231k2 + 287k + 162

B8(k) = k8 + 28k6 + 56k5 + 280k 4 + 616k3 + 1148k2 + 1296k + 715

B9(k) = k9 + 36k7 + 84k6 + 504k5 + 1386k4 + 3444k3 + 5832k2 + 6435k + 3425

B10(k) = k10 + 45k8 + 120k7 + 840k6 + 2772k5 + 8610k4 + 19440k3 + 32175k2 + 34250k + 17722

. . . . .

Note that the coefficients of the second highest degree terms are zero. By the Recursion Formula, we have: n −1

Bn(1) = Bn−1(2) =

= bn that is, the sum of coefficients of the spectral polynomial of degree n is the Bell number bn . This could serve as a method of checking the calculation of the Bell numbers. Alternatively, if we already know them, it could be used to check the calculation of the spectral polynomials. For example, B6(1) = 1 + 15 + 20 + 60 + 66 + 41 = 203 = b6,

B8(1) = 1 + 28 + 56 + 280 + 616 + 1148 + 1296 + 715 = 4140 = b8 ;

B10(1) = 1 + 45 + 120 + 840 + 2772 + 8610 + 19440 + 32175 + 34200 + 17722 = 115975 = b10

We shall now see a number of other ways to calculate the spectral polynomials. The first is via the binomial formula: (E + k)nb0 = Bn(k +1) where E is the shift operator and b0 = 1. Alternatively, we can use the so-called symbolic notation,

Bn(k + 1) = (b + k)n

Authors prefer to use the symbolic notation where, in the expansion of (b + k)n via the binomial formula one writes bm = bm (even though the use of the shift operator E is more transparent). We ourselves shall also be using the symbolic notation in the sequel. The expansion is called the binomial linear combination of the Bell numbers. For example, we can calculate the spectral polynomials as follows: B1(k + 1) = (b + k)1 = b1 + k = k + 1;

B2(k + 1) = (b + k)2 = b2 + 2b1k + k2 = k2 + 2k + 2 = (k + 1)2 +1;

B3(k + 1) = (b + k)3 = b3 + 3b2k + 3b1k2 + k3 = (k + 1)3 + 3(k + 1) + 1;

B4(k + 1) = (b + k)4 = b4 + 4b3k + 6b2k2 + 4b1k3 + k4 = (k + 1)4 + 6(k + 1)2 + 4(k + 1) + 4

At the end of this Chapter we shall mention another, in fact the easiest, method of calculating the successive spectral polynomials using integral calculus. The following relations exist between spectral polynomials, spectral coefficients, and the Bell numbers:

Bn(k)

=

(b + k − 1)n

= n+k −2 k −2 n k

=

Bn – k(k + 2)

=

(b + k +1)n – k

(b + k)n

= n + k −1 k −1

=

Bn (k + 1)

In Chapter 8 on Dobinski’s representation we shall add yet another formula expressing the spectral coefficients in terms of infinite series. The middle formula above has a name of its own:

Binomial Exchange Formula n k

= (b + k +1)n –k = Bn – k(k + 2)

The choice of name will be made clear in Volume II in the Chapter on digital exchanges. The symbolic notation can also be used to calculate spectral coefficients in terms of the Bell numbers, e.g.,

= (b + 2) 4 = b4 + 8b3 + 24b2 + 32b1 + 16 = 15 + 40 + 48 + 32 + 16 = 151 ;

= (b + 3)3 = b3 + 9b2 + 27b1 + 27 = 5 + 18 + 27 + 27 = 77 .

Recall that the entries along the slanting rows with slope + 1 of Pascal’s triangle are: n n +1 n+2 n+3 n+k

= Bn(2) = bn+1 ;

= Bk(3) ;

= Bn(k + 2) ;...

= Bn(4) ;

= Bn(5) ; ..., k

The case n = 0 deserves further attention. In symbolic notation: bk + 1 = (b + 1)k from where we get the

Vertical Recursion Formula for the Bell numbers

⎛k ⎞

⎛k ⎞

⎛ k ⎞ bk +1 = bk + ⎜ ⎟ bk −1 + ⎜ ⎟ bk −2 + ... + ⎜

⎟ b1 + 1

⎝1⎠

⎝2⎠

⎝ k − 1⎠

There is a nice combinatorial proof of this. We distinguish one of the elements of the set X of k + 1 elements, say, by calling it black while the others are white. We also call that coset of a quotient set of X black which contains the black element of X. Then we count the quotient sets of X according as they have 1, 2, 3,…, k + 1 elements in the black coset, and add.

In Chapter 5 we shall also see another, called the Horizontal Recursion Formula. The terminology will be made clear in Volume II, Chapter 11.

Our formula can be used to calculate the Bell numbers, e.g., b6 = (b +1)5 = b5 + 5b4 + 10b3 + 10b2 + 5b1 + b0 = 52 + 5(15) + 10(5) + 10(2) + 5(1) + 1 = 203.

Yet another recursion formula for the Bell numbers will be given in Chapter 5 in terms of the Stirling numbers of the first kind. An even simpler method of calculation in terms of higher differences will be discussed in Volume II. It is interesting to note that E.T. Bell developed an elaborate but wholly superfluous ‘umbral calculus’ as a result of his failure to grasp the idea that one can transfer a shift from subscript to superscript by the shift operator E. Bell was not the only one to fall into this trap. G. T. Williams [8] suffered the same fate.

As noted above, the values for k = 2, 3, 4,... of Bn(k) are just the entries that stand in slanting rows 2, 3, 4,... with slope + 1 of Pascal’s triangle. In addition, Bn(1) = bn+1 are the entries in slanting row 1. This furnishes yet another method of calculating the Bell numbers, namely, by adding up the coefficients of the spectral polynomials. In the same order of ideas we mention the

Theorem. The alternating sum of the first n Bell numbers is just the constant term in the spectral polynomial Bn+1(x):

Bn+1(0) = bn – bn−1 + bn – 2 − + ... + (−1)n +1b1

Proof. By the Recursion Formula for the spectral polynomials, Bn +1 (0) = Bn (1) − Bn (0) . Hence

Bn +1 (0) = bn − Bn (0) = bk − bn −1 + Bn −1 (0) = ... = bn − bn −1 + bn −2 − +... + ( −1) n +1 b1 .

For example,

52 −15 + 5 − 2 + 1 = 58 − 17 = 41 = B6(0)

203 – 52 + 15 – 5 + 2 – 1 = 162 = B7 (0)

877 – 203 + 53 – 15 + 5 – 2 + 1 = 715 = B8(0)

We note that the spectral polynomials satisfy the differential equation

Bn′(x) = nBn −1(x) which makes it possible to calculate them through successive integration:

Bn+1(x) = (n + 1) ∫ Bn(x)dx + C where the constant C = Bn +1(0) can be obtained as the alternating sum of the Bell numbers. It can also be obtained as C = bn − Bn (0). For example, if we know that

B4(x) = x4 + 6x2 + 4x + 4, then we can write:

B5(x) = 5(x5/5 + 6x3/3 + 4x2/2 + 4x) + C = x5 + 10x3 + 10x2 + 20x + C where C = B5(0) = b4 − b3 + b2 − b1 = 15 − 5 + 2 − 1 = 11. In this way we can calculate the successive spectral polynomials from B1(x) = x through the indefinite integral, provided that we have the sequence of the Bell numbers.

To recapitulate, in the slanting rows of slope −1 of Pascal’s triangle for the spectral n+k −2 with n fixed and k = 2, 3, 4,… These numbers are coefficients (see p 47) we find Bn(k) = k −2 in an arithmetic progression of order n. One can check that the nth difference sequence is constant and is equal to n! For example, the entries in row 2: 5, 10, 17, 26, 37, 50,..., are in arithmetic progression of order two, and the second difference sequence is constant equal to 2 = 2!; those in row three: 15, 37, 77, 141, 235,...are in arithmetic progression of order three and the third difference sequence is constant equal to 6 = 3!; those in row four: 52, 151, 372, 799, 1540,... are in arithmetic progression of order four and the fourth difference sequence is constant equal to 24 = 4!, etc. The property that entries in the slanting rows of slope −1 are in arithmetic progression is shared by Pascal’s triangle for the binomial coefficients (see Chapter 2) and the Stirling numbers of either kind (Chapters 5 and 6).

Indeed, it is this fact that is responsible for the striking repetitive fractal pattern revealed by the Sierpinski triangles (mod p), where p is a prime number.

We have also treated entries in the slanting rows of slope + 1. They are, once more, the numbers Bn(k) = n+k −2 where this time it is k that is fixed and n = 0, 1, 2, 3,… is variable. Thus k −2 for k = 2, Bn(2) = n +1 n

= (b + yields the Bell numbers 1, 2, 5, 15, 52,…; for k = 3, Bn(3) =

2)n yields the numbers 1, 3, 10, 37,…; for k = 4, Bn(4) =

1, 4, 17, 77,…; for k = 5, Bn(5) = n+2

= (b + 3)n yields the numbers n+3

= (b + 4)n yields the numbers 1, 5, 26, 141,…

In this Chapter we have seen three roles that the spectral coefficients play: (1) they are the lengths of blocks of consecutive stepnumbers from a pure stepnumber to the highest pure stepnumber of the same number of digits; (2) they furnish the values of the spectral polynomials; (3) they are the binomial linear combinations of consecutive Bell numbers. To this we shall add two more roles that the spectral coefficients have. In Chapter 7 we shall see that the spectral coefficients furnish the variable the variable place value of digits in the stepnumber system. In Chapter 8 we shall discuss Dobinski’s representation of the Bell numbers in terms of infinite series. This representation can be extended to the binomial linear combinations of the Bell numbers with the result that the spectral coefficients also have their own Dobinski representation.

Further results on the Bell numbers can be found in the Exercises. Chapter 6 on the Stirling numbers the second kind has further information concerning the Bell numbers.

Exercises

1. Show that the coefficients cn,m , cn,m+1 , cn,m+1 ,... of the spectral polynomials Bn(k) are in arithmetic progression of order k. Find k in terms of m. Calculate the kth difference sequence. 2. Derive the Recursion Formula for the coefficients cn,m of the spectral polynomials Bn(k).

2. Show that the coefficients of Bp(x), with the exception of the first and last, are divisible by p, provided that p is a prime number. Is this true or false for a composite number?

3. Show that the coefficients of B pn ( x ) , with the exception of the firs and last, are divisible by the prime number p.

4. Put the coefficients of Bm(x) for m = 1, 2, 3,... into Pascal’s and pass to Sierpinski’s triangle (mod p). Describe the pattern that comes along.

5. Show that cp,0 ≡ 1 (mod p), where cp0 is the constant term of the spectral polynomial Bp(x), provided that p is a prime number.

6. The smallest n whose stepnumber representation has fewer digits than its decimal is 58.

True or false: every number larger than n must have the same property.

8. Prove that 1n + 1n = 10n+1 + 1 for n = 0, 1, 2, 3,...

9. Show that (b − 1)n = bn – 1 − bn – 2 + ... + (−1)nb1 and, from this, get another recursion formula for bn . Use this result to calculate bn up to n = 6.

10. Show that the spectral coefficients standing in slanting row m with slope −1 of Pascal’s triangle are in arithmetic progression of order k. Find k in terms of m. Calculate the kth difference sequence.

11. Construct the Sierpinski triangles (mod p) of the spectral coefficients, for p = 2, 3, 5, 7.

Describe the pattern that comes along.

12. Prove that the spectral polynomials satisfy the differential equation

Bn′(x) = nBn – 1(x)

(Hint: Use Maclaurin’s Formula.)

13. Solve the system of linear equations with infinitely many unknowns

1x1 = b1

1x1 + 1x2 = b2

1x1 + 2x2 + 1x3 = b3

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

. . . . . . where on the left hand side we have the binomial coefficients, and check.

14. Solve the system of linear equations with infinitely many unknowns

1x1 = b0

– 1x1 + 1x2 = b1

1x1 – 2x2 + 1x3 = b2

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

. . . . . . where on the left hand side we have the binomial coefficients with alternating signature.

Check.

15. Using the Recursion Formula, calculate the entries in row 13 of Pascal’s triangle for the spectral coefficients, starting with 1 on the far right and proceeding to the left. For example, = 1 + 13

= 1 + 13 = 14 ;

= 14 + 12

= 14 + 156 = 170 ;

= 170 + 11 = ...

16. Show that bn ≡ 0 (mod 2) ⇔ n ≡ 2 (mod 3). In other words, b2 and every third Bell number thereafter is even, and all the others are odd.

17. Show that, more generally, for any fixed k, n

≡ 0 (mod 2) ⇔ n ≡ 2 (mod 3) k

18. Show that Bk (0) + Bk −1 (0) = bk for k = 2, 3, 4, …

In the following exercises, p is a prime number.

19. Show that B p +1 (0) ≡ 2 (mod p).

20. True or false?

B pn +1 (1) ≡ 2 (mod p).

21. Put Cn = bn − bn −1 + bn −2 − +... + ( −1) p +1 b1 . Show that:

(a) Cp ≡ 1

(mod p); (b) C p +1 ≡ 1 (mod p); (c) C p + 2 ≡ 2 (mod p)

22. Show that: (a) B p (1) ≡ 2 (mod p);

(b) B p + 2 (1) ≡ 7 (mod p)

23. Show that: (a) B p (2) ≡ 2 (mod p); (b) B p +1 (2) ≡ 3 (mod p); (c) B p + 2 (2) ≡ 7 (mod p); (d) B p +3 (2) ≡ 20 (mod p)

24. Show that: (a) B2 p (2) ≡ 5 (mod p); (b) B3 p (2) ≡ 15 (mod p); (d) B4 p (2) ≡ 19 (mod p) 25. Show that Bk+1(1) = Bk(2)

25. Show that Bk+1(2) = Bk+1(1) + Bk(3)

26. Solve the differential equation dn y

= n ! under the initial conditions y(k)(1) = k!bn−k dx n for k = 1, 2, 3,…, n.

28. Solve the system of linear equations with infinitely many unknowns

1x1 = y1

2x1 + 1x2 = y2

5x1 + 3x2 + 1x3 = y3

15x1 + 10x2 + 4x3 + 1x4 = y4

52x1 + 37x2 + 17x3 + 5x4 + 1x5 = y5

. . . . . . . . . . . where on the LHS the coefficients are the entries in Pascal’s triangle for the spectral coefficients, by the method of expressing the unknowns one after another from one equation and substituting the previously obtained values into it…