3
$\begingroup$

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!

$\endgroup$
14
  • 47
    $\begingroup$ Because before proving an identity you must have an identity. $\endgroup$ Commented May 9, 2019 at 16:38
  • 5
    $\begingroup$ Why doesn't your second example involve guessing in your opinion? It seems to me that when using induction you always have to guess the solution first (which is reflected by the need of an induction hypothesis). $\endgroup$
    – asdq
    Commented May 9, 2019 at 16:41
  • 7
    $\begingroup$ You can use the calculus of finite differences to evaluate such sums in a systematic way, just as integrals are evaluated systematically in calculus. $\endgroup$
    – littleO
    Commented May 9, 2019 at 16:42
  • 2
    $\begingroup$ Suggested change of question to more broadly consider any sort of induction problem, since the issue here is about induction and not so much about sums from what I gather. $\endgroup$ Commented May 9, 2019 at 16:53
  • 3
    $\begingroup$ I don't see what this question has to do with induction at all. You simply ask for deriving vs. proving an equality/inequality. If you have a right side (guessed or however), you can prove it. If you have none, there is nothing to prove. In the first example you say "what if I don't know the right side, how to find it with induction?". But the question works on the second example too. You (for some reason) just assume that you are already given the right side in the second example. So the difference between the examples are your assumptions about what is given to you. $\endgroup$
    – M. Winter
    Commented May 10, 2019 at 6:41

7 Answers 7

31
$\begingroup$

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.

$\endgroup$
14
  • 9
    $\begingroup$ Morally speaking? And what do you mean to derive the closed form through the process of induction? Deriving something implies it came from somewhere, but where did it come from, for you to begin to use induction on it? $\endgroup$ Commented May 9, 2019 at 16:56
  • 2
    $\begingroup$ What does "find theorems" even mean? Generally speaking, one does not simply stumble upon a theorem. You say that "in the process of finding the theorem, you discover why it is true", but in my answer, I give a pretty clear example of when you might believe something might be true, without having proven it at all. $\endgroup$ Commented May 10, 2019 at 11:47
  • 1
    $\begingroup$ "Using empirical induction to guess a formula is useless because it gives you no information." This is absolutely wrong. If you mean that this guess is nothing more than a guess until I have proven it, then yes, that is certainly true. And to fix that, you can use induction. Even if said guess is wrong, you can gain a better understanding of the problem by figuring out why it's wrong, and possibly realize how to make it right. I've faced countless problems where I've had to guess a formula or inequality off of intuition, and then proceed to prove it using induction. $\endgroup$ Commented May 10, 2019 at 14:08
  • 4
    $\begingroup$ And that's why it's nothing more than a guess? You seem to be completely ignoring the fact that after you make a conjecture, you can prove it with induction. $\endgroup$ Commented May 10, 2019 at 14:36
  • 2
    $\begingroup$ I think this answer could be improved by showing how induction can be useful to "find the theorem", even if you of only have a small amount of intuition. If you have the sum $\sum_{k=1}^n (5k+12)$ there is (for most people) no easy intuition of what it might equal exactly. If you have the intuition that it probably is a polynomial, then you already have enough intuition to prove it with induction! (As long as you guess that the degree of the polynomial is at least 2.) $\endgroup$
    – DrPhil
    Commented May 10, 2019 at 21:28
12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ If you must derive the sum without induction then you don't really need induction to prove it do you $\endgroup$
    – Fomalhaut
    Commented May 9, 2019 at 17:03
  • 3
    $\begingroup$ @ErotemeObelus Well, yes and no. The key here is that sometimes you can derive the sum without induction, and then yes you don't need induction to prove it. But given a sum, you can always guess a POTENTIAL answer, and then try to prove it by induction. If your guess is right, the problem usually becomes easy once you apply induction. If the guess is wrong, you'll see when doing the induction that it is wrong. And then, make another guess. Noyte that until proving it, your guess is just a guess. $\endgroup$
    – N. S.
    Commented May 9, 2019 at 17:06
  • $\begingroup$ @ErotemeObelus To understand the difference, just look at $\sum_{k=1}^n k^3$. You can calcualte this sum without induction, but unless you seen the technique before it is very tricky... Just try it yourself.. With induction here is how one would proceed $$\sum_{k=1}^1 k^3=1\\ \sum_{k=1}^2 k^3=9 \\ \sum_{k=1}^3 k^3=36 \\ \sum_{k=1}^4 k^3=100$$ You should imediately recognize that all these numbers are prefect squares and then see that $$\sum_{k=1}^1 k^3=1^2\\ \sum_{k=1}^2 k^3=3^2 \\ \sum_{k=1}^3 k^3=6^2 \\ \sum_{k=1}^4 k^3=10^2$$ At this point, if you are familiar with triangular numbers $\endgroup$
    – N. S.
    Commented May 9, 2019 at 17:12
  • $\begingroup$ if note, you either calculate few more terms, or just stare at them until you observe the somewhat obvious pattern, especially if you also calcualte $mn=5,6..$: $$3-1=2 \\6-3=3\\10-6 =4 \\15-10=5\\21-15=6$$ At the end of the day, guessing the right formula here and then proving it by induction is easier and faster than proving it without induction.... Of course in some problems guessing can be really tricky, but those are not good induction sum problems ;) Don't expect every sum to be easy to guess and prove by induction, that would make many areas of mathematics very easy. $\endgroup$
    – N. S.
    Commented May 9, 2019 at 17:14
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is there a good reason why sums are much more difficult than other inductive cases? Yes you said "sums are as difficult as antiderivatives" (I strongly agree) but what is the reason for this? $\endgroup$
    – Fomalhaut
    Commented May 9, 2019 at 16:56
  • $\begingroup$ See my edited answer. $\endgroup$
    – J.G.
    Commented May 9, 2019 at 17:00
  • $\begingroup$ From what your answer looks like, it appears you are going for the argument that symmetric (in)equations are easier since they usually boil down to the 2-variable case, while other problems have the inductive step usually depending on $n$. $\endgroup$ Commented May 9, 2019 at 17:01
8
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Fomalhaut
    Commented May 9, 2019 at 21:30
  • $\begingroup$ Induction is a proof technique. As long as it is consistent with the other proof techniques, it is valid. Sure, induction won't help you find a theorem. But that's because it's YOUR job to find the theorems. $\endgroup$
    – nomen
    Commented May 10, 2019 at 13:54
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .