11,578
pages

In this blog post, I will be proving the following lower bound to the fast growing hierarchy:

for , by proving

We will prove by induction over .

For our base case, we show this holds for .

We do this by applying induction over in

Trivially holds for . Assume holds for some arbitrary . We now show must hold for .

which concludes our base case for . Assume holds for some arbitrary . We now show must hold for by applying induction over .

Trivially holds for . Assume holds for some arbitrary . We now show must hold for .

Q.E.D.