I'm trying to understand an induction proof in a book ("Geometry of Banach spaces, duality mappings and nonlinear problems" by I. Cioranescu, page 202). The theorem goes like this:
For $m,n \in \mathbb{N}$ with $m\leq n$ and $\alpha, \beta >0$ let $a_{k,j} \in \mathbb{R}$ where $0\leq k\leq m, 0\leq j\leq n$ be such that: $$a_{k,j} \leq \alpha a_{k-1,j-1} +\beta a_{k,j-1}$$ Then it holds that: $$a_{m,n}\leq \sum_{j=0}^{m-1} \alpha^j \beta^{n-j} \binom{n}{j} a_{m-j,0} + \sum_{j=m}^n \alpha^m \beta^{j-m}\binom{j-1}{m-1}a_{0,n-j}$$
The author proves this by some sort of double(?) induction. First he proves that for $m=1$ it holds that:
$$a_{1,n}\leq \beta^n a_{1,0} +\sum_{j=1}^n \alpha \beta^{j-1}a_{0,n-j}$$
for all $n$. Then he shows that if $m\leq n$ and the statement in the proof holds for $a_{m,n}$ then it holds for $a_{m,n+1}$.
I feel like one should have to show it for each $m$ as well I mean: If it holds for $m\leq n$ then it holds for $m+1 \leq n$. Why is this not a necessary step in this case?
Yeah, that's weird.
Let me first point out that even though you have two variables, there is no need to do induction for both, and you can do induction for just one of them, as long as you show that the theorem holds for any value for the other variable (for which you might be able to do a straight-up universal proof). I get the impression that this is what the author was trying to do.
However, the author is then using $m=1$ as a base case (but generalizes over all $n$) but then does the inductive step on $n$ ... that's definitely not sufficient. The author probably should have started with $n=1$ as a base case (and that should be easy to show for any $m \le n$), rather than $m=1$. And with that as a base case, and with the step going from $n$ to $n+1$, as long as the author did indeed show the step to hold for any $m \le n+1$, it would be a complete proof.