0

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.

Turbo
  • 6,221
  • What you've written out in your second paragraph isn't double induction, it's regular induction on $n$ with an irrelevant letter $k$ being used as a decoration. – Jack M Jan 10 '18 at 16:02
  • @JackM That's technically true, but I think it's pedagogically irrelevant. In my experience, if there are two variables floating around, and you need to induct, then you'll get confused if you don't understand double induction - even if what you end up doing isn't technically double induction after all. – Misha Lavrov Jan 10 '18 at 19:32
  • 1
    I would recommend against writing "nonsense" equations like "$n = n + 1$". You should work out what you actually mean by such statements and choose notation and terminology accordingly. – Derek Elkins left SE Jan 10 '18 at 19:57

1 Answers1

0

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.

Misha Lavrov
  • 142,276
  • In my case $k\geq n$ always. – Turbo Jan 11 '18 at 05:57
  • In that case, the $(n,k) \implies (n+1,k)$ induction step might not work well: certainly the implication $(k,k) \implies (k+1,k)$ shouldn't work. But you could go the other way: start with the base cases $(n,n)$ for all $n$, and prove that $(n,k) \implies (n,k+1)$. – Misha Lavrov Jan 11 '18 at 16:32
  • that I think helps. I have $k \times k$ matrices of rank $n$ that I want to prove something. So prove $n=1$ and $k=1$ and assume for $k=n$ and prove for $k>n$. However that only proves for rank up to $n$ not beyond it. is there a better technique? – Turbo Jan 11 '18 at 16:36
  • If you're set on using induction, you usually start with figuring out what induction steps you can show, and then you see what that gives you and what base cases you need. You might want to ask a more specific question about your problem. – Misha Lavrov Jan 11 '18 at 19:53