Definition
Examples
Bounds
We will show that grows like and thus that grows like (See Knuth's up-arrow notation and User:sligocki/up-arrow properties).
- Claim.
- for any and
- Proof by induction.
- Base Case
-
-
- Inductive Step
Assume that (for all or )
-
- QED
- Claim.
- for any and (In fact the bound can be tightened to m+1 for k ≥ 2)
- Proof by induction.
- Base Case
-
-
- (left as an exercise to the reader)
- Inductive Step
Assume that (for or )
-
≤? statements seem obvious, but grungy to prove (left as an exercise to the reader :)
- Claim.
- for
- Proof.
-
-
-
-
- QED
References