In one dimensional induction we show something holds for $n=0$ or $n=1$ and assume it is true at $n=n$ and prove for $n=n+1$.
In two dimensional induction is it something along show it is true for $(n,k)=(0,k)$ or $(n,k)=(1,k)$ at any $k$ and assume it is true at $(n,k)=(n,k)$ and prove for $(n,k)=(n+1,k)$?
In my case $n\leq k$ always.
Proving that the $(0,k)$ case holds for all $k$, and that $(n,k) \implies (n+1,k)$ for all $k$, is one valid way to do two-dimensional induction. (In fact, you could also think of it as a one-dimensional induction on $n$, leaving $k$ as an arbitrary fixed constant.)
There are other ways to do it. Another common setup for two-dimensional induction is proving that $(0,0)$ holds, that $(n,k) \implies (n+1,k)$, and that $(n,k) \implies (n,k+1)$.
It's better not to focus on specifics, and think about what actually makes the induction work. The key thing to check is: for any case $(n,k)$, is there a path of implications you've proven that starts at a base case, and ends at $(n,k)$?
This is true in the case in your question: we have the path $$(0,k) \implies (1,k) \implies \dots \implies (n-1,k) \implies (n,k).$$ This is true in the other example I gave: we have the path $$(0,0) \implies (0,1) \implies \dots \implies (0,k) \implies (1,k) \implies \dots \implies (n,k).$$
There are always going to be examples which mess with the template, but work because such a path always exists. The weirdest example I know of is one-dimensional - a proof of the fundamental theorem of algebra by Laplace, which takes all odd $n$ as a base case, and proves the implication $\binom{n}{2} \implies n$. This really seems like it ought not to work, but you can show that for every $n$, there's a path that starts at an odd number and uses this implication to get to $n$. (For example, to get to $4$, you take the path $45 \implies 10 \implies 4$.)
That's a digression, but the point is that you shouldn't try to memorize templates for induction that work. Instead, check if every case has a proof - a chain of implications that lead to that case from a base case.