So I have 2 functions:
$$ a(0,y) = y+ 1\\ a(x, 0) = a(x-1,1)\\ a(x,y) = a(x-1,a(x,y-1)) $$ And: $$ c(0,n) = 0\\ c(1,n) = n^2 + n +1\\ c(m,0) = c(m-1,1)\\ c(m,n) = c(m-1,c(m,n-1)) $$
And then I have: $d(n) = 2^{2^{.^{.^{.^{.^{2}}}}}}$ while the height of the power tower is $n+2$.
I need to show that $c(n,n)>d(n)$ for $n \geq 3$.
I already proved that $a(n,n)>d(n)$ for $n \geq 4$ using induction. So if I was to prove that $c(n,n) > a(n,n)$ for $n>1$, it would mean $c(n,n) > d(n)$ for $n \geq 4$.
But what about $n=3$? Here $a(3,3)<d(3)$ but clearly $c(3,3)>d(3)$. My way to go here would be proving that $c(n,n) > a(n+1,n+1)$ for $n \geq 3$ using induction, so my end goal would be $c(n,n)>a(n+1,n+1)>d(n+1)>d(n) \Rightarrow c(n,n)>d(n)$.
Begin: $c(2,2) = 183 > 61 = a(3,3)$
Assumption: $c(n,n) > a(n+1,n+1)$ for random but fixed $n \geq 3$.
Step: $$ c(n+1,n+1) = c(n,c(n+1,n)) \stackrel{Assumption, wrong?} \geq c(n,a(n+2,n+1)) \stackrel{Assumption, wrong?} > a(n+1, a(n+2,n+1) + 1) \geq a(n+1,a(n+2,n+1)) = a(n+2,n+2) $$
I'm not sure I can use the assumption the way I'm using it to prove the induction step. I think the right way to write it would be:
Step: $$ c(n+1,n+1) = c(n,c(n+1,n)) \geq c(n,c(n,n)) \stackrel{Assumption} \geq c(n,a(n+1,n+1)) ...?\\ $$
To conclude:
I'm a bit lost on how I can show that $c(n,n)>d(n)$ for $n \geq 3$, using $c(n,n) > a(n+1,n+1)$ or attentively to show that $c(n,n)>d(n)$ for $n \geq 4$, using $c(n,n) > a(n,n)$
Note that:
$$c(1,n)>n^2$$
$$c(2,0)=3$$
Prove by induction that:
$$c(2,n)>2^{2^n}$$
And hence notice that
$$c(3,0)=c(2,1)>2^2=d(2)$$
By induction again:
$$c(3,n)>d(2n+2)$$
Which is more than sufficient.