Trying to learn the basics of series of sums and proof by induction

Question

I'm trying to get better at writing recursive algorithms and the book I'm studying with ("Thinking Recursively with Java") goes into a discussion of inductive proofs in Chapter 2.

An introduction to inductive proofs provides as datum:

$1 + 2 + 3 + ... + n = \frac{(n)(n+1)}{2}$

Well, OK, that's very interesting as datum and I saw how to use it as a component in the inductive proof. But the essential thing is that I don't know how to generate a similar insight on my own once things move to a slightly more advanced level.

The "homework" asks us to write the series for the sum of all even numbers. I've tried to attack the problem and by, more or less, a guess-and-check method I came up with a series of calculations that seems to suggest a formula.

n  n*2 n**2 + n
----------------
1  2   2
2  4   6
3  6   12
4  8   20
5  10  30
6  12  42
7  14  56
8  16  72
9  18  90
10 20  110

So that led me to believe that:

$2 + 4 + 6 + ... + 2n = (n^2 + n)$

Am I already off in the weeds? It seems to work based on my table, supra. Is there any way to come to this insight other than writing some Ruby to generate a table? Or am I participating in a historical empathy lesson: trying to reason with small stones like the ancients?

Under the (seemingly mistaken) belief that I did the first part right, I tried to do an inductive proof, but some things here bothered me. First why couldn't I use $n=1$? The part that makes the value even is my $2n$. So if I choose $n=1$ whereby to prove the claim, then it (obviously) doesn't work. How do you get would-be mathematicians to agree to a constraint set?

But in order to make my life easy, I assumed $n=2$ and, as predicted by the formula and table, got $6$. I then tried to pass in $(n + 1)$ into the formula and, well, I didn't know how to proceed. The example given didn't have an explanation about how to deal with a complex term (i.e. $2n$) so I wasn't sure how to proceed. I figured that I must have screwed up at an earlier phase and that I probably needed some help in formulating my "given" statement better.

Can anyone help me get on the right track with this? I'd even take a book or a chapter recommendation that would help me to build this intuition. My goal is growth, not the right answer (well, OK, it's both) but I want to appreciate the method as well as the result.

Thanks for your consideration of a math-bumbler muddling up your SE forum :)

Answer 1

The thing about induction is that it's only useful for proving the result of the thing you're trying to prove and not so useful for arriving at the result. For example, we know that the sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$ and we can use induction to prove that, but how does one arrive at $\frac{n(n+1)}{2}$ in the first place?

Suppose that we didn't know what the sum of the first $n$ natural numbers are. We could guess that perhaps it's a quadratic function (just by looking at the sum of the first few sums, the formula is clearly not linear and it seems that a cubic function might grow a bit too fast). So let us suppose that the sum of the first $n$ natural numbers is given by $f(n)$ and that,

$$f(n) = An^2+Bn+C,$$

for some integers $A, B, C.$

We see that sum of the first natural is just $1$. Plugging into our formula, we get: $$1 = f(1) = A(1)^2+B(1)+C = A+B+C.$$

The sum of the first two natural numbers is $1+2 = 3$. Plugging into our formula, $$3 = f(2) = A(2)^2+B(2)+C = 4A+2B+C.$$

The sum of the first three natural numbers is $1+2+3 = 6$. Plugging into our formula, $$6 = f(3) = A(3)^2+B(3)+C = 9A+3B+C.$$

Notice that now we have a system of three linear equations with three variables: $$A+B+C = 1$$ $$4A+2B+C = 3$$ $$9A+3B+C = 6$$

Solving this system yields $A = \frac{1}{2}$, $B = \frac{1}{2}$, and $C=0$ which means that our function is given by, $$f(n) = An^2+Bn+C = \frac{1}{2}n^2+\frac{1}{2}n+0 = \frac{n(n+1)}{2}.$$

Note that this does not prove that $f(n)$ is actually $\frac{n(n+1)}{2}$. We've shown that if the function $f$ is quadratic, then it must be equal to $\frac{n(n+1)}{2}$. But at least we now have a formula to work with and we can use mathematical induction to actually prove the result (whereas our work earlier allowed us to obtain the result.)

Answer 2

You are trying to find a formula for the sum of the first $n$ even numbers: $2+4+\cdots+(2n-2)+2n$. If you notice that this sum can be written as $2(1+2+\cdots+(n-1)+n)$, then you can use your earlier result to get $2 \cdot \frac{n(n+1)}{2} = n(n+1)=n^2+n$ which is what you had.

However, if you want to do this from scratch using in induction, here is how you set it up. If you choose your base case to be $n=1$ then you are done: the sum of the first "one" even number is $2$, which is $n^2+n=1+1=2$. If you want to instead use the base case $n=2$, then the sum of the first two even numbers is $2+4=6$ which is $2^2+2=6$.

So, we have assumed $$2+4+\cdots+2n=n^2+n\tag{$*$}$$ is true for some particular $n$, and we want to prove the analogous statement for $n+1$, that is, we want to prove $$2+4+\cdots+2n+(2n+2) = (n+1)^2+(n+1).$$ Well, using ($*$) we have \begin{align} [2+4+\cdots+2n]+(2n+2) &= (n^2+n) + 2n+2\\ &= (n^2+2n+1) + (n+1)\\ &= (n+1)^2+(n+1). \end{align}

Answer 3

Of course, you could find the answer in this case by simply multiplying both sides of the example by 2. However I don't think this would be instructive or illuminating.

First, keep in mind that induction frequently doesn't show "why" things are true in the elegant way you may be used to with deductive proofs. You just use the machinery as instructed, and out comes the result.

Induction however is a good tool for proving hypotheses, when you don't really know why they hold. The other benefit with induction, is it's very well suited to recursive algorithms (which are common in computer science).

Answer 4

Here is my general template for proof by induction.

I usually start writing it down before I even know the answer.

It always seems to work for me, so I hope that it will work for you.

---

First, show that this is true for $n=1$:

$\sum\limits_{k=1}^{1}2k=1^2+1$

Second, assume that this is true for $n$:

$\sum\limits_{k=1}^{n}2k=n^2+n$

Third, prove that this is true for $n+1$:

$\sum\limits_{k=1}^{n+1}2k=$

$\color\red{\sum\limits_{k=1}^{n}2k}+2(n+1)=$

$\color\red{n^2+n}+2(n+1)=$

$(n+1)^2+(n+1)$

---

Please note that the assumption is used only in the part marked red.