2

I've noticed something about students versus more mathematically mature people when using induction. When we assume a statement is true for some $k$, i.e. $P(k)$ is true, we then proceed directly from $P(k)$ to $P(k+1)$. Whereas I've noticed in books that writers tend to do it differently; they tend to use the $P(k)$ statement somewhere in the middle, as opposed to starting with it. I'll make this clearer with an example:

I want to prove $$1+2+\ldots + n = n(n+1)/2$$

for all naturals $n$. Base case is obvious, suppose it's true for some $k$. Now from here, I would write down $1 + \ldots + k = k(k+1)/2$, then add $k+1$ to both sides, and derive $P(k+1)$ from there. However, I feel like I've noticed more advanced mathematicians start with $1 + \ldots + (k+1) = (1+\ldots + k) + (k+1)$, then invoke the $P(k)$ statement to get $(1 + \ldots + k) + (k+1) = k(k+1)/2 + (k+1)$, and then proceed from there. Is there anything wrong with my approach? Is there a reason mathematicians prefer the second way, or is that not true?

HK Lee
  • 19,964
Evan
  • 55

2 Answers2

2

All that induction requires you to prove is that $P(k)$ implies $P(k+1)$.

In other words, you assume that $P(k)$ is true, and using that assumption you must prove that $P(k+1)$ is true.

There is no requirement that you must "start with that assumption", nor any requirement that you must "use that assumption in the middle". In fact there is no requirement at all regarding the position in your argument at which you use that assumption. You are free to use that assumption wherever it may be appropriate in your proof (assuming, of course, that the proof in which you use that assumption is a valid proof).

Lee Mosher
  • 120,280
2

If you have a mission to accomplish and your boss sends you out with a tool box, because he knows exactly what you will need along the way, you don't start the mission by taking out the screwdriver when you don't know yet where you will need it.

Your observation is very accurate, and yes, there is a reason behind this phenomenon: more experienced people don't get too excited when they receive a new tool.

Another aspect of it is that students don't always feel fully comfortable with implications, and may feel like the proof of a statement such as "$A\Longrightarrow B$" has to start with $A$, somehow.

Arnaud Mortier
  • 27,276