How to do double induction when one variable puts a constraint on the other one.

Question

I have a proposition $P(n,l)$ that I believe to be true for $n\geq3$ and $0\leq l < n-1$. How can I prove that?

I've read a comment somewhere about converting a double induction into a standard single variable induction, but I don't know how that works, I feel like the constraint on $l$ might be an obstacle there.

All tips are welcome.

---

The theorem I have was provable by first fixing $n$ and proving it for all allowed $l$, then using that to prove for $n$, but I think the way I did it is not very elegant, because a slight bit of convincing is still necessary. Maybe an honest double induction, if possible, would be more elegant.

Answer 1

You can of course do the following scheme of a double induction. But the exact way of doing it may depend on your concrete problem which you haven't really stated.

1. Induction step for $l$: Let $n \in \mathbb{N}$. Prove that $P(n,l) \Rightarrow P(n,l+1)$ for all $1 \leq l+1 < n-1$
2. Induction step for $n$: Prove that $P(n, n) \Rightarrow P(n+1,0)$.

Together with the base case $P(3,0)$, this will prove your statement.

Basically, what we do here is use that the set of pairs $(n,p)$ that are admissible is countable. We can use any kind of enumeration of this set to map the usual induction scheme from $\mathbb{N}$ to this case. The path I suggested is:

$$ (3,0) \Rightarrow (3,1) \Rightarrow (3,2) \Rightarrow (3,3) \Rightarrow \\ (4, 0) \Rightarrow (4, 1) \Rightarrow \dots \Rightarrow (4,4) \Rightarrow \\ (5,0) \Rightarrow \dots \\ \dots $$ and so on. You may always also take another enumeration of this set, whatever suits your concrete problem.

Answer 2

You may be thinking of something like this answer, which shows how to prove that $Q(x,y)$ is true for all integers $x \geq 0$ and $y \geq 0.$ In particular, consider this syllogism from that answer:

\begin{align} &Q(0,0) \tag1\\ &\forall x,y. Q(x,y) \Rightarrow Q(x+1,y) \tag2\\ &\forall x,y. Q(x,y) \Rightarrow Q(x,y+1) \tag3\\ \hline &\forall x,y. Q(x,y) \end{align}

This is basically induction on the sum $k=x+y.$ The base case $(1)$ is the only possible case when $k=0.$ The inductive step requires two cases because we need $Q(x,y)$ to be true for all possible pairs $(x',y')$ such that $x'+y'=k+1,$ including $x'=k+1, y'=0$ (which can be shown by $(2)$ with $x=k,y=0$ but not by $(3)$) and $x'=0, y'=k+1$ (which can be shown by $(3)$ with $x=0,y=k$ but not by $(2)$).

You have $n \geq 3$ and $0 \leq l < n-1,$ not $x\geq 0$ and $y\geq 0.$ So you can try a change of variables. The fact that $l \leq n-2$ implies that $n - l - 2 \geq 0,$ so you could try setting $x=n - l - 2,$ which makes $x$ an integer such that $x\geq 0.$ Then you can set $y=l,$ so $y\geq 0.$ So $P(n,l)$ becomes $P(x+y+2,y).$ So $Q(x,y) = P(x+y+2,y).$

There's one hitch (aside from the possibility that $P(x+y+2,y)$ is too awkward a statement for you to easily work with): the base case $x=y=0$ requires you to prove $P(2,0),$ which is not something you claimed to be true. There are a few ways around this:

• Show that $P(2,0)$ is true after all (but this works only if the statement actually is true!).
• Let $Q(x,y) = (P(x+y+2,y) \lor (x=0,y=0)).$
• Prove $P(3,0)$ and $P(3,1),$ from which you can conclude that $Q(1,0) \land Q(0,1),$ and use that as your base case instead of $Q(0,0).$ (Basically this is doing induction on $x+y$ where $x+y\geq 1$ rather than $x+y\geq 0.$)

Alternatively, you can go back to your original claim, $P(n,l),$ do an induction on $n$ with base case $n=3$ (which means you have to prove $P(3,0)$ and $P(3,1)$), and for the inductive case you have to prove that if $P(n,l)$ for all $l$ such that $0 \leq l < n-1,$ then $P(n+1,m)$ for all $m$ such that $0 \leq m < n.$