Can an inductive proof with a fixed parameter assume the hypothesis proved for a different value of that parameter?

Question

Suppose we are trying to prove a statement $\forall n\forall k\varphi(n,k)$.

We fix $n$ and proceed to prove $\forall k\varphi(n,k)$ by induction. We show the base case $k=0$, we suppose it's true for $k-1$, but then when showing the inductive step of $k$ we appeal to $\varphi(n+1,k-1)$.

Is the resulting proof valid? Are we allowed to appeal to the inductive hypotheses of a different $n$? Could this be some kind of infinite dependence?

Answer 1

This line of argument is valid, but the justification isn't correct. $\forall n\forall k \phi(n, k)$ is logically equivalent to $\forall k \forall n \phi(n, k)$. The latter formula can be proved by induction on $k$, and then the inductive hypothesis will be $\forall n \phi(n, k - 1)$. So yes, you can appeal to the inductive hypotheses for any $n$ you like, provided you strengthen the statement you are trying to prove (from $\forall k \phi(n, k)$ to $\forall k \forall n \phi(n, k)$).

Answer 2

When doing induction by $k$, one is attempting to prove some formula $\psi(k)$, and so in the induction step one is proving the implication $\psi(k-1) \implies \psi(k)$.

From the setup that you have described, once $n$ is fixed then the statement $\psi(k)$ is given by $$\psi(k) := \phi(n,k) $$ So the implication $\psi(k-1) \implies \psi(k)$ translates into $\phi(n,k-1) \implies \phi(n,k)$.

So no, $\phi(n+1,k-1) \implies \phi(n,k)$ is the incorrect implication. You should be appealing to $\phi(n,k-1)$, not to $\phi(n+1,k-1)$.

Answer 3

No, if you fix $n$ at the "top level" of your proof, you can't appeal to $\varphi(n+1, k-1)$.

With complicated inductions like this, it's often useful to explicitly identify your induction proposition, $P(k)$. And in this case if you did define

$$ P(k) = \forall n \, \, \, \varphi(n, k)$$

then you would be allowed to assume $\varphi(n+1, k-1)$ in your induction step, as it is a specific instance of $P(k-1)$.

When doing an induction with two variables present it can be useful to think of it as painting in the non-negative quadrant of the lattice of integer points $(k,n)$. Sadly I'm not good enough at making digital math diagrams to draw it, but let me try to describe it.

Assume the $k$-axis is the horizontal, and $n$ the vertical axis, and we're just considering non-negative integer values.

Fixing $n$ and doing an induction on $k$ means you're looking at an arbitrary row. Proving the $k=0$ case means you've painted the point in the row on the vertical $n$-axis, and the induction step shows that you can keep moving over to the right and paint in the whole row. @LeeMosher's answer explains this version.

Having your induction proposition include "$\forall n$", (as I describe in the first part of this answer), means your $k=0$ proof paints the entire vertical column on the $n$-axis. Then your induction step says that if you've got one entire column painted you can paint the entire column that's one step to the right.

Both of these are valid, although the "do it for arbitrary fixed $n$" version is much more common than the "for all $n$" version. I think the "fixed $n$" version is conceptually simpler, and so if you can do the proof that way, you're going to prefer it.

But I'm a big fan of understanding it either way, and really like the approach of treating induction as

• base step = painting in some starter points,

• induction step = if I have certain points painted I can paint certain other points, and

• your goal is paint all the points.