Here we are going to proof that TREE(n+1)/TREE(n)  is strictly increasing, or TREE(n+1)/TREE(n) > TREE(n)/TREE(n-1). In fact, we'll show that TREE(n+1)/TREE(n) > TREE(n), or TREE(n+1) > TREE(n)^2.


Let []k be the kth bracket and () a level 1 bracket. Now we'll proof TREE(n+1) > TREE(n)^2. for n≥2.

1. []n+1

2. [[]n]n

3. [[]n-1[]n-1]n

4. [[[]n-1[]n-1]n-1]n

5. [[[[[]n-1]n-1]n-1]n-1]n

6. ([[[[]n-1]n-1]n-1]n[]n)

7. ([[[[]n-1]n-1]n-1]2nd graph of TREE(n))

t+5. ([[[[]n-1]n-1]n-1]n t th graph of TREE(n))

TREE(n)+6. ([[[[]n-1]n-1]n-1]n)

TREE(n)+7. ([]n[]n...[]n[]n) w/ TREE(n)+6 []ns.

We can reduce each of these one by one for TREE(n) steps, so we've proven that TREE(n+1) ≥ TREE(n)(TREE(n)+6) > TREE(n)^2.

This completes the proof.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.