0
$\begingroup$

This question already has an answer here:

I'm currently learning mathematical induction from this site: https://www.mathsisfun.com/algebra/mathematical-induction.html

What I'm confused about is how it presents mathematical induction. It says that there are 3 steps to induction:

  • Show it true for $n=1$.
  • Assume it is true for $n=k$
  • Prove it is true for $n=k+1$ (we can use the $n=k$ case as a fact.)

There are many things I am confused about here, about all $3$ steps.

Starting from the first step, why is it necessary to prove it true for $n=1$? I don't get why this step is needed. Second, why choose $1$ of all numbers; can't a number like $2$ be chosen?

Moving on to the second step, why is it legitimate to assume it true for all $n=k$? Is this assumption proved true by the third step, if so, how?

On the final step, first, how can we prove it true for all $n=k+1$ ? Because this prove fundamentally assumes that it is true for $n=k$, but there is no way to verify this. Second, what happens if the set we're doing induction on has only a limited amount of numbers, let's say 100 numbers. So if we go up to the 100th number, then how can $n=k+1$ still be true? Because there is no 101st term for it to be true on; there are only 100 numbers!

Please explain this as simply as possible; I'm still a beginner. I will not be able to understand complicated proof notation.

DETAILS: This question is different from the question above since the question above uses $\lim_{x\to\infty}$ notation and other pieces of calculus knowledge. However, I have not learnt calculus, and nothing about this question suggest prior calculus knowledge. An answer where induction is explained without calculus would benefit me greatly.

$\endgroup$

marked as duplicate by Hans Lundmark, Namaste algebra-precalculus Jun 30 '18 at 15:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ If it helps I'd like to provide a cheap but effective example :) Imagine you're standing in a row of 100 people. The rule is at any time if a person "k" slaps himself, the next person "k+1" must also slap himself. Lets say the first person slaps himself - With just this information, is it conclusive that everyone in the row got a slap ? $\endgroup$ – rsadhvika Jun 30 '18 at 12:55
  • 1
    $\begingroup$ Maybe I should rephrase the rule : Whenever a person slaps himself, the person standing next to him also slaps himself. $\endgroup$ – rsadhvika Jun 30 '18 at 13:21
  • 1
    $\begingroup$ @EthanChan we're only dealing with natural numbers here. Also "you need to make sure" that "k+1" slaps himself if/when "k" slaps himself. This is not a given, you need to prove it. $\endgroup$ – rsadhvika Jun 30 '18 at 13:30
  • 1
    $\begingroup$ Firstly, it is not necessary to start from $n=1$, but only for a base $n_0$ for which the statement is true for each natural number $n \ge n_0$. As an example, the statement may be false for $n = 1, 2, 3$ but true for all $n \ge 4$. Secondly, for the inductive hypothesis (and after), we are only concerned with the case that, if we assume $P(k)$ is true then this implies that $P(k+1)$ is also true, and not necessarily with the factual truth of $P(k)$. But if $P(k) \Rightarrow P(k+1)$, then if $P(k)$ is factually true, then so is $P(k+1)$. $\endgroup$ – Winter Soldier Jun 30 '18 at 13:38
  • 1
    $\begingroup$ @rsadhvika Oh, so we prove it's true for 1. And then since there is 1 person that slaps himself, then the next person would slap himself, and so on and so on. But then, I have 3 more questions. First, why choose 1, of all numbers? Can't we choose any other numbers? Second, why can we only limit ourselves to natural numbers. Last, what happens when we're doing induction in a set with limited numbers. Like here, if we go up to the 100th person, then how can n=k+1 still be true? Because there is no 101st person for it to be true on; there are only 100 people! $\endgroup$ – Ethan Chan Jun 30 '18 at 13:39
1
$\begingroup$

To start from the end. You ask:

[W]hat happens if the set we're doing induction on has only a limited amount of numbers[?]

The first thing to note is that the axiom of induction is useful for proving that a statement holds for infinitely many objects. To show that something is true only a finite number of times, one often uses other means -- and, as a last resort, brute calculation (a famous proof that uses this as one of its major steps is the Four-Colour Theorem).

You also say:

[H]ow can we prove it true for all $n=k+1$? Because this prove fundamentally assumes that it is true for $n=k$, but there is no way to verify this.

The point is not verification. We are assuming that the statement holds for the $k$th item in order to prove that it would then hold for the next, namely the $k+1$th item. Indeed, a contemporary way to look at the practice of mathematics is as trying to deduce implications of axioms and definitions (which no one can guarantee to be true or not, or to even have any specific, intrinsic meaning -- in other words, mathematics does not concern the truth of axioms per se, but correct implications of whatever axioms and conventions we make; this is what we mean by saying a statement is true in mathematics -- it follows logically from the axioms, definitions, conventions and other theorems).

Then:

[W]hy is it legitimate to assume it true for all $n=k$? Is this assumption proved true by the third step, if so, how?

First, the assumption is not proved by the third step. As to why it is legitimate to make the assumption. Well, that depends on what you mean by legitimate. I mean, that's what happens in mathematics all the time: We assume that some hypotheses hold, then we deduce some implications from this assumption.

Finally:

[W]hy is it necessary to prove it true for $n=1$? I don't get why this step is needed. Second, why choose $1$ of all numbers; can't a number like $2$ be chosen?

You need to understand the goal of this principle. Again, we want to show that a statement holds for an infinite list of objects. To do this we have to label the objects to talk about them. We use the positive integers $1,2,3,4,...$ for this, usually. However, if it is convenient for you, you could start with any other positive integer -- indeed with any integer at all. But usually however, it is always easiest to start with $n=1$ (and sometimes $n=0$). However there is no rigidity about this. The thing is, whatever integer you start with, whether you count either forwards or backwards matters little (however, we're most accustomed to counting forwards from $1$; hence we index our set of objects using the positive integers).

A final word: The goal of this method of proof is to show that if we are guaranteed that whenever $P(k)$ holds, then $P(k+1)$ must follow, then if we can only demonstrate that $P(n)$ is true for the first object, then it would follow that it holds for the next, namely the second, which would imply that it holds for the third, etc., from which it follows that it holds for them all, infinite though they be -- since the next is always true.

$\endgroup$
0
$\begingroup$

Let us try to prove e.g. that the following statement is true for $n=1,2,3,\dots$:$$1+2+3+\cdots+n=\frac12n(n+1)\tag1$$

First we proof this to be true for $n=1$ (as stated in the first bullet in your question).

That is just a matter of verifying that: $1=\frac12\cdot1\cdot2$

So if we abbreviate $(1)$ by $P(n)$ this is a verification of: $$P(1)\text{ is true}\tag2$$

What is said under the second and third bullet in your question can actually be summarized as:$$\text{Prove for every }k\text{ that - if }P(k)\text{ is true }\text{ - then also }P(k+1)\text{ is true }\tag3$$

How to do that? Well, by assuming that $P(k)$ is indeed true for some fixed $k$ (second bullet in question) and then (try to) prove that on that base it can be shown that $P(k+1)$ is also true (third bullet in your question).

Suppose that you managed to prove $(2)$ and $(3)$.

Then $P(1)$ is true, and $(3)$ assures us that from this we are allowed to conclude that also $P(2)$ is true.

But then again $(3)$ assures us that also $P(3)$ is true.

But then again $(3)$ assures us that also $P(4)$ is true.

But then again $(3)$ assures us that also $P(5)$ is true.

Et cetera. And summarizing this we conclude that $P(n)$ is true for all $n=1,2,3,4,\dots$.


If things are still unclear for you, then let me know.

$\endgroup$
0
$\begingroup$

Well, take it starting from 2nd step:

  • If it is true for $n$ then it is true for $n+1$ (and thus $n+2,\cdots$)

That is, we do not know if it is true for $n$, but if it is (assumption) then...

Told in other terms, in the step above we are just proving only the relation $$ \left\{ \matrix{ P(n) = TRUE \Rightarrow P(n + 1) = TRUE \hfill \cr P(n) = FALSE \Rightarrow P(n + 1) = ? \hfill \cr} \right. $$ where $P(n)$ indicates any assertion made on $n$ (e.g. "$n$ is greater than $2$", "$n$ is integer",...) and the symbol $\Rightarrow$ stands for "implies", or "if .. then".

And the relation is independent from the assertion in itself, whether it is true or not.

In demonstrating this cascade relation, however, we shall also fix the range of $n$ for which it is true: it is possible that for certain values of $n$ the cascade does not hold.

Once the above is acquired, then we move to find a possible first case in which the hypothesis is true (and no more an assumption), within the said range of validity. We start with the lowest values of $n$, which could be $0$ or $1$ or $2$: call it $n_0$.
Then we know that if it is true for $n_0$, it is also true for $n_0+1,n_0+2,\cdots$.

As a ultra-simple example, suppose that we want to demonstrate that $2<5$.

  • we demonstrate first that $2<n \Rightarrow 2<n+1$;
  • by knowledge, intuition, trial we "discover" and prove that $2<4$
  • then the first step will tell us that $4,5,6,\cdots$ are also greater than $2$, and in particular it is true that $2<5$.

Clearly we could have started with $3$ instead of $4$, if we know how to demonstrate that $2<3$. But in more complicated cases this could not be achievable.
After that, try by yourself to demonstrate that $2<5<6$, and you can grasp the importance that to the relation above we shall attach the range of the values of $n$ for which it applies.

$\endgroup$
  • $\begingroup$ @G_Cab So this entire proof is based on the assumption that n is true? But how can it be called it proof, and not an assumption then? $\endgroup$ – Ethan Chan Jun 30 '18 at 13:06
  • $\begingroup$ because for $n=n_0$ it is actually true, and thus we can restart our analysis from $n_0$ as a starting point : provided it is within the range in which $P(n) \to P(n+1)$. $\endgroup$ – G Cab Jun 30 '18 at 13:16
  • $\begingroup$ @G_Cab I'm sorry, you've got to simply this, I'm still a beginner. what does n=n0 mean, and what is the significance of ti being true? Also, what does P(n)→P(n+1) mean? $\endgroup$ – Ethan Chan Jun 30 '18 at 13:19
  • $\begingroup$ Ok, I will expand the answer $\endgroup$ – G Cab Jun 30 '18 at 13:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.