Problem Proof 0 (1.2.1, 2)

``There must be something wrong with the following proof. What is it?

Theorem. Let a be any positive number. For all positive integers
n we have a^n-1 = 1. Proof. If n=1, a^n-1=a^1-1=a⁰=1.
And by induction, assuming that the theorem is true for 1, 2, ..., n, we have



so the theorem is true for n+1 as well."

Continued

Not a Knuth exercise, I know, but no less important

Mr Steve Mayer argues that it is wrong to start with what you want to prove end up with a true statement. Given that I've been doing just that for quite some time now, I have no choice but to disagree.

1.2.6, 13

Knuth asks:

Prove the summation formula, Eq. (10).

Continued

Floor and Ceiling (1.2.4, 3)

Knuth asks

Let n be an integer and let x be a real number. Prove that

Continued

Product Rules (1.2.3, 22)

Knuth asks:

State the appropriate analogs of Eqs (5), (7), (8), and (11) for products instead of sums.

Continued

The Laws of Exponents (1.2.2, 7)

Knuth asks

Given that x and y are integers, prove the laws of exponents, starting from he definition given by Eq.(4).

Continued

Property of Fibonacci (1.2.1, 4)

Knuth asks

Prove that, in addition to Eq(3), Fibonacci numbers satisfy F_n ≥ Φ^n-2

Unfortunately, Knuth has failed to include the important point that the above is only valid for n ≥ 1. I suspect that this is because he starts counting from 1. We do not, however, having learned why the natural numbers should begin at 0.

Continued

Introduction to Induction (1.2.1, 1)

Knuth asks

Explain how to modify the idea of proof by mathematical induction, in case we want to prove some statement P(n) for all nonnegative integers - that is, for n = 0, 1, 2, ... instead of n = 1, 2, 3, ... .

To prove by induction



where n is a natural number and P is predicate we first prove P.0. We then prove



By renaming the dummy we can see that this is the same as saying

Multiple Assignment (1.1, 1)

Knuth asks

The text showed how to interchange the values of variables m and n, using the replacement notation, by setting t←m, m←n, n←t. Show how the values of four variables (a,b,c,d) can be rearranged to (b,c,d,a) by a sequence of replacements. In other words, the new value of a is to be the original value of b, etc. Try to use the minimum number of replacements.

Continued

With Complements (1.3.1, 6)

Knuth asks

Prove or disprove the following rule for negating a n-bit number in two's complement notation: "Complement all the bits, then add one." (For example, ^#0...01 becomes ^#f...fe, then ^#f...ff; also ^#f...ff becomes ^#0..00, then ^#0..01.)

Solution.

(1.3.1, 24)

Knuth asks:

If we represent a subset S of {0, 1, ..., 63} by the bit vector

([0 ∈ S], [1 ∈ S], ..., [63 ∈ S]),

the bitwise operations ∧ and ∨ correspond respectively to 
set intersection  (S ∩ T) and set union (S ∪ T).

Which bitwise operation corresponds to set difference (S\T)?

The set S\T is characterised by the predicate

S ∧ ¬T

.
Hence the required operation is ANDN.

The Byte Chain (1.3.1, 4)

Knuth asks:

A kilobyte (kB or KB) is 1000 bytes, and a megabyte (MB) is 1000 kB. What are the official names and abbreviations for larger numbers of bytes?

Thanks to wikipedia we have

1000 MB = 1 gigabyte (GB)
1000 GB = 1 terabyte (TB)
1000 TB = 1 petabyte (PB)
1000 PB = 1 exabyte (EB)
1000 EB = 1 zetabyte (ZB)
1000 ZB = 1 yottabyte (EB)

Inspired by a dog (1.3.1, 3)

Knuth asks:

Four-bit quantities - half-bytes, or hexadecimal digits - are often called nybbles. Suggest a good name for two-bit quantities, so that we have a complete binary nomenclature ranging from bits to octabytes.

Well I was once attacked by a dog and, though I managed to escape being bitten,
he did manage to nip my thigh. So I propose 'nip'. Henceforth 2 bits = 1 nip.

Odd letters (1.3.1, 2)

Knuth asks:

Which of the letters {A,B,C,D,E,F,a,b,c,d,e,f} are odd when considered as
(a) hexadecimal digits? (b) ASCII characters?

(a) Since #A = (10)₁₀ we have immediately {B, D, F,b,d,f} are odd when considered as hexadecimal digits.

(b) The ascii for A is #41 and a is #61. Hence we can easily see that {A,C,E,a,c,e} are odd when considered as ASCII characters.