1.5 Sequences 15Now we can write 2^100 in the form 10x, onlyxwill not be an integer:
the appropriate value ofxisx=lg2^100 = 100 lg 2 (we use lg to denote
logarithm with base 10). We have then
k− 1 ≤x<k,which means thatk−1 is the largest integer not exceedingx. Mathemati-
cians have a name for this: It is theinteger part,orfloor,ofx, and it is
denoted by x. We can also say that we obtainkby roundingxdown to
the next integer. There is also a name for the number obtained by rounding
xup to the next integer: It is called theceilingofx, and denoted byx.
Using any scientific calculator (or table of logarithms), we see that lg 2≈
0 .30103, thus 100 lg 2≈ 30 .103, and rounding this down we get thatk−1=
- Thus 2^100 has 31 digits.
1.4.1How many bits (binary digits) does 2^100 have if written in base 2?1.4.2Find a formula for the number of digits of 2n.1.5 Sequences
Motivated by the “encoding” of subsets as strings of 0’s and 1’s, we may
want to determine the number of strings of lengthncomposed of some other
set of symbols, for example,a,bandc. The argument we gave for the case
of 0’s and 1’s can be carried over to this case without any essential change.
We can observe that for the first element of the string, we can choose any
ofa,bandc, that is, we have 3 choices. No matter what we choose, there
are 3 choices for the second element of the string, so the number of ways
to choose the first two elements is 3^2 = 9. Proceeding in a similar manner,
we get that the number of ways to choose the whole string is 3n.
In fact, the number 3 has no special role here; the same argument proves
the following theorem:
Theorem 1.5.1The number of strings of lengthncomposed ofkgiven
elements iskn.
The following problem leads to a generalization of this question. Suppose
that a database has 4 fields: the first, containing an 8-character abbreviation
of an employee’s name; the second, M or F for sex; the third, the birthday
of the employee, in the format mm-dd-yy (disregarding the problem of not
being able to distinguish employees born in 1880 from employees born in
1980); and the fourth, a job code that can be one of 13 possibilities. How
many different records are possible?
The number will certainly be large. We already know from theorem 1.5.1
that the first field may contain 26^8 > 200 , 000 , 000 ,000 names (most of