The argument of a proof based on double induction

Question

I am struggling to convince myself of this proof. Let me rewrite it so that the proof's structure and my interpretation of it are more apparent.

Let $ S(k, n) $ be true when $ n! \mid P(k, n) $ where $ P(k, n) = (k+1)(k+2)\cdots(k+n) $. We want to show that $ S(k, n) $ holds for all $ k, n \in \mathbb{Z}^{+} $. (I consider only the positive integers to simplify the discussion.)

Induction on $ n $:

1. The base case $ S(k, 1) $ holds since $ 1! \mid (k + 1) $ for all $ k $
2. The inductive step on $ n $ is not demonstrated yet, but the inductive hypothesis $ H_0 $ is introduced: $ (n-1)! \mid P(k, n-1) $
3. Induction on $ k $:
   1. The base case $ S(0, n) $ holds since $ P(0, n) = n! $
   2. The inductive step $ H_1 $ on $ k $ assumes $ n! \mid P(k, n) $
   3. Consider $$ \begin{align} P(k+1, n) & = ((k+1)+1)((k+1)+2)\cdots((k+1)+(n-1))((k+1)+n) \\ & = [(k+2)(k+3)\cdots(k+n)](k+1) + [(k+2)\cdots(k+n)]n \\ & = P(k, n) + nP(k+1, n-1) \end{align} $$
   4. The first term $ P(k, n) $ is divisible by $ n! $ by $ H_1 $
   5. The second term $ nP(k+1, n-1) $ is also divisible by $ n! $:
      1. By $ H_0 $ we have $ (n-1)! \mid P(k+1, n-1) $
      2. Then $ n $ times a multiple of $ (n-1)! $ is divisible by $ n! $
   6. Therefore, $ S(k+1, n) $ holds

I do not see what makes step 3.5.1 valid. How can one use $ S(k+1, n-1) $ during the induction step when neither $ H_0 \equiv S(k, n-1) $ nor $ H_1 \equiv S(k, n) $ are stated in terms of $ k + 1 $?

Please note that I understand the inductive argument on $ [ k + n = z ] \to [ k + n = z + 1 ] $ as presented in the alternative answer. Such argument also holds for the proof in question, but this is not how the author structured it. According to this answer, the proof appears to use simple induction twice. See this proof for an example of such argument. From what I can see, it does not use $ \ell+1 $ during the induction step on the second variable $ \ell $.

Answer 1

It may help to elaborate on the argument between 2 and 3.

The inductive step on n is not demonstrated yet, but the inductive hypothesis $H_0$ is introduced: $(n−1)!∣P(k,n−1)$ for all $k \in \mathbb{N}$

I added the for all $k\in \mathbb{N}$. We are assuming that everything works perfectly for $n-1$ (this is the nature of induction).

Perhaps a better way is to just frame this in terms of the proposition we're trying to prove: You've already shown that $S(k,0)$ holds for all $k$, so now we will assume inductively that $S(k,n-1)$ holds for all $k$.

For the next step, you say we are going to use

Induction on k

but specifically what proposition are we proving here? As per the proof by induction format, we're trying to prove $S(k,n)$, where $n$ is some fixed value, and we know $S(j,n-1)$ is true for all $j$ (note the change of variable here, so as not to cause confusion).

Now hopefully it's clear why you can use $S(j,n)$, where $j = k+1$: it's simply part of the inductive hypothesis.