uni/adm/ue1.ms

.TL
ADM UE1
.AU
strlst
.SH
motivation
.PP
This document outlines exercises 6, 11, 15, 20, 24.
.EQ
define implies `~~=>`
define so `~:`
define is `~~=~~`
.EN

.SH
e6
.PP
Using induction, prove the following:
.EQ
sum from n to j=2 {j(j-1)} is {(n - 1) n (n + 1)} over 3 ,~ (n >= 2)
.EN
.PP
.BX "induction basis"
.EQ
2~ (2 - 1) is {(2 - 1) ~2~ (2 + 1)} over 3 is {3 over 3} 2~ (2 - 1) is 2~ (2 - 1) 
.EN
.PP
.BX "induction step"
.EQ
P(n) implies P(n + 1)
.EN
.EQ
sum from {j = 2} to {n + 1}
times ~j (j-1) mark is
{n~ (n + 1) (n + 2)} over 3
.EN
.EQ
sum from {j = 2} to {n}
times ~j (j-1)
times (n+1) n lineup is
{(n - 1) ~n~ (n + 1)} over 3 + (n+1)n
.EN
.EQ
lineup is {(n-1) bold {~(n+1) ~n} + 3~ bold {(n+1)~n}} over 3
.EN
.EQ
lineup is {bold {(n+1)~n} ~(n-1+3)} over 3
.EN
.EQ
lineup is {bold {(n+1)~n} ~(n+2)} over 3
.EN
.BX q.e.d.

.SH
e11
.PP
.EQ
F sub 0 = 0, F sub 1 = 1,~ F sub {n+2} = F sub {n + 1} + F sub n,~ n ... roman {natural number}
.EN
.PP
Using induction, prove the following:
.EQ
define pexp `{1 + sqrt 5} over 2`
define qexp `{1 - sqrt 5} over 2`
define fibdef `F sub $1 is
1 over sqrt 5 left [
    left ( pexp right ) sup $1 - 
    left ( qexp right ) sup $1 
right ]`
define fibshort `1 over sqrt 5 left [
    p sup $1 - 
    q sup $1 
right ]`
fibdef(n)
.EN
.PP
.BX "induction basis"
.EQ
fibdef(0) is 1 over sqrt 5 (1 - 1) is 0
.EN
.EQ
fibdef(1) is 1 over {2 sqrt 5} (1 + sqrt 5 - 1 + sqrt 5) is {2 sqrt 5} over {2 sqrt 5} is 1
.EN
.PP
.BX "induction step"
.EQ
p = pexp,~ q = qexp
so F sub n is 1 over sqrt 5 ( p sup n - q sup n )
.EN
.EQ
F sub n+2 = F sub n+1 + F sub n
.EN
.EQ
fibshort(n+2) mark is fibshort(n+1) + fibshort(n)
.EN
.EQ
p sup n+2 - q sup n+2
lineup is p sup n+1 - q sup n+1 + p sup n - q sup n
.EN
.EQ
p sup n+2 - q sup n+2
lineup is { p sup n+2 } over p - { q sup n+2 } over q + { p sup n+2 } over p sup 2 - { q sup n+2 } over q sup 2
.EN
.EQ
p sup n+2 - q sup n+2
lineup is p sup n+2
~left [ 1 over p + 1 over p sup 2 right ]
- q sup n+2
~left [ 1 over q + 1 over q sup 2 right ]
delim $$
.EN
.PP
At this point, we observe the very particular structure $ p sup n+2 - q sup n+2 = p sup n+2 times ~r - q sup n+2 times ~k $ and note that in order for this equation to be valid, we need $ r = 1 $ and $ k = 1 $ to be true. We continue our proof by examining $ r $ and $ k $ separately. 
.EQ
1
mark is 1 over p + 1 over {p sup 2}
     is 1 over q + 1 over {q sup 2}
.EN
.EQ
lineup is 1 over { ( pexp ) } + 1 over { ( pexp ) sup 2 }
       is 1 over { ( qexp ) } + 1 over { ( qexp ) sup 2 }
.EN
.EQ
lineup is 1 over { ( 1 over 2 (1 + sqrt 5 )) } + 1 over { ( 1 over 2 (1 + sqrt 5 )) sup 2 }
       is 1 over { ( 1 over 2 (1 - sqrt 5 )) } + 1 over { ( 1 over 2 (1 - sqrt 5 )) sup 2 }
.EN
.EQ
lineup is 2 over { (1 + sqrt 5 ) } + 4 over { ( 1 + sqrt 5 ) sup 2 }
       is 2 over { (1 - sqrt 5 ) } + 4 over { ( 1 - sqrt 5 ) sup 2 }
.EN
.EQ
lineup is { 2~ (1 + sqrt 5 ) + 4 } over { (1 + sqrt 5 ) sup 2 }
       is { 2~ (1 - sqrt 5 ) + 4 } over { (1 - sqrt 5 ) sup 2 }
.EN
.EQ
lineup is { 2~ (1 + sqrt 5 ) + 4 } over { 1 sup 2 + 2~ sqrt 5 + { sqrt 5 } sup 2 }
       is { 2~ (1 - sqrt 5 ) + 4 } over { 1 sup 2 - 2~ sqrt 5 + { sqrt 5 } sup 2 }
.EN
.EQ
lineup is { 2 + 2~sqrt 5 + 4 } over { 1 + 2~ sqrt 5 + 5 }
       is { 2 - 2~sqrt 5 + 4 } over { 1 - 2~ sqrt 5 + 5 }
.EN
.EQ
lineup is {6 + 2~ sqrt 5 } over {6 + 2~ sqrt 5 }
       is {6 - 2~ sqrt 5 } over {6 - 2~ sqrt 5 }
.EN
.EQ
1 lineup is 1 is 1
.EN
.PP
.BX q.e.d.

.SH
e15
.PP
The following is assumed to be true
.EQ
x sub 0 = 1,~ x sub {k+1} is x sub k + 18k + 15,~ k >= 0
.EN
.PP
Using induction, prove that the following closed form expression is identical:
.EQ
x sub n is (3n + 1) sup 2 ,~ n >= 0
.EN
.BX "induction basis"
.EQ
x sub 0 is (3 times 0 + 1) sup 2 = 1 sup 2 = 1
.EN
.BX "induction step"
.EQ
x sub n+1 is (3 (n+1) + 1) sup 2 = x sub k+1 = x sup n + 18n + 15,~ n = k
.EN
.EQ
(3(n+1) + 1) sup 2 mark is (3n + 1) sup 2 + 18n + 15
.EN
.EQ
(3n + 4) sup 2 lineup is 9n sup 2 + 2 times 3n times 1 + 1 sup 2 + 18n + 15
.EN
.EQ
9n sup 2 + 24n + 16 lineup is 9n sup 2 + 6n + 18n + 1 + 15
.EN
.EQ
24n lineup is 24n
.EN
.PP
.BX q.e.d.

.SH
e20
.PP
Given the predicate
.EQ
P sub initial (A) so 3n + 2 sup n <= 3 sup n
.EN
.PP
Find the $ n >= x $ for which the predicate is valid using induction. 
.EQ
define pinit `3 times $1 + 2 sup $1 <= 3 sup $1`
pinit(0) ,~ 1 <= 1 ,~ roman valid
.EN
.EQ
pinit(1) ,~ 10 <= 9 ,~ roman { invalid! }
.EN
.EQ
pinit(2) ,~ 5 <= 3 ,~ roman { invalid! }
.EN
.EQ
pinit(3) ,~ 17 <= 27 ,~ roman valid
.EN
.PP
We make the assumption that for $ n >= x ,~ x = 3 $, and begin our proof:
.EQ
3 sup n+1 = 3 sup n times 3 mark ~~>=~~ 3(n+1) + 2 sup n+1 = 3n + 3 + 2 sup n times 2
.EN
.PP
We make use of our initial assumption $ P sub initial (A) $ by retransforming it:
.EQ
3n + 2 sup n mark ~~<=~~ 3 sup n
.EN
.EQ
2 sup n lineup ~~<=~~ bold { 3 sup n - 3n }
.EN
.PP
Now we substitue $ 2 sup n $ for $ (3 sup n - 3n) $ (printed bold above), a term that is at least as big, and continue our previous line of thought:
.EQ
3 sup n+1 = 3 times 3 sup n mark ~~>=~~ 3n + 3 + 2 sup n times 2
.EN
.EQ
3 times 3 sup n lineup ~~>=~~ 3n + 3 + bold { (3 sup n - 3n) } times 2
.EN
We transform the right hand side into a different form:
.EQ
3n + 3 + bold { (3 sup n - 3n) } times 2
mark is 3n + 3 + 2 times 3 sup n - 6n
.EN
.EQ
lineup is 3 sup n times 2 + 3 - 3n
.EN
.PP
At this point, the clever reader might have wondered about the $ (3 - 3n) $ part in particular, noticing a most interesting property:
.EQ
n >= 3 implies 3 - 3n <= 0
.EN
.PP
In essence, $ 3 - 3n $ will never produce a number that would
.UL increase
our previous term, allowing us to suggest the following:
.EQ
bold { 3 sup n times 2 } + 3 - 3n ~~<=~~ mark bold { 3 sup n times 2 } 
.EN
.EQ
lineup bold { 3 sup n times 2 } ~~<=~~ 3 sup n times 3 = 3 sup n+1
.EN
.PP
.BX q.e.d.

.SH
e24
.PP
Disprove $ roman max( a, b ) = a = b $, given the following predicate and proof:
.EQ
a, b >= 0 ,~ P(A) so a = b
.EN
.BX "induction basis"
.EQ
P(0) so max(a, b) = 0 implies a = b = 0
.EN
.BX "induction step"
.EQ
P(A) implies P(A+1) so max(a, b) = n implies max(a, b) = n + 1
.EN
.EQ
max(a, b) = n + 1 implies max(a - 1, b - 1) = n so a-1 = b-1 implies a = b
.EN
.PP
This proof has a specific problem, best showed by inserting a few test values:
.EQ
max(a, b) mark is 2 so a = b = 2
.EN
.EQ
implies max(a - 1, b - 1) lineup is 2 - 1 so a - 1 is b - 1 is 1
.EN
.EQ
max(a, b) mark is 1 so a = b = 1
.EN
.EQ
implies max(a - 1, b - 1) lineup is 1 - 1 so a - 1 is b - 1 is 0
.EN
.EQ
max(a, b) mark is 0 so a = b = 0
.EN
.EQ
implies max(a - 1, b - 1) lineup is 0 - 1 so a - 1 is b - 1 is 0 - 1
.EN
.PP
This proof makes it valid for us to suggest $ a is b is 0 - 1 $, but the proof condition also requires $ a, b >= 0 $, a contradiction! Thus, $ a, b $ are not elements of the natural numbers, invalidating the initial condition. 

.SH
e26
.PP
$ P(A) so ~sqrt 5~ $ is irrational. 
.PP
To prove that $ sqrt 5 $ is indeed irrational, let's try proving the opposite:
.EQ
undef is
P(B) : sqrt 5~ roman { is~rational }
define is `~~=~~`
implies sqrt 5 is p over q
.EN
.EQ
5 is p sup 2 over q sup 2 ~~~~~ 5 q sup 2 mark is p sup 2 ~~~~~ 5 ~|~ (5q sup 2 ) implies 5 ~|~ p sup 2 so p is 5 times r
.EN
.EQ
5q sup 2 lineup is (5r) sup 2 is 25 r sup 2
.EN
.EQ
q sup 2 lineup is 5 r sup 2 ~~~~~ 5 ~|~ (5r sup 2 ) implies 5 ~|~ q sup 2 so q = 5 times k
.EN
.EQ
(5k) sup 2 is 25k sup 2 lineup is 5r sup 2
.EN
.EQ
5 lineup is { 5r sup 2 } over { 5k sup 2 }
.EN
.EQ
sqrt 5 lineup is r over k
.EN
.PP
In the beginning we defined $ sqrt 5 $ to be $ p smallover q $, where $ p, q $ are factors that automatically assume smallest possible values because of the reductions applicable to rational numbers. But here we clearly show $ sqrt 5 $ to be a smaller set of factors $ r smallover k $:
.EQ
P(B) implies sqrt 5 is r over k < p over q
.EN
.PP
A contradiction!
.EQ
not~ P(B) < = > P(A)
.EN
.PP
.BX q.e.d.