I'm working through a problem set on mathematical induction. One of the problems asks you to prove that for all $n\in\mathbb N$,
$$\sum_{i=0}^{n}8n-5=4n^2-n.$$
I don't have a problem proving this, but I wondered: What formula relates the coefficients and constants of the summed terms (here, 8 and 5) to the coefficients and constants of the formula for the partial sum (here, 4 and 1)? I've tested several series, and if the summands of the partial sum form a linear progression, as in the above example, it seems that for $a, b \in \mathbb {Z}$,
$$\sum_{i=0}^n (ai+b) = \frac a2n^2+ (\frac a2+b)n, \forall n \in \mathbb N.$$
Of course I've only tested several cases; I understand I haven't proved it for all integers $a,b$. Since there are only these two terms to consider, there are $\mathbb N \times \mathbb N$, or only countably infinitely many, possible combinations of $a$ and $b$. So I thought, "I'll use mathematical induction to prove this!" That plan fell apart pretty quick. My first question is this: Is there a modified version of induction that can be used when we're tossing around more than one variable? Can we use induction to prove not the truth of $P(n)$ $\forall n \in\mathbb N$, but the truth of $P(a_1n, a_2n,…,a_in)$ $\forall a_1, a_2, …, a_i \in \mathbb N,$ $\forall n \in \mathbb N$?
So I thought I'd simplify things by taking out $b$. And to simplify things further still, I'd take $a \in \mathbb N$ instead of $a \in \mathbb Z$. My thinking was, if we can use induction across the rows, we should be able to do the same thing down the column:
$$
\begin {matrix}
& 2 & + & 4 & + & 8 & + & \cdots & + & 2n & = & n^2 & + & n \\
& 3 & + & 6 & + & 9 & + & \cdots & + & 3n & = & \frac 32n^2 & + & \frac 32n \\
& 4 & + & 8 & + & 12 & + & \cdots & + & 4n & = & 2n^2 & + & 2n \\
& \vdots & & \vdots & & \vdots & & & & \vdots & & \vdots & & \vdots \\
& a & + & a\cdot 2 & + & a\cdot 3 & + & \cdots & + & a\cdot n & = & \frac a2n^2 & + & \frac a2n \\
\end {matrix}
$$
My second question is: This doesn't work either, does it? There's not a way to apply induction down the column. That is, the true of $\sum_{i=0}^n 2i=n^2+n$ doesn't imply the truth of $\sum_{i=0}^n 3i= \frac 32n^2+ \frac 32n$, right? There's not a way to go from $P(a) \rightarrow P(a+1)$, is there?
My last question is, So how can we prove this?
Best Answer
Firstly, for this particular example, you actually don't need to do induction with several variables: the sum is linear and can be separated to two separate sums, each of whose values you know (or can get by induction on one variable). $$\sum_{i=0}^n(ai+b) = a\sum_{i=0}^ni + b\sum_{i=0}^n1$$
Also, when you have multiple variables which affect the truth of the proposition, one thing you can do is to not induct on the variables themselves, but on a function of the variables, i.e. $f$ where $f$ is a function of all the variables to $\mathbb N$. This can be done, for example, in the proof of the existence of the GCD and in Bezout's Lemma (inducting on $a+b$).
In the above example, you can induct on $f(a, b) = |a| + |b|$ which goes to natural numbers (and hence is a valid quantity to induct on).
Apart from this, if you want to actually induct on more than one variable, that's possible too. But I believe it would get very messy beyond two variables, though two is sometimes done.