6
$\begingroup$

I am currently taking Discrete Mathematics and while I understand most of the topics covered, the one topic which I still don't quite understand is Mathematical Induction. The way the professor taught the topic was very complicated, and on top of that, the textbook creates more confusion with the use of terms and notations which I simply don't understand. Questions which run through my head are "what is Mathematical Induction?", "when do we know when to use simple induction and strong induction?", "how do we begin an induction proof?", "what exactly is a base case, induction hypothesis and inductive step?". Is there anyone here who has mastered Induction and is willing to explain to me(using examples[both simple and strong]) in such as way that even for those who haven't looked at Induction before can easily understand the topic?

Thanks

$\endgroup$
  • 1
    $\begingroup$ As you progress with your mathematical studies, the (formal) definitions of terms you haven't yet encountered are critical to constructing proofs. If you don't understand terms/notation, it might be best to backtrack and understand those first. $\endgroup$ – Emily Nov 25 '13 at 22:31
3
$\begingroup$

What is induction?

At its core, induction is this statement:

Take a set $S$. If $1 \in S$, and $k \in S$ implies that $k + 1 \in S$, then all natural numbers are in $S$.

Intuitively, this is pretty obvious. Assume both hypotheses: that $1 \in S$ and $k \in S \implies k + 1 \in S$.

  • Is $1 \in S$? Yes, by assumption.
  • Is $2 \in S$? Yes, because $1 \in S$, and $1 \in S$ implies $1 + 1 \in S$.
  • Is $3 \in S$? Yes, because we just showed $2 \in S$, and $2 \in S$ implies $2 + 1 \in S$.
  • $\ldots$

That clearly wasn't a formal proof that induction is valid, but it's a good place to start your intuition. No matter what natural number we start at, we can "step back" by one until we hit $1$, which we know is true.


Wait, how'd sets get in there?

Normally, people don't talk about sets when it comes to induction. Usually, it's about propositions. But the two are equivalent, consider the set $S = \{ n \mid P(n) \}$ or the proposition $P(n) = n \in S$. If you're working with propositions, induction is stated as:

Take a proposition $P$. If $P(1)$ is true, and $P(k)$ implies that $P(k+1)$, then $P(n)$ is true for all $n \in \mathbb{N}$.


How do we do inductive proofs?

Like any conditional statement, all you need to do is prove the two hypotheses:

  • $1 \in S$ (the base case)
  • If $k \in S$, then $k + 1 \in S$ (the recursive case)

or for propositions,

  • $P(1)$ (the base case)
  • If $P(k)$, then $P(k + 1)$ (the recursive case)

The confusing part

The recursive step sometimes confuses people. "Aren't we assuming what we want to prove?" Not quite. Here, a precise understanding of conditional statements is required. If I say, "If today is Friday, tomorrow is Saturday", I am not saying that today is Friday. I am only saying that, if we can show today is Friday, then we know tomorrow is Saturday.

It is the same with the recursive step. We are proving: "if $P$ is true for $k$, then it is also true for $k + 1$". We have not said anything about whether or not $P(k)$ is true!

Additionally, we are not assuming $P$ is true for all $k$, we are only assuming it to be true for a particular $k$. In notation, the recursive step is:

$$\forall k \in \mathbb{N} \ (P(k) \implies P(k + 1))$$

Finally, induction is not the process of proving those two statements. Those can be proved like any other statement. Induction is the statement "if those two statements are true, then $P$ is true for all natural numbers".


An example

We want to show that $\sum_{i = 1}^n i = \frac{n(n+1)}{2}$. (In terms of sets, this would be "all natural numbers are in the set $\{ n \mid \sum_{i = 1}^n i = \frac{n(n+1)}{2} \}$, but usually, the proposition syntax is easier).

"$P$ is true for $1$" is pretty easy to see, just plug it in and check.

The recursive case isn't much harder. Assume that $\sum_{i = 1}^k i = \frac{k(k + 1)}{2}$ is true for some $k$. Then, by adding $k + 1$ to both sides, we get $\sum_{i = 1}^{k+1} i = \frac{(k + 1)(k + 2)}{2}$. So, $P(k) \implies P(k+1)$.

Since $P(1)$ and $P(k) \implies P(k + 1)$, then by induction, $P(n)$ is true for all $n$.


Strong induction

The induction described above is called "weak induction". Strong induction is when your recursive hypothesis is replaced with "if $P$ is true for all $i$ less than $k$, then $P$ is true for $k$". The justification is similar, except to prove that $P(k)$ is true, we can look at any $i$ less than $k$, not just $k - 1$. It is called strong because your hypothesis is stronger, you can look at more $i$.

Sometimes this format is easier to use than weak induction. As an example, we show that all natural numbers can be written as $2^a m$, where $m$ is odd. The base case is easy, $1 = 2^0 \cdot 1$.

For the recursive case: let $k \in \mathbb{N}$ and assume that $P(i)$ is true for all $i < k$. If $k$ is odd, we are done. If not, there is some $i < k$ such that $2i = k$. By hypothesis, $i = 2^a m$ for some $a, m$, where $m$ is odd. Thus, $k = 2^{a + 1} m$.

Since $P(1)$ and $\forall i < k \ P(i) \implies P(k)$, by strong induction, $P(n)$ is true for all $n \in \mathbb{N}$. This would be difficult with weak induction.


Why is it valid?

Above, an intuitive argument for induction was shown. But in math we like to prove things. To do so, we introduce the "well-ordering principle": all non-empty subsets of $\mathbb{N}$ have a smallest element.

The well-ordering principle, weak induction, and strong induction are all equivalent!

Either you can take one of them as an axiom, or you can prove one by whichever construction of $\mathbb{N}$ you have. Then, there are pretty simple proofs to show the equivalence of the three.

Well-ordering implies weak induction: Let $S$ be a set, where $1 \in S$, and $k \in S \implies k + 1 \in S$. Let $T = \mathbb{N} \setminus S$, that is, all natural numbers not in $S$. Assume $T$ is non-empty. By well-ordering, it has a least element, $k$. Clearly it can't be $1$, because $1 \in S$. So it must be greater than $1$, and so $k - 1 \in \mathbb{N}$. Since $k$ is the smallest element in $T$, $k - 1$ can't be in $T$, meaning $k - 1 \in S$. But by assumption, that implies $(k - 1) + 1$ is in $S$, and so $k \in S$, which contradicts that $k \in T$. Therefore, $T$ was empty after all, and so $\mathbb{N} \subseteq S$.

Weak induction implies strong induction: Let $P(k)$ be a proposition where $P(1)$ and if $P(i)$ for all $i < k$, then $P(k)$. Let $Q(n)$ be the proposition "$P(k)$ is true for all $k < n$". We will use weak induction on $Q$. First, note that $Q(1)$ is true. Next, assume that $Q(n)$ is true. That means that $P(i)$ is true for all $i < k$, and so by our initial description of $P$, $P(n + 1)$ is true. But since $Q(n)$ and $P(n + 1)$ are true, $Q(n + 1)$ is true as well. Therefore, the conditions for weak induction are satisfied, and $Q(n)$ is true for all $n$. This clearly means that $P(n)$ is true for all $n$ as well.

Strong induction implies well-ordering: Let $P(n)$ be the proposition "if $n \in S$, then $S$ has a least element". Clearly it is true for $1$, because if $1 \in S$, then $1$ is the least element of $S$. For the recursive step, assume that $P(i)$ is true for all $i < k$. Then we wish to show that $P(k)$ is true. Let $k \in S$. If $k$ is the smallest element, then we are done. If not, then there is some $i < k$ such that $i \in S$. Thus, $P(i)$ is true, and so $S$ has a smallest element. By strong induction, if there is any $n \in S$, then it has a least element (this is where the "non-empty" part crops up).

Which one of these proofs you need depends on what your construction of $\mathbb{N}$ is or what axioms you have.

$\endgroup$
  • $\begingroup$ "Weak induction implies strong induction"...strong induction may be used in an uncountable domain: $(\forall x \in \mathbb{R} (\forall y < x \in \mathbb{R} \,P(y)) \Rightarrow P(x)) \Rightarrow (\forall z \in \mathbb{R}\, P(z))$ so it's really not possible that strong induction can follow from weak induction since weak induction is only countable (unless there is some amazing result with infinitesimals that no one knows yet). $\endgroup$ – DanielV Jan 4 '14 at 6:45
  • 1
    $\begingroup$ I'm not so sure that's true, because strong induction implies well-ordering. And the reals are not well ordered under $<$. A counter-example: consider $P(x) = (x \le 0)$. If everything less than $x$ is non-positive, then $x$ is non-positive. But not all reals are non-positive. $\endgroup$ – Henry Swanson Jan 4 '14 at 7:07
  • $\begingroup$ You are right I should have said given an uncountable set with a minimum, like "all non-negative reals" or so. That's an interesting counterexample, $(\forall x, x < y \Rightarrow x \le 0) \Rightarrow y \le 0$, is this actually provable? $\endgroup$ – DanielV Jan 4 '14 at 8:04
  • 1
    $\begingroup$ It's still not true though, just change $0$ to $1$. You need a set that is well-ordered, where every non-empty subset has a minimum. As for the proof, assume $y > 0$. Then $y/2 < y$, but is greater than $0$. Contradiction, thus, $y \le 0$. $\endgroup$ – Henry Swanson Jan 4 '14 at 8:29
2
$\begingroup$

Have you looked at the perfectly sensible Wikipedia article?

http://en.wikipedia.org/wiki/Mathematical_induction

Or how about

http://www.math.utah.edu/mathcircle/notes/induction.pdf

For a famously lucid book, try

Daniel J. Velleman How to Prove It, Ch. 6

[A general observation: you write. "The way the professor taught the topic was very complicated, and on top of that, the textbook creates more confusion with the use of terms and notations which I simply don't understand." And so? There are many other textbooks! That is in part what libraries are for -- to provide the back-up and/or parallel reading, which you should always be doing if you get stuck.]

$\endgroup$
1
$\begingroup$

The best way to casually describe induction is thusly:

Imagine each "step" is a domino. You assume that knocking down any domino will knock down the successive domino, no matter which domino you start at. This is equivalent to saying "If $P(n)$ is true, then so is $P(n+1)$." Since it doesn't matter which domino you start at, it doesn't matter if you knock down the domino at position $n$, or if it is knocked down by the domino immediately before it. All that matters is that it is knocked down somehow.

However, this last statement requires us to prove that the first domino can knock down the second. This is the base case.

If we prove these two things, then we know that the chain of dominoes will continue to be knocked down, no matter where we look.

Therefore, if we can knock the first domino into the second, and all that matters is that any domino will knock down its successor, we know that all dominoes will be knocked down... hence, the proof is complete.

$\endgroup$
1
$\begingroup$

Induction is a useful way to prove properties that hold for natural numbers.

Suppose that we want to prove a property, for example, that $1+2+…+n=\frac{1}{2}n(n+1)$.

For this to hold for all natural numbers, it obviously has to hold for the first natural number: $1$. We can clearly see that $1=\frac{1}{2}\cdot 1 \cdot 2$, so the property holds for $1$. This is the base case: we have shown that the property we want to prove holds for the least element for which we want to prove it.

We now have to show that the property holds for an arbitrary element of the natural numbers, say $k$. If we assume that it is true for $k-1$ and we can then show it is true for $k$, we can then show that it is true for any two consecutive natural numbers and therefore it is true for all natural numbers.

So, we assume that the property is true for $k-1$ where $k$ is an arbitrary natural number. Therefore we have that $1+2+…+(k-1)=\frac{1}{2}(k-1)(k)$. This is the induction assumption, or induction hypothesis - the assumption that the property holds true for $k-1$.

We now have to show that the property is true for $k$, i.e. that $1+2+…+k=\frac{1}{2}(k)(k+1)$. Notice that $1+2+…+k=1+2+…+(k-1)+k=(1+2+…+(k-1))+k$. Notice that in our induction assumption, we assumed that $1+2+…+(k-1)=\frac{1}{2}(k-1)(k)$, and therefore $(1+2+…+(k-1))+k=\frac{1}{2}(k-1)(k)+k$. This is the induction step: we input what we assumed to be true in our induction assumption to help us prove the property holds for $k$.

We can clearly see that $\frac{1}{2}(k-1)(k)+k=\frac{1}{2}(k)(k+1)$ by trivial rearrangement. We have therefore shown that for an arbitrary element of the natural numbers, our property holds, and the proof was dependent on our induction assumption. Therefore our proposition holds for all natural numbers.

This is an example of weak induction: in our induction hypothesis, we only needed to assume that the property was true for one element less than $k$. In strong induction, we would have to assume that the property was true for $all$ elements less than $k$.

More formally, if $P$ is a property of natural numbers, we prove $P$ by weak induction by

1)Show $P(1)$ is true. This is the Base case.

2)Assume $P(k-1)$ is true where $k-1$ is arbitrary. This is the induction hypothesis.

3)Show $P(k)$ is true by using the fact that $P(k-1)$ is true. This is the induction step.

To prove $P$ by strong induction, we only change step 2. This becomes

2') Assume $P(i)$ is true for all $1 \leq i \leq k-1$

Running through some exercises for induction should give you an idea of how it works. I hope this helped.

$\endgroup$
1
$\begingroup$

Mathematical Induction is used to prove statements for the set of natural numbers. From my understanding of Mathematical Induction (I profess to hold no exalted knowledge of the topic) the proof is structured as such:

1) Base Case (usually $n = 1$)

Here you are showing that the statement is true for the smallest element in the set

2) Assume true for $n = k$

Here you are merely "assuming" that it is true for any arbitrary $k$ in the set

3) Prove true for $n = k + 1$

Here is where you actually prove (given the assumption from $n=k$), that the statement is true for any successive term i.e. $n = k + 1$. This step is where the bulk of the "proving" will take place. It is where you perform various mathematical gymnastics (rearranging/re-ordering, expressing the terms in different forms etc..) in order to show that for any arbitrary $k$, the statement will hold for the $(k + 1)^{th}$ term. In doing so, you have also proved that the statement holds for the $k^{th}$ term (true for $n = k + 1 \implies$ true for $n = k$)

4) Conclude that since it is true for the base case, $n = k$ and $n = k + 1$, then it is also true for all natural numbers

Clearly, since the statement holds (is true and was proven) for $n = k + 1$ and as a result it also holds for $n = k$, and given that the smallest element of set (base case) was also proven to be true, one can then draw the conclusion that for all (it is imperative to note that since the smallest element in the set and $n = k + 1$ which encompasses successive terms, was proven true - all elements were taken care of ) members in the set, the statement will be true.


Examples

My first taste of Mathematical Induction Proofs were of the "$\sum (3n - 2) = \frac{n(3n + 1)}{2}$" form, and for the most part I understood those readily (my professor taught me a nifty trick to ensure that I would always be able to correctly prove for $n = k + 1$). Then I was exposed to ones such as "prove $6^{n-1}$ is divisible by $5$", . I recently did an induction proof on the Fibonacci Sequence (which at first I thought was going to be a pain in the neck, but was quite fun and simple to get out). What I have found is that, like with maths, once you practice and are comfortable with mathematical notions and algebra, these will come naturally and you will be able to "see" tricks and various gymnastics you can perform to prove statements easily and in no mean time.

$\endgroup$
0
$\begingroup$

Consider example, statement A(n) - you can climb on n-th bar of the ladder. Suppose you have shown that you can climb on first bar meaning that A(1) = true. And you have shown that you can go from n-th bar to n+1-th bar or in other words if A(n) = true then A(n+1) = true. Now you know that A(1) = true, from fact that if A(n) = true then A(n+1) = true you know that A(2) = true, but if A(2) = true then A(3) = true. Now it is clear that A(n) is true for all positive integer values 1,2,... and therefore A(n) = true.

$\endgroup$
0
$\begingroup$

You can give a first step, and if you did a step then you can make a next step. Then you can go as long as you want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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