maths.free › Discrete Math & Logic › 5. Sequences › Proof by Induction

Proof by Induction

Investigation What is the unit digit (the right-most digit) of 6^n? Does the answer depend on n?

Section Preview

Investigation

What is the unit digit (the right-most digit) of \(6^n\)? Does the answer depend on \(n\)?

Mathematical induction is a powerful proof technique that can be used to prove statements are true for a sequence of statements, as long as that sequence of statements has some starting place. For example, if we are trying to say something about the unit digit of \(6^n\), we are making that claim for \(n=1\), then \(n = 2\), then \(n = 3\), and so on.

Induction is closely related to recursive definitions; the main idea in a proof by induction is to explain how you can get from one statement in the sequence to the next.

Recursive Reasoning

We have seen that describing a sequence recursively can often be easier than describing the sequence with a closed formula. We will now see how using similar recursive reasoning can help us prove statements using a proof technique called mathematical induction. This style of proof is especially useful when the different instances of the statement (for different values of \(n\), say) are related recursively.

For example, suppose we wanted to prove a fact about all the terms in a sequence for which we have a recursive definition. Consider the sequence \((a_n)_{n\ge 0}\) defined recursively by \(a_n = 3a_{n-1} - 2\) with \(a_0 = 5\). Could we prove that every term in this sequence is odd?

Let's start by writing out the first few terms of the sequence: \[5, 13, 37, 109, \ldots\]. So far, all these numbers look odd. Will the next number be odd? Of course, we could just compute it using the recurrence relation. We would take \(3\cdot 109 - 2\). We don't actually care which odd number this is, just that it is, in fact, odd. We know it will be odd because the product of two odd numbers is odd, and subtracting 2 from an odd number results in an odd number.

Great, so \(a_4\) is odd. Will \(a_5\) be odd too? Yes, use the same argument as above: \(a_5 = 3 a_4 - 2\). We just convinced ourselves that \(a_4\) is odd (without finding its actual value), so \(3 a_4\) is odd, and 2 less than it will be odd too.

What about \(a_6\)? Do the same thing. In fact, why are we using any particular number as the index? If it is the same argument each time, we should be able to just give this argument once and say it always works.

Suppose we have found that \(a_k\) is odd (where \(k\) is some arbitrary natural number). From this, we can find that \(a_{k+1}\) is odd, since \(a_{k+1} = 3 a_k - 2\), and \(3\) times the odd number \(a_{k}\) will be odd, and subtracting 2 will result in an odd number. Yay. Let's put this all together as a proof.

Proof

We claim that for any \(n \ge 0\), the number \(a_n\) is odd, where \(a_n = 3a_{n-1} - 2\) and \(a_0 = 5\).

When \(n = 0\), the claim is true, since \(a_0 = 5\) is an odd number.

Further, we can prove that every larger \(n\) has \(a_n\) odd because as long as \(a_k\) is odd, so is \(a_{k+1}\) (since \(a_{k+1} = 3a_{k} - 2\), and 3 times an odd number minus 2 is always odd).

Therefore \(a_n\) is odd for all \(n \ge 0\).

Soon we will give a more rigid structure for proofs by induction, but the basic idea is exactly what we have above.

Formalizing Proofs

Induction can prove many statements that hold for all natural numbers, not just statements about sequences. In particular, induction should be used when there is some way to go from one case to the next when you can see how to always do one more.

Thinking about how we write statements in logical symbols, we will use induction to prove statements of the form \[\forall n P(n)\], where the domain of discourse (the values of \(n\) we quantify over) has some least element. Say that domain of discourse is the natural numbers. We are then proving this sequence of statements: \[P(0), P(1), P(2), P(3), \ldots\]. The way we do this with induction is to prove a base case, that \(P(0)\) is true (or \(P(a)\) where \(a\) is the least element of our domain of discourse). Next, we prove the inductive case, that \(P(k) \imp P(k+1)\) for all \(k \ge 0\) (or \(k \ge a\)).

Together, these are enough to prove \(P(n)\) is true for all \(n\). How do we know? That is, why is this style of proof valid? Well, let's convince ourselves that \(P(3)\) is true. We know \(P(0)\) is true. And because we know that \(P(0) \imp P(1)\), we then also know that \(P(1)\) is true. Because \(P(1) \imp P(2)\), we then get that \(P(2)\) is true. Finally, because \(P(2) \imp P(3)\), we have that \(P(3)\). There is nothing special about 3 here. We could have gone up as far as we like, to any \(n\) value!

Think of a row of dominoes set up standing on their edges. We want to argue that in a minute, all the dominoes will have fallen. For this to happen, you will need to push the first domino. That is the base case. It will also have to be that the dominoes are close enough together that when any particular domino falls, it will cause the next domino to fall. That is the inductive case. If both of these conditions are met you push the first domino over, and each domino will cause the next to fall then all the dominoes will fall.

Induction is powerful! Think how much easier it is to knock over dominoes when you don't have to push over each domino yourself. You just start the chain reaction and then rely on the relative nearness of the dominoes to take care of the rest.

When writing a proof by induction, we will follow a standard style. Writing in this style allows us to keep our ideas organized and might even help us formulate the proof.

Here is the general structure of a proof by mathematical induction:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Examples

Here are some examples of proof by mathematical induction.

Example

Prove for each natural number \(n \ge 1\) that \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\).

Solution

First, let's think inductively about this equation. In fact, we know this is true for other reasons (reverse and add comes to mind). But why might induction be applicable? The left-hand side adds up the numbers from 1 to \(n\). If we know how to do that, adding just one more term (\(n+1\)) would not be that hard. For example, if \(n = 100\), suppose we know that the sum of the first 100 numbers is \(5050\) (so \(1 + 2 + 3 + \cdots + 100 = 5050\), which is true). Now to find the sum of the first 101 numbers, it makes more sense to just add 101 to 5050, instead of computing the entire sum again. We would have \(1 + 2 + 3 + \cdots + 100 + 101 = 5050 + 101 = 5151\). In fact, it would always be easy to add just one more term. This is why we should use induction.

Now the formal proof:

Proof

Let \(P(n)\) be the statement \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\). We will show that \(P(n)\) is true for all natural numbers \(n \ge 1\).

Base case: \(P(1)\) is the statement \(1 = \frac{1(1+1)}{2}\) which is clearly true.

Inductive case: Let \(k \ge 1\) be a natural number. Assume (for induction) that \(P(k)\) is true. That means \(1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\). We will prove that \(P(k+1)\) is true as well. That is, we must prove that \(1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\). To prove this equation, start by adding \(k+1\) to both sides of the inductive hypothesis: \[1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)\].

Now, simplifying the right side we get: \[\begin{aligned}\frac{k(k+1)}{2} + k+1 \amp = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ \amp = \frac{k(k+1) + 2(k+1)}{2} \\ \amp = \frac{(k+2)(k+1)}{2}\end{aligned}\].

Thus \(P(k+1)\) is true, so by the principle of mathematical induction, \(P(n)\) is true for all natural numbers \(n \ge 1\).

Note that in the part of the proof where we proved \(P(k+1)\) from \(P(k)\), we used the equation \(P(k)\). This was the inductive hypothesis. Seeing how to use the inductive hypotheses is usually straightforward when proving a fact about a sum like this. In other proofs, it can be less obvious where it fits in.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (39)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Suppose that \(6^{472}\) had a 2 for its unit digit. That is, suppose \(6^{472} = 19,381,6\ldots\ldots 2\). What would the unit digit of \(6^{473}\) be? ____

Revelează răspunsul

Hint:
\(6^{473} = 6 \cdot 6^{472}\).
What is the unit digit of \(6^{2}\), of \(6^3\), and of \(6^4\)?
The unit's digit of \(6^2\) is ____.
The unit's digit of \(6^3\) is ____.
The unit's digit of \(6^4\) is ____.
Which of the following are true? Select all that apply.
Explain your answer to the previous question.
Suppose you wanted to prove, using mathematical induction, that \(1+3+5+\cdots+2n-1 = n^2\) for all values of \(n \ge 1\). Which of the following would be an appropriate first line of the proof? Select all that apply.
Suppose you wanted to prove that \(P(n,3) \ge \binom{n}{3}\) for all \(n \ge 4\). Write the first line of a proof by induction.
What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about after reading this section.
Suppose you are trying to prove, by mathematical induction, that a statement \(P(n)\) is true for all \(n \ge 0\). What would you attempt to prove in the induction step of the proof? (Select all that apply.)
Suppose you wanted to prove the following statement: \[2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ for all } n \ge 1\]. What would the first line of a proof by induction be?
Suppose you were proving the following statement by mathematical induction: \[2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ for all } n \ge 1\]. What would you need to show to establish the base case?
Suppose you were proving the following statement by mathematical induction: \[2 + 4 + 6 + \cdots + 2n = n(n+1) \text{ for all } n \ge 1\]. What would the first line of the inductive case be?
Arrange some of the statements below to create a correct proof by induction that the recurrence relation \(a_n = 5a_{n-1} + 4\), with initial condition \(a_0 = 0\) has closed formula \(a_n = 5^n - 1\).
Arrange some of the statements below to create a correct proof by induction that for all \(n \ge 1\), the number \(14^n - 1\) is a multiple of \(13\).
Arrange some of the statements below to create a correct proof by induction that for all \(n \ge 1\), \(1+1+2+3+5+\cdots + F_n = F_{n+2} - 1\), where \(F_n\) is the \(n\)th Fibonacci number.
On the way to the market, you exchange your cow for some magic dark chocolate espresso beans. These beans have the property that every night at midnight, each bean splits into two, effectively doubling your collection. You decide to take advantage of this, and each morning (around 8 am) you eat 5 beans.
1. Explain why it is true that if at noon on day \(n\) you have a number of beans ending in a 5, then at noon on day \(n+1\) you will still have a number of beans ending in a 5.
2. Why is the previous fact not enough to conclude that you will always have a number of beans ending in a 5? What additional fact would you need?
3. Assuming you have the additional fact in part (b), and have successfully proved the fact in part (a), how do you know that you will always have a number of beans ending in a 5? Illustrate what is going on by carefully explaining how the two facts above prove that you will have a number of beans ending in a 5 on day 4 specifically. In other words, explain why induction works in this context.
Revelează răspunsul
1. If we have a number of beans ending in a 5, and we double it, we will get a number of beans ending in a 0 (since \(5\cdot 2 = 10\) ). Then if we subtract 5, we will once again get a number of beans ending in a 5. Thus, if on any day we have a number ending in a 5, the next day we will also have a number ending in a 5.
2. If you don't start with a number of beans ending in a 5 (on day 1), the above reasoning is still correct but not helpful. For example, if you start with a number ending in a 3, the next day you will have a number ending in a 1.
3. Part (b) is the base case, and part (a) is the inductive case. If on day 1 we have a number ending in a 5 (by part (b)), then on day 2 we will also have a number ending in a 5 (by part (a)). Then by part (a) again, we will have a number ending in a 5 on day 3. By part (a) again, this means we will have a number ending in a 5 on day 4.
  The proof by induction would say that on every day we will have a number ending in a 5, and this works because we can start with the base case and then use the inductive case over and over until we get up to our desired \(n\).
Use induction to prove for all \(n \in \N\) that \(\d\sum_{k=0}^n 2^k = 2^{n+1} - 1\).

Revelează răspunsul

Proof
We must prove that \(1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1\) for all \(n \in \N\). Thus let \(P(n)\) be the statement \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\). We will prove that \(P(n)\) is true for all \(n \in \N\). First we establish the base case, \(P(0)\), which claims that \(1 = 2^{0+1} -1\). Since \(2^1 - 1 = 2 - 1 = 1\), we see that \(P(0)\) is true. Now for the inductive case. Assume that \(P(k)\) is true for an arbitrary \(k \in \N\). That is, \(1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\). We must show that \(P(k+1)\) is true (i.e., that \(1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1\)). To do this, we start with the left-hand side of \(P(k+1)\) and work to the right-hand side: \[\begin{aligned}1 + 2 + 2^2 + \cdots + 2^k + 2^{k+1} = \amp ~ 2^{k+1} - 1 + 2^{k+1} \amp \text{by the inductive hypothesis.} \\ = \amp ~2\cdot 2^{k+1} - 1 \amp \\ = \amp ~ 2^{k+2} - 1 \amp\end{aligned}\]
Thus \(P(k+1)\) is true, so by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\).
Prove that \(7^n - 1\) is a multiple of 6 for all \(n \in \N\).

Revelează răspunsul

Proof
Let \(P(n)\) be the statement, \(7^n - 1\) is a multiple of 6. We will show \(P(n)\) is true for all \(n \in \N\). First we establish the base case, \(P(0)\). Since \(7^0 - 1 = 0\), and \(0\) is a multiple of 6, \(P(0)\) is true. Now for the inductive case. Assume \(P(k)\) holds for an arbitrary \(k \in \N\). That is, \(7^k - 1\) is a multiple of 6, or in other words, \(7^k - 1 = 6j\) for some integer \(j\). Now consider \(7^{k+1} - 1\): \[\begin{aligned}7^{k+1} - 1 ~ \amp = 7^{k+1} - 7 + 6 \amp \text{by cleverness:} -1 = -7 + 6 \\ \amp = 7(7^k - 1) + 6 \amp \text{factor out a 7 from the first two terms} \\ \amp = 7(6j) + 6 \amp \text{by the inductive hypothesis} \\ \amp = 6(7j + 1) \amp \text{factor out a 6}\end{aligned}\]
Therefore \(7^{k+1} - 1\) is a multiple of 6, or in other words, \(P(k+1)\) is true. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\).
Prove that \(1 + 3 + 5 + \cdots + (2n-1) = n^2\) for all \(n \ge 1\).

Revelează răspunsul

Proof
Let \(P(n)\) be the statement \(1+3 +5 + \cdots + (2n-1) = n^2\). We will prove that \(P(n)\) is true for all \(n \ge 1\). First the base case, \(P(1)\). We have \(1 = 1^2\) which is true, so \(P(1)\) is established. Now the inductive case. Assume that \(P(k)\) is true for some fixed arbitrary \(k \ge 1\). That is, \(1 + 3 + 5 + \cdots + (2k-1) = k^2\). We will now prove that \(P(k+1)\) is also true (i.e., that \(1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2\)). We start with the left-hand side of \(P(k+1)\) and work to the right-hand side: \[\begin{aligned}1 + 3 + 5 + \cdots + (2k-1) + (2k+1) ~ \amp = k^2 + (2k+1) \amp \text{by the inductive hypothesis} \\ \amp = (k+1)^2 \amp \text{by factoring}\end{aligned}\]
Thus \(P(k+1)\) holds, so by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 1\).
Prove that \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\) where \(F_n\) is the \(n\)th Fibonacci number.

Revelează răspunsul

Proof
Let \(P(n)\) be the statement \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\). We will show that \(P(n)\) is true for all \(n \ge 0\). First the base case is easy because \(F_0 = 0\) and \(F_1 = 1\) so \(F_0 = F_1 - 1\). Now consider the inductive case. Assume \(P(k)\) is true, that is, assume \(F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\). To establish \(P(k+1)\) we work from left to right: \[\begin{aligned}F_0 + F_2 + \cdots + F_{2k} + F_{2k+2} ~ \amp = F_{2k+1} - 1 + F_{2k+2} \amp \text{by the inductive hypothesis.} \\ \amp = F_{2k+1} + F_{2k+2} - 1 \amp \\ \amp = F_{2k+3} - 1 \amp \text{by the recursive definition.}\end{aligned}\]
Therefore \(F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\), which is to say \(P(k+1)\) holds. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 0\).
Prove that \(2^n \lt n!\) for all \(n \ge 4\). (Recall, \(n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n\).)

Revelează răspunsul

Proof
Let \(P(n)\) be the statement \(2^n \lt n!\). We will show \(P(n)\) is true for all \(n \ge 4\). First, we check the base case and see that yes, \(2^4 \lt 4!\) (as \(16 \lt 24\)), so \(P(4)\) is true. Now for the inductive case. Assume \(P(k)\) is true for an arbitrary \(k \ge 4\). That is, \(2^k \lt k!\). Now consider \(P(k+1)\): \(2^{k+1} \lt (k+1)!\). To prove this, we start with the left side and work to the right side. \[\begin{aligned}2^{k+1}~ \amp = 2\cdot 2^k \amp \\ \amp \lt 2\cdot k! \amp \text{by the inductive hypothesis} \\ \amp \lt (k+1) \cdot k! \amp \text{ since } k+1 \gt 2 \\ \amp = (k+1)! \amp\end{aligned}\]
Therefore \(2^{k+1} \lt (k+1)!\), so we have established \(P(k+1)\). Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \ge 4\).
Prove, by mathematical induction, that \(F_0 + F_1 + F_2 + \cdots + F_{n} = F_{n+2} - 1\), where \(F_n\) is the \(n\)th Fibonacci number (\(F_0 = 0\), \(F_1 = 1\) and \(F_n = F_{n-1} + F_{n-2}\)).
Zombie Euler and Zombie Cauchy, two famous zombie mathematicians, have just signed up for Myspace accounts. After one day, Zombie Cauchy has more followers than Zombie Euler. Each day after that, the number of new followers of Zombie Cauchy is exactly the same as the number of new followers of Zombie Euler (and neither lose any followers). Explain how a proof by mathematical induction can show that on every day after the first day, Zombie Cauchy will have more followers than Zombie Euler. That is, explain what the base case and inductive case are, and why they together prove that Zombie Cauchy will have more followers on the 4th day.
Find the largest number of points that it is impossible for a football team to get exactly, using just 3-point field goals and 7-point touchdowns (ignore the possibilities of safeties, missed extra points, and two-point conversions). Prove your answer is correct by mathematical induction.

Revelează răspunsul

Hint:
It is not possible to score exactly 11 points. Can you prove that you can score \(n\) points for any \(n \ge 12\)?
Prove that the sum of \(n\) squares can be found as follows \[1^2 +2^2 +3^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}\].
Prove that the sum of the interior angles of a convex \(n\)-gon is \((n-2)\cdot 180^\circ\). (A convex \(n\)-gon is a polygon with \(n\) sides for which each interior angle is less than \(180^\circ\).)

Revelează răspunsul

Hint:
Start with \((k+1)\)-gon, and divide it up into a \(k\)-gon and a triangle.
What is wrong with the following proof of the fact that \(n+3 = n+7\) for all values of \(n\) (besides of course that the thing it is claiming to prove is false)?
Proof
Let \(P(n)\) be the statement that \(n + 3 = n + 7\). We will prove that \(P(n)\) is true for all \(n \in \N\). Assume, for induction, that \(P(k)\) is true. That is, \(k+3 = k+7\). We must show that \(P(k+1)\) is true. Now since \(k + 3 = k + 7\), add 1 to both sides. This gives \(k + 3 + 1 = k + 7 + 1\). Regrouping \((k+1) + 3 = (k+1) + 7\). But this is simply \(P(k+1)\). Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\).

Revelează răspunsul

The only problem is that we never established the base case. Of course, when \(n = 0\), \(0+3 \ne 0+7\).
The proof in the previous problem does not work. But if we modify the fact, we can get a working proof. Prove that \(n + 3 \lt n + 7\) for all values of \(n \in \N\). You can do this proof with algebra (without induction), but the goal of this exercise is to write out a valid induction proof.

Revelează răspunsul

Proof
Let \(P(n)\) be the statement that \(n + 3 \lt n + 7\). We will prove that \(P(n)\) is true for all \(n \in \N\). First, note that the base case holds: \(0+3 \lt 0+7\). Now assume for induction that \(P(k)\) is true. That is, \(k+3 \lt k+7\). We must show that \(P(k+1)\) is true. Now since \(k + 3 \lt k + 7\), add 1 to both sides. This gives \(k + 3 + 1 \lt k + 7 + 1\). Regrouping \((k+1) + 3 \lt (k+1) + 7\). But this is simply \(P(k+1)\). Thus by the principle of mathematical induction \(P(n)\) is true for all \(n \in \N\).
Find the flaw in the following proof of the fact that \(n \lt 100\) for every \(n \in \N\).
Proof
Let \(P(n)\) be the statement \(n \lt 100\). We will prove \(P(n)\) is true for all \(n \in \N\). First we establish the base case: when \(n = 0\), \(P(n)\) is true, because \(0 \lt 100\). Now for the inductive step, assume \(P(k)\) is true. That is, \(k \lt 100\). Now if \(k \lt 100\), then \(k\) is some number, like 80. Of course \(80+1 = 81\) which is still less than 100. So \(k +1 \lt 100\) as well. But this is what \(P(k+1)\) claims, so we have shown that \(P(k) \imp P(k+1)\). Thus by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\).

Revelează răspunsul

The problem here is that while \(P(0)\) is true, and while \(P(k) \imp P(k+1)\) for some values of \(k\), there is at least one value of \(k\) (namely \(k = 99\)) when that implication fails. For a valid proof by induction, \(P(k) \imp P(k+1)\) must be true for all values of \(k\) greater than or equal to the base case.
While the above proof does not work (it better not since the statement it is trying to prove is false!) we can prove something similar. Prove that there is a strictly increasing sequence \(a_1, a_2, a_3, \ldots\) of numbers (not necessarily integers) such that \(a_n \lt 100\) for all \(n \in \N\). (By strictly increasing we mean \(a_n \lt a_{n+1}\) for all \(n\). So each term must be larger than the last.)

Revelează răspunsul

Hint:
For the inductive step, you can assume you have a strictly increasing sequence up to \(a_k\) where \(a_k \lt 100\). Now you just need to find the next term \(a_{k+1}\) so that \(a_{k} \lt a_{k+1} \lt 100\). What should \(a_{k+1}\) be?
What is wrong with the following proof of the fact that for all \(n \in \N\), the number \(n^2 + n\) is odd?
Proof
Let \(P(n)\) be the statement \(n^2 + n\) is odd. We will prove that \(P(n)\) is true for all \(n \in \N\). Suppose, for induction, that \(P(k)\) is true, that is, that \(k^2 + k\) is odd. Now consider the statement \(P(k+1)\). Now \((k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2\). By the inductive hypothesis, \(k^2 + k\) is odd, and of course \(2k + 2\) is even. An odd plus an even is always odd, so therefore \((k+1)^2 + (k+1)\) is odd. Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \in \N\).

Revelează răspunsul

We once again failed to establish the base case: When \(n = 0\), \(n^2 + n = 0\) which is even, not odd.
Now give a valid proof (by induction, even though you might be able to do so without using induction) of the statement, For all \(n \in \N\), the number \(n^2 + n\) is even.

Revelează răspunsul

Hint:
For the inductive case, you will need to show that \((k+1)^2 + (k+1)\) is even. Factor this out, and locate the part of it that is \(k^2 + k\). What have you assumed about that quantity?
Prove that there is a sequence of positive real numbers \(a_0, a_1, a_2, \ldots\) such that the partial sum \(a_0 + a_1 + a_2 + \cdots + a_n\) is strictly less than \(2\) for all \(n \in \N\). Hint: Think about how you could define what \(a_{k+1}\) is to make the induction argument work.

Revelează răspunsul

Hint:
This is similar to , although there you were showing that a sequence had all its terms less than some value, and here you are showing that the sum is less than some value. But the partial sums forms a sequence, so this is actually very similar.
Use induction to prove that if \(n\) people all shake hands with each other, that the total number of handshakes is \(\frac{n(n-1)}{2}\).

Revelează răspunsul

Hint:
We have already proved this without using induction, but looking at it inductively sheds light onto the problem (and is fun).
The question you need to answer to complete the inductive step is, how many new handshakes take place when a person \(k+1\) enters the room? Why does adding this give you the correct formula?
Use induction to prove that \(\d\sum_{k=0}^n {n \choose k} = 2^n\). That is, the sum of the \(n\)th row of Pascal's triangle is \(2^n\).

Revelează răspunsul

Hint:
Here's the idea: Since every entry in Pascal's triangle is the sum of the two entries above it, we can get the \(k+1\)st row by adding up all the pairs of entry from the \(k\)th row. But doing this uses each entry on the \(k\)th row twice. Thus each time we drop to the next row, we double the total. Of course, row 0 has sum \(1 = 2^0\) (the base case). Now try to make this precise with a formal induction proof. You will use the fact that \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) for the inductive case.
Use induction to prove \({4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\). (This is an example of the hockey stick theorem.)

Revelează răspunsul

Hint:
To see why this works, try it on a copy of Pascal's triangle. We are adding up the entries along a diagonal, starting with the 1 on the left-hand side of the 4th row. Suppose we add up the first 5 entries on this diagonal. The claim is that the sum is the entry below and to the left of the last of these 5 entries. Note that if this is true, and we instead add up the first 6 entries, we will need to add the entry one spot to the right of the previous sum. But these two together give the entry below them, which is below and left of the last of the 6 entries on the diagonal. If you follow that, you can see what is going on. But it is not a great proof. A formal induction proof is needed.
Use the product rule for logarithms (\(\log(ab) = \log(a) + \log(b)\)) to prove, by induction on \(n\), that \(\log(a^n) = n \log(a)\), for all natural numbers \(n \ge 2\).

Revelează răspunsul

The idea here is that if we take the logarithm of \(a^n\), we can increase \(n\) by 1 if we multiply by another \(a\) (inside the logarithm). This results in adding 1 more \(\log(a)\) to the total.
Proof
Let \(P(n)\) be the statement \(\log(a^n) = n \log(a)\). The base case, \(P(2)\) is true, because \(\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\), by the product rule for logarithms. Now assume, for induction, that \(P(k)\) is true. That is, \(\log(a^k) = k\log(a)\). Consider \(\log(a^{k+1})\). We have \[\log(a^{k+1}) = \log(a^k\cdot a) = \log(a^k) + \log(a) = k\log(a) + \log(a)\], with the last equality due to the inductive hypothesis. But this simplifies to \((k+1) \log(a)\), establishing \(P(k+1)\). Therefore by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 2\).
Let \(f_1, f_2,\ldots, f_n\) be differentiable functions. Prove, using induction, that \[(f_1 + f_2 + \cdots + f_n)' = f_1' + f_2' + \cdots + f_n'\].
You may assume \((f+g)' = f' + g'\) for any differentiable functions \(f\) and \(g\).

Revelează răspunsul

Hint:
You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, and then apply the usual sum of derivatives rule, and then the inductive hypothesis.
Suppose \(f_1, f_2, \ldots, f_n\) are differentiable functions. Use mathematical induction to prove the generalized product rule: \[(f_1 f_2 f_3 \cdots f_n)' = f_1' f_2 f_3 \cdots f_n + f_1 f_2' f_3 \cdots f_n + f_1 f_2 f_3' \cdots f_n + \cdots + f_1 f_2 f_3 \cdots f_n'\].
You may assume the product rule for two functions is true.

Revelează răspunsul

Hint:
For the inductive step, we know by the product rule for two functions that \[(f_1f_2f_3 \cdots f_k f_{k+1})' = (f_1f_2f_3\cdots f_k)'f_{k+1} + (f_1f_2f_3\cdots f_k)f_{k+1}'\].
Then use the inductive hypothesis on the first summand, and distribute.
In we proved that the following is a valid deduction rule:
\(P \imp Q\)
\(Q \imp R\)
\(\therefore\) \(P \imp R\)
Now use mathematical induction to prove you can chain together any number of statements like this. That is, prove for any \(n\) that the following is a valid deduction rule:
\(P_1 \imp P_2\)
\(P_2 \imp P_3\)
\(\vdots\)
\(P_{n-1} \imp P_n\)
\(\therefore\) \(P_1 \imp P_n\).

Revelează răspunsul

Hint:
You can inductively assume that from the first \(n-2\) implications you can deduce \(P_1 \imp P_{n-1}\). Then you can use a truth table to verify that this simplified deduction rule is valid.

Symbols used here

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\forall,\ \exists

for all, there exists
Quantifiers: every x; at least one x.

P(A),\ P(A \mid B)

probability, conditional probability
Chance of A; chance of A given that B happened.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

O(n^2),\ \Theta,\ \Omega

big-O notation
Grows no faster than n² (up to a constant), for large n.

a \bmod n

remainder
What is left after dividing a by n.

How to: Proof by Induction

Identify the parts of a proof by mathematical induction and how they relate to the statement being proved.
Prove statements using mathematical induction.
Explain why a proof by mathematical induction is valid.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Încearcă pe tine.

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mai multe în Discrete Math & Logic

Truth tables Sums and induction Proof by induction Algorithms and growth of functions

	\(P_1 \imp P_2\)
	\(P_2 \imp P_3\)
	\(\vdots\)
	\(P_{n-1} \imp P_n\)
\(\therefore\)	\(P_1 \imp P_n\).

	\(P \imp Q\)
	\(Q \imp R\)
\(\therefore\)	\(P \imp R\)