<<     >>

APL Exercises 3
Proofs
 

⎕io←0 throughout.

The following way of proof is adapted from Kenneth E. Iverson’s Turing lecture, section 1.5:

A proof by a sequence of identities is presented by listing a sequence of expressions, annotating each expression with the supporting evidence for its equivalence with its predecessor. For example:

+/⍳n
+/⌽⍳n + is associative and commutative
2÷⍨(+/⍳n)+(+/⌽⍳n) (x+x)÷2 ←→ x
2÷⍨+/(⍳n)+(⌽⍳n) + is associative and commutative
2÷⍨+/n⍴n-1 lemma
2÷⍨n×n-1 definition of ×
2!n definition of !

3.0 Proof by Induction

Proof by induction of a statement S(n) has the following two-step plan:

• BasisShow that S(0) is true.
• Induction  Show that if S(n) is true, then S(n+1) is also true. The antecedent “if S(n) is true” is called the inductive hypothesis.

The following is a proof by induction that +/⍳n ←→ 2÷⍨n×n-1 .

+/⍳0 basis
0
2÷⍨0×0-1
 
+/⍳n+1 induction
(+/⍳n)+n
(+/⍳n)+2÷⍨2×n
(2÷⍨n×n-1)+2÷⍨2×n inductive hypothesis
2÷⍨(n×n-1)+2×n
2÷⍨n×(n-1)+2
2÷⍨n×n+1
QED

a. Provide an annotation for each step.

b. Pick a random value for n ≥ 0 . Enter each expression in the proof into an APL session to check that each expression has the same result as the preceeding and following expression.
 

3.1 Proof by Contradiction

In proof by contraction of a statement S , assume that ~S (the negation of S) is true and then show that it leads to a contradiction. Therefore, S must have been true in the first place.

The following is a proof by contradiction that √2 is not a rational number. (A rational number is a ratio p÷q where p and q are integers with 1=p∨q .)

(2*0.5)=p÷q assume 2*0.5 is rational
2=(p÷q)*2
(2×q*2)=p*2
(2×q*2)=(2×r)*2 p*2 is even and therefore p is even;
p=2×r for some integer r
(2×q*2)=4×r*2
(q*2)=2×r*2
2≤p∨q q*2 is even and therefore q is even;
p and q are both even
QED

Provide an annotation for each step.
 

3.2 Sum of Odd Integers

Prove that the sum of the first n odd integers is n*2 . That is, +/1+2×⍳n is n*2 . The veracity of the statement for n=10 is illustrated by the following 10-by-10 matrix:

   ∘.⌈⍨ 1+2×⍳10
 1  3  5  7  9 11 13 15 17 19
 3  3  5  7  9 11 13 15 17 19
 5  5  5  7  9 11 13 15 17 19
 7  7  7  7  9 11 13 15 17 19
 9  9  9  9  9 11 13 15 17 19
11 11 11 11 11 11 13 15 17 19
13 13 13 13 13 13 13 15 17 19
15 15 15 15 15 15 15 15 17 19
17 17 17 17 17 17 17 17 17 19
19 19 19 19 19 19 19 19 19 19

3.3 Sum of an Arithmetic Progression

a+b×⍳n is an arithmetic progression vector. Derive and prove a formula for the sum of an arithmetic progression vector.
 

3.4 Sum of a Geometric Progression

a.  a×r*⍳n is a geometric progression vector. Derive and prove a formula for the sum of a geometric progression vector.

b.  If 1>|r , prove that +/a×r*⍳∞ is a÷1-r .
 

3.5 Sum of Binomial Coefficients

Prove that the sum of the binomial coefficients of order n is 2*n .
 

3.6 Permutation

Let ⍵ be a permutation.

a. Prove that ⍋⍵ is the inverse of ⍵ .
b. Prove that ⍋⍋⍵ is the identity function.