Etydhv

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 $xpartial_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.

Note that there is a difference between

Prove that $displaystylesum_k=1^nk=fracn(n+1)2$ by induction.

and

Derive a closed form for $displaystylesum_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 $displaystylesum_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:

$displaystylesum_k=1^1(2k-1)=1$

$displaystylesum_k=1^2(2k-1)=4$

$displaystylesum_k=1^3(2k-1)=9$

$displaystylesum_k=1^4(2k-1)=16$

which my intuition tells me that we most likely have

$displaystylesum_k=1^n(2k-1)=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.

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$$

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

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!

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.