Why can't I prove summation identities without guessing?

Question

In order to prove using induction that

$$\sum_{k = 1}^n k = \frac{n(n+1)}{2}$$

I have to first guess what the sum is and then show that this guess bears out using induction. This is very unusual for induction proofs. The proof by induction of the generalized triangle inequality

$$\sum_{k = 1}^n |x_k| \geq \left|\sum_{k = 1}^n x_k\right|$$

requires no such guessing. Why can't I prove summation identities the same way I prove the triangle inequality?

Some have said that "the problem is that you can't use mathematical induction to find theorems; you can only use it to prove theorems." But like pushing a bump in the rug which causes it to reappear elsewhere, this introduces another problem: if mathematical induction can't find theorems, then it's self-defeating. Why? Because in the process of finding the theorem, you discover why it is true (and find a proof as a side-effect) which makes proving by induction redundant!

Answer 1

I have to first guess what the sum is and then show that this guess bears out using induction.

[...]

if mathematical induction can't find theorems, then it's self-defeating. Why? Because in the process of finding the theorem, you discover why it is true (and find a proof as a side-effect) which makes proving by induction redundant!

Induction will require some guessing, in the same way that finding any proof will require some guessing. In both cases the guessing can be way more efficient with some intuition/luck/prior knowledge. We don't know of any efficient way of finding proofs for theorems in general.

---

Here is some intuition that will help you make more efficient guesses when finding closed forms of sums of polynomials. $$\sum_{k=1}^n (5k + 12)$$ It might seem very difficult to first guess the closed form of this sum and then prove it with induction. (To be fair, it seems difficult to find a visual proof as well!) We don't need to guess the exact closed form, a vague guess is often just as good.

We can guess that the closed form is a polynomial of degree 3 (if we are unsure we can guess an even higher order polynomial). Here's what that will look like:

$$\sum_{k=1}^n (5k + 12) \stackrel?= an^3 + bn^2 + cn + d$$ For the induction we will want to show that it holds in the base case $n=0$, which means that $d=0$. Let's call the sum $p(n)$ for short. For the induction step we get that $$p(n+1) = p(n) + 5(n+1) + 12$$ which with our assumption that $p(n) = a^3 + bn^2 + cn$ will mean: $$a(n+1)^3 + b(n+1)^2 + c(n+1) = a^3 + bn^2 + cn + 5n + 17$$ Now we just need to solve this equation. One way would be to look at each degree separately, giving us:

$\displaystyle n^0: \quad a + b + c = 17$

$\displaystyle n^1: \quad 3a + 2b + c = c + 5$

$\displaystyle n^2: \quad 3a + b = b$

$\displaystyle n^3: \quad a = a$

From the second degree terms we see that $a=0$. This means that the first degree terms show that $b = \frac{5}{2}$ and finally we see that $c = \frac{29}{2}$. This means we with induction have found the theorem and proven that

$$\sum_{k=1}^n (5k + 12) = \frac{5}{2}n^2 + \frac{29}{2}n$$

from only the intuition that the right hand side should probably be a polynomial. With some better intuition we would have guessed that it was a 2-degree polynomial and saved us some time.

Answer 2

Note that there is a difference between

Prove that $\displaystyle\sum_{k=1}^nk=\frac{n(n+1)}2$ by induction.

and

Derive a closed form for $\displaystyle\sum_{k=1}^nk$.

The former tells you what to use induction on, while the latter does not. In the case of the second problem, note that induction is not required. However, induction may be used. A good example of when I would do such might be in this problem:

Derive a closed form for $\displaystyle\sum_{k=1}^n(2k-1)$.

Often times, whether it be discrete or continuous, checking how some cases work out, either by writing out a few values or plotting on a graph, can be very helpful for intuition. In this problem, you can see the first few terms are given as:

$\displaystyle\sum_{k=1}^1(2k-1)=1$

$\displaystyle\sum_{k=1}^2(2k-1)=4$

$\displaystyle\sum_{k=1}^3(2k-1)=9$

$\displaystyle\sum_{k=1}^4(2k-1)=16$

which my intuition tells me that we most likely have

$\displaystyle\sum_{k=1}^n(2k-1)\stackrel?=n^2$

to which I would then apply induction. If this was not clear to me, I would probably use some other method to evaluate this.

The key idea is that, yes, there is a guess involved. This guess may be wrong or right. But the guess is not blind, rather it is an educated guess. You can write out a few terms to see what you want your guess to be. And induction is not the only method by which you can prove things, there's plenty of other approaches to any given problem.

Answer 3

Proofs of inequalities by induction often use the $n=2$ case for the inductive step, so knowing that case automatically makes you know the general result. In particular, it's the kind of reasoning a normal person would achieve, albeit in an unclear form, if they'd never heard of "proof by induction". They wouldn't even need to be told what to try to prove. In this case, the result is essentially that the shortest path between two points on a line involves no double-backing.

Sums, on the other hand, are about as difficult to figure out as antiderivatives, and for much the same reason (integration is to continuous problems what addition is to discrete ones) - and of course, that's very hard. In fact, one way to state a proof by induction of a sum - by checking the difference between consecutive partial sums takes the desired value, so the sum telescopes - closely mirrors the use of differentiation to double-check a putative antiderivative. (Fun fact: the odd antiderivative of $\sec x$ was correctly conjectured before the fundamental theorem of calculus had been proven, so it couldn't be checked the way we'd do it today. It's as if they couldn't do the inductive step in a discrete problem.)

The need to know the conjecture before you can prove it is one obvious downside of induction, when the downside applies. Luckily, you can often guess the answer easily enough by trying the first few values. So you could also think of induction as a way to automate the conversion of a guess from examples to a proof. The name similarity to induction in philosophy isn't all that inappropriate.

Now, sometimes it's a lot harder. If I asked you to evaluate $\sum_{k=1}^n kx^k$ by jumping straight into induction, you probably wouldn't guess the right conjecture to start an inductive proof. However, just about any strategy you'd use instead of that would build on an easy inductive result. (For example, can you work out $\sum_{k=1}^n x^k$ by the guess-then-verify technique? I bet you can. Now just apply $x\partial_x$.) So the "easy" way to turn the induction handle is more powerful than it seems at first. As with many techniques, induction is very simple in theory but potentially very hard to use in practice; it often comes down to knowing which claim to prove for all $n$. But don't worry: it's not just induction that can be easier if you try to prove more.

Answer 4

The reason why you cannot prove the statement by induction withpout guessing is because there is nothing to prove:

Just look for example at $$\sum_{k=1}^n k^2$$

If you don't guess what the sum is, what are you proving by induction? What is your induction statement? Is that the sum is unknown?

As for the reason why the second involves no guessing is because you already have both sides.

Note that the second relation is an inequality, the first is an equality after guessing. The two problems are similar/comparable only after you make the right guess. Before that, you are comparing two completely different type of problems and wonder why a tool only works for one...

Now, what you probably wonder is why the first type of problem is given in an incomplete form (i.e. not a complete equality), while the second must be given in complete form...This is actually what makes the two problems different.

The answer is actually simple: Given a sum, there is an unique closed form which can be equal to your sum. For an inequality, there are infinitely many ways to complete it, and some make the problem much easier. That's why we need both sides.

Just to emphasize the last point, assume that an inequality is given as a guess: Prove by inducton that $$\sum_{k = 1}^n |x_k| \geq ??$$

Now, what is the logical RHS? Is it the one from the question posted by you? Is it $0$? Is it $-2019$?

What about $$\sum_{k = 1}^n |x_k| \geq \left|x_1-x_2+x_3-x_4+...\right|$$

or $$\sum_{k = 1}^n |x_k| \geq \sqrt[n]{\prod_{k=1}^n \left|x_k\right|}$$

All of those are true inequalities, some are easier than others. But all of them are completely different problems.

Answer 5

You seem to want to ask about how we can guess the correct formula for a general summation. For summation of perfect powers, or in general polynomials, see this post which explains a very efficient method to derive the closed-formula without any guessing whatsoever.

However, expressions can be hard to simplify even if you know it can be simplified. For example, you can prove that $F_{n-1} F_{n+1} - {F_n}^2 = (-1)^n$ by induction, where $F_n$ is the $n$-th fibonacci number, but if I simply asked you to simplify $F_{n-1} F_{n+1} - {F_n}^2$ without guessing the pattern, it is harder. It can be done, and the algebraic proof is very elegant, but you need mathematical insight.

Also, there is an inherent complexity in some theorems that can only be proven using induction, in a precise technical sense. For example, some theorems that can be proven by PA or ACA0 must use an induction axiom, and by this I mean that we can prove that it cannot be proven without using any induction axiom. In this post you can find two examples of such theorems, including the well-known facts:

• Every natural number is either a multiple of two or one more than a multiple of two.
• There is no ratio of positive integers whose square is two.

There is a field of mathematics called Reverse Mathematics that studies finer distinctions, such as how much induction is needed. Many high-school problems can be solved using quantifier-free induction. These same problems often can be proven algebraically in a manner that hides the induction, say via telescoping. For instance, $\sum_{k=1}^n (6k^2+2) = \sum_{k=1}^n \big( (k+1)^3-(k-1)^3 \big)$. But there is no easy systematic way to find such telescoping sums.

Answer 6

Theorem discovery and proof are simply different processes. Quoting from Rosen, Discrete Mathematics and its Applications, 7th Edition, Sec. 5.1, "The Good and the Bad of Mathematical Induction":

An important point needs to be made about mathematical induction before we commence a study of its use. The good thing about mathematical induction is that it can be used to prove a conjecture once it is has been made (and is true). The bad thing about it is that it cannot be used to find new theorems. Mathematicians sometimes find proofs by mathematical induction unsatisfying because they do not provide insights as to why theorems are true. Many theorems can be proved in many ways, including by mathematical induction. Proofs of these theorems by methods other than mathematical induction are often preferred because of the insights they bring.

And, in a sidebar:

You can prove a theorem by mathematical induction even if you do not have the slightest idea why it is true!

Answer 7

There are already several great answers here, but I wish to append my thoughts to the points made by Daniel R. Collins, specifically in regard to ErotemeObelus's statement

"The problem is that if mathematical induction can't find theorems, then it's self-defeating. Why? Because in the process of finding the theorem, you discover why it is true (and find a proof as a side-effect) making proving by induction redundant."

which is included both in the original question and as a comment in response to Collins's answer.

Mathematical Statements, Mathematical Proof, and Mathematical Discovery

As Collins noted, discovering a mathematical fact and proving a mathematical fact are different tasks. In a mathematical proof, the objective is to take a clear, precisely articulated mathematical statement, consisting of some number of hypotheses and some number of conclusions, and rigorously show that the hypotheses imply the conclusions. ErotemeObelus already gave several examples of such statements in his question:

1) Let $n$ be a positive integer (hypothesis). Then $\sum_{k = 1}^n k = \frac{n(n+1)}{2}$ (conclusion). In this case, the conclusion is of the form $A=B$, where $A$ and $B$ are prima facie different--here the sum of all the integers up to $n$ and the product $\frac{n(n+1)}{2}$. The unexpected equivalence of these two objects is what makes the statement nontrivial.

2) Let $x_1,\dots,x_n$ be real numbers (hypothesis). Then $\sum_{k = 1}^n |x_k| \geq \left|\sum_{k = 1}^n x_k\right|$ (conclusion). In this case, the conclusion is of the form $A \geq B$. For general statements of this kind, the unexpected ordering of $A$ and $B$ in this way is what makes the statement nontrivial (although in this case it is easy to understand intuitively why the statement is true).

These are of course both simple examples of mathematical statements, with only one hypothesis and one conclusion. In general, mathematical statements can have several hypotheses and several conclusions.

Only once you have a precise mathematical statement can you have a proof. A proof is a rigorous (meaning logically air-tight) argument that shows that if the hypotheses of the statement are true, then the conclusion is also true. There are different ways to make such an argument, but all of them are ultimately based on a small number of standard techniques. Induction is one of those techniques (although its philosophical treatment is much more nuanced than other techniques--say, for example, contradiction--that follow directly from basic logic). Therefore, whenever you apply induction, you are necessarily using it to construct a mathematical proof, which presumes that you have a mathematical statement to prove.

Now let's look at mathematical discovery. In mathematical discovery, the objective is to create a mathematical statement that you believe to be true. Such a statement is called a conjecture, and its truth is unknown until it is proven. Mathematical discovery is a far less systematized task than mathematical proof. It relies on intuition, plausible reasoning, visualization, analogies, sudden flashes of insight, and even claims of divine intervention (whatever you choose to make of that). A classic book that examines mathematical discovery is G. Polya's Mathematics and Plausible Reasoning (Vol. 1 and Vol. 2).

One thing which is certainly NOT the case is that in the process of making a conjecture you necessarily discover why it's true or even that it is true. Many conjectures are simply educated guesses. Many turn out to be wrong. All of them need to be proven before they can be promoted to the status of theorems (propositions, lemmas, etc.) in mathematics. This is actually the first mistake ErotemeObelus makes--you do not find theorems, you find/make conjectures. If you can prove a conjecture, then it becomes a theorem, but not before.

Is Induction Self-Defeating or Redundant?

No. Induction is a method of proof, not a method of discovery. As we have discussed, methods of discovery are much less systematic than methods of proof. For example, you might guess the sum $\sum_{k = 1}^n k$ by writing out the first few terms. You might guess it by using Gauss's trick of starting with an even $n$ and writing the first half of the terms in ascending order, then the second half on the next line in descending order. But even the latter technique, though ingenious, is not a proof, because it is not a rigorous argument. Therefore, your conjecture--though quite plausible--is not yet a theorem. Here we find the purpose of induction as a method of proof for your conjecture. Thus it is neither self-defeating nor redundant. It is simply directed toward a different task than the task to which ErotemeObelus would like to direct it.