Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Ah-ha! I would never have thought to separate the sums. And thanks for adding the Bezout's Lemma example. –  Ryan Apr 7 at 3:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.