I will prove a stronger result. We will prove that $N(t,s)\leq N(t-1,s)+N(t,s-1)$$\bf{Proof}$: Let $n=N(t-1,s)+N(t,s-1)$, then assume that we are giving a coloring of $K_n$. We want to find either a red copy of $K_t$ or a blue copy of $K_s$. Let $x\in K_n$ be given. As the graph is complete, we have that $deg(x)=n-1=N(t-1,s)+N(t,s-1)-1$. Either there are $N(t-1,s)$ red edges or $N(t,s-1)$ blue edges (let me know if you want me to elaborate in this part). Without loss of generality, let us say that the first case holds. We have at least $a=N(t-1,s)$ red edges. Then consider a subgraph $K_a$ that is formed by the $a$-number of vertices adjacent to $x$ through a red edge. If there is a blue copy of $K_s$ in $K_a$ we are done. If otherwise, by definition of $N(t-1,s)$, we have a red copy of $K_{t-1}$ in $K_a$, by adjoining $x$ to $K_a$, we have a red copy of $K_t$ in $K_n$.
Hence the bound is proven. Now we prove that $N(t,s)\leq \binom{s+t-2}{t-1}$by induction on $s+t$. Note that if $t=2$ or $s=2$, then we have that $N(t,2)=t$. And hence we would have that $t=N(t,2)\leq\binom{2+t-2}{t-1}=t$ holds. This was our base case. Then assume that it holds for any pair (t',s') with t'+s'.Then by our recursive looking bound we have that $N(t,s)\leq N(t-1,s)+N(t,s-1)\leq\binom{s+t-1-2}{t-1-1}+\binom{s-1+t-2}{t}=\binom{s+t-2}{t-1}$Now we are almost done. Let $t=s$. Then, $N(t,t)\leq\binom{2t-2}{t-1}$. I leave it to you to check that indeed $\binom{2t-2}{t-1}\leq 2^{2(t-1)}=4^{t-1}$
$\bf{Remark:}$ You could do a little better since $\binom{2t-2}{t-1}\leq \frac{2^{2t-2}}{\sqrt{t}}$