A friend of mine is working on some project where he wants to prove by induction that $$E[X]^{j}_n = \lambda T \;\;\;\; \forall n\in\mathbb{N}, j>n$$
We are wondering how to do this by induction when we have two free parameters.
Is it true that the induction procedure is as follows:
Base case:
Take two arbitrary numbers $(n,j)$ for which it holds, e.g. (1,2).
Induction step:
Induction on $n$: assume it holds for $n=k$ and $j=n+1$
, proof it holds for $n=k+1$, $j=n+1$.
- Inner induction: to prove $$E[X]^{n+C}_n = \lambda T \;\;\;\; n=k,C\in\mathbb{N}$$
Base case: Take C=1
Induction step: Assume it holds for $C=x$, prove it holds for $C=x+1$.
My reasoning is that in the outer induction part, the distance between $j-n$ is fixed and we need to prove that for all $n$ and for the same fixed distance this is true. Then, withing this induction part, we need to prove by induction that this holds for a varying distance $j-n$.
Is this correct reasoning?
Best Answer
Your set-up is pretty weird, because the 'inner' induction actually does not depend on the outer induction at all. That is, you don't do the 'inner' induction inside the 'outer' induction, but rather, you end up with two separate inductions:
The 'outer' induction shows that the claim holds for all $(n,n+1)$ (note: you'll have to use the base case $(1,2)$ if you do ... rather than say that you just take some 'arbitrary case')
The 'inner' induction takes some arbitrary $n$, and then shows, by induction, that the claim holds for any $j>n$.
Well ... notice that the latter is sufficient to prove the whole thing!
To be specific, with the 'inner' induction', you end up just do the following:
Take any arbitrary $n$
Now you show by the 'inner' induction that for all $j>n$, the claim holds
But since $n$ was arbitrary, the claim holds for all $n, j>n$
That is, you do a universal proof on $n$, and inside that you induct on $j$, and with that, the whole proof is done!
Indeed, the 'inner' induction is only 'inner' to the universal proof you do on $n$.
This means that the 'outer' induction in not necessary at all!
Indeed, you effectively end up showing all the $(n,n+1)$ cases through the base case of the inner induction. To be precise, when you show that for any arbitrary $n$, the base case of the inner induction holds, you have in effect shown that the claim holds for all $(n,n+1)$.