Mathematical Induction

Overview

In the realm of discrete mathematics, establishing the truth of statements for an infinite sequence of natural numbers often requires a specialized and robust proof technique. Mathematical Induction is precisely that tool, offering a systematic method to prove propositions that hold for all integers greater than or equal to some initial value. It provides a logical framework crucial for verifying properties across a potentially infinite domain, moving beyond mere empirical observation to rigorous logical certainty.

For aspiring data scientists, a firm grasp of mathematical induction is not just an academic exercise but a foundational skill. It is indispensable for rigorously proving the correctness and analyzing the complexity of algorithms, understanding recursive definitions, and validating properties of data structures—all critical components of the CMI curriculum. Mastery of this chapter will equip you with the ability to construct logically sound arguments, a skill highly valued in both theoretical understanding and practical application within data science.

This chapter will focus on developing your proficiency in applying the principle of induction. Expect to encounter problems that test your ability to define a suitable predicate, identify the base case, formulate the inductive hypothesis, and execute the inductive step to complete a proof. This rigorous approach to problem-solving is directly relevant to CMI examinations, where precise logical deduction and proof construction are frequently assessed to ensure a deep, verifiable understanding of core discrete mathematics concepts.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | The Principle of Induction | Learn the two steps of inductive proof. |

---

---

Learning Objectives

---

---

Now let's begin with The Principle of Induction...
## Part 1: The Principle of Induction

Introduction

The Principle of Induction is a fundamental and powerful proof technique in discrete mathematics, essential for establishing the truth of statements that hold for all natural numbers or for an infinite sequence of cases. In the context of a Masters in Data Science, understanding induction is crucial for proving the correctness of algorithms, analyzing their complexity, and validating properties of data structures, which often involve iterative or recursive definitions. This topic enables the rigorous verification of hypotheses across an infinite domain, a skill invaluable for advanced theoretical work and practical applications where correctness is paramount.

---

---

Key Concepts

#
## 1. The Well-Ordering Principle

The Principle of Mathematical Induction is deeply rooted in the fundamental property of natural numbers known as the Well-Ordering Principle. This principle provides a foundational guarantee that underpins the validity of inductive proofs.

Explanation:
This principle implies that if we have a property $P(n)$ that we claim is false for some positive integers, then there must be a smallest positive integer for which $P(n)$ is false. This idea is used in proofs by contradiction to demonstrate the validity of induction. If induction were to fail, there would be a smallest counterexample, which could then be used to derive a contradiction.

---

---

#
## 2. The Principle of Mathematical Induction (PMI)

The Principle of Mathematical Induction (PMI) is a deductive inference rule used to prove universal statements about natural numbers. It is formally stated as follows:

Worked Example: Summation Formula

Problem: Prove that the sum of the first $n$ positive integers is given by the formula $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ for all integers $n \ge 1$.

Solution:

Let $P(n)$ be the statement $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Step 1: Base Case

Show that $P(1)$ is true.

For $n=1$, the left-hand side (LHS) is:

The right-hand side (RHS) is:

Since LHS = RHS, $P(1)$ is true.

Step 2: Inductive Step

Assume $P(k)$ is true for an arbitrary integer $k \ge 1$. This is the Inductive Hypothesis (IH).

Now, we must prove that $P(k+1)$ is true, i.e., $\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2}$.

Consider the LHS of $P(k+1)$:

By the Inductive Hypothesis, we can substitute $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$:

Factor out $(k+1)$:

Combine the terms inside the parenthesis:

Rearrange to match the desired form:

This is equal to $\frac{(k+1)((k+1)+1)}{2}$, which is the RHS of $P(k+1)$.

Thus, $P(k+1)$ is true.

Step 3: Conclusion

By the Principle of Mathematical Induction, $P(n)$ is true for all integers $n \ge 1$.

Answer: The formula $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ is proven true for all $n \ge 1$.

---

---

Worked Example: Proving an Inequality

Problem: Prove Bernoulli's Inequality: For any real number $x > -1$, $(1+x)^n \ge 1+nx$ for all integers $n \ge 1$.

Solution:

Let $P(n)$ be the statement $(1+x)^n \ge 1+nx$ for a fixed $x > -1$.

Step 1: Base Case

Show that $P(1)$ is true.

For $n=1$, the LHS is:

The RHS is:

Since LHS = RHS, $(1+x)^1 \ge 1+1 \cdot x$ is true. So, $P(1)$ is true.

Step 2: Inductive Step

Assume $P(k)$ is true for an arbitrary integer $k \ge 1$. This is the Inductive Hypothesis (IH).

Now, we must prove that $P(k+1)$ is true, i.e., $(1+x)^{k+1} \ge 1+(k+1)x$.

Consider the LHS of $P(k+1)$:

Since $x > -1$, we have $1+x > 0$. We can multiply both sides of the IH by $(1+x)$ without changing the direction of the inequality:

Expand the RHS:

Rearrange the terms:

We know that $k \ge 1$ and $x^2 \ge 0$ (since $x$ is a real number). Therefore, $kx^2 \ge 0$.

Combining the inequalities, we have:

This is the statement $P(k+1)$. Thus, $P(k+1)$ is true.

Step 3: Conclusion

By the Principle of Mathematical Induction, Bernoulli's Inequality $(1+x)^n \ge 1+nx$ is true for all integers $n \ge 1$ and for any real number $x > -1$.

Answer: Bernoulli's Inequality is proven true.

---

---

#
## 3. The Principle of Strong Mathematical Induction (PSMI)

Sometimes, to prove $P(k+1)$, it is not enough to assume only $P(k)$. We might need to assume that $P(j)$ is true for all integers $j$ from $n_0$ up to $k$. This leads to the Principle of Strong Mathematical Induction.

Worked Example: Fibonacci Numbers

Problem: The Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$. Prove that $F_n < (\frac{7}{4})^n$ for all integers $n \ge 1$.

Solution:

Let $P(n)$ be the statement $F_n < (\frac{7}{4})^n$.
We need to use strong induction because $F_n$ depends on two preceding terms.

Step 1: Base Cases

We need two base cases because the recurrence $F_n = F_{n-1} + F_{n-2}$ involves two previous terms.

For $n=1$:
$F_1 = 1$
$(\frac{7}{4})^1 = 1.75$
Since $1 < 1.75$, $P(1)$ is true.

For $n=2$:
$F_2 = F_1 + F_0 = 1 + 0 = 1$
$(\frac{7}{4})^2 = \frac{49}{16} = 3.0625$
Since $1 < 3.0625$, $P(2)$ is true.

Step 2: Inductive Step

Assume $P(j)$ is true for all integers $j$ such that $1 \le j \le k$, for an arbitrary integer $k \ge 2$. This is the Strong Inductive Hypothesis (SIH).
That is, assume $F_j < (\frac{7}{4})^j$ for all $1 \le j \le k$.

Now, we must prove that $P(k+1)$ is true, i.e., $F_{k+1} < (\frac{7}{4})^{k+1}$.

For $k+1 \ge 3$, we use the definition of the Fibonacci sequence:

By the Strong Inductive Hypothesis, $P(k)$ and $P(k-1)$ are true:
$F_k < (\frac{7}{4})^k$
$F_{k-1} < (\frac{7}{4})^{k-1}$

Substitute these into the equation for $F_{k+1}$:

Factor out $(\frac{7}{4})^{k-1}$:

Simplify the term in parentheses:

We want to show $F_{k+1} < (\frac{7}{4})^{k+1}$. This means we need to show $\frac{11}{4} \le (\frac{7}{4})^2$.
Let's check this inequality:

Since $2.75 < 3.0625$, we have $\frac{11}{4} < (\frac{7}{4})^2$.

Substitute this back into the inequality for $F_{k+1}$:

This is the statement $P(k+1)$. Thus, $P(k+1)$ is true.

Step 3: Conclusion

By the Principle of Strong Mathematical Induction, $P(n)$ is true for all integers $n \ge 1$.

Answer: The inequality $F_n < (\frac{7}{4})^n$ is proven true for all $n \ge 1$.

---

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following statements can be proven using the Principle of Mathematical Induction for all positive integers $n \ge 1$?" options=["A. $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$","B. $n^2 + n + 41$ is a prime number.","C. For every integer $n \ge 2$, $n$ is a prime number.","D. $n! < 2^n$"] answer="A. $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$" hint="Consider what types of statements induction is suitable for proving." solution="Option A: This is a standard summation formula, perfectly suited for proof by mathematical induction.
Option B: While $n^2+n+41$ generates primes for many initial $n$, it is not true for all $n$ (e.g., for $n=41$, $41^2+41+41 = 41(41+1+1) = 41 \cdot 43$, which is composite). Induction proves universally true statements.
Option C: This statement is false. While $2$ and $3$ are prime, $4$ is not. Induction cannot prove a false statement.
Option D: This inequality is false for $n \ge 4$. For $n=4$, $4! = 24$ and $2^4 = 16$, so $24 \not< 16$. Induction cannot prove a false statement.
Therefore, only A can be proven by induction."
:::

:::question type="NAT" question="Consider the inequality $3^n > n^3$ for all integers $n \ge n_0$. What is the smallest integer $n_0$ for which this inequality holds true and can be proven by induction?" answer="4" hint="Test small values of $n$ to find the base case where the inequality first holds." solution="Let $P(n)$ be the statement $3^n > n^3$.
We test small values of $n$:
For $n=1$: $3^1 = 3$, $1^3 = 1$. $3 > 1$. ($P(1)$ is true)
For $n=2$: $3^2 = 9$, $2^3 = 8$. $9 > 8$. ($P(2)$ is true)
For $n=3$: $3^3 = 27$, $3^3 = 27$. $27 \not> 27$. ($P(3)$ is false)
For $n=4$: $3^4 = 81$, $4^3 = 64$. $81 > 64$. ($P(4)$ is true)

The inequality $3^n > n^3$ is true for $n=1, 2$ and for $n=4$. However, for an inductive proof, we need a contiguous range starting from $n_0$. Since $P(3)$ is false, we cannot use $n_0=1$ or $n_0=2$. The first value for which the inequality holds and can serve as the base for a continuous inductive argument is $n=4$.

Let's quickly check the inductive step for $n \ge 4$:
Assume $3^k > k^3$ for $k \ge 4$.
We want to show $3^{k+1} > (k+1)^3$.
$3^{k+1} = 3 \cdot 3^k > 3 \cdot k^3$.
We need to show $3k^3 > (k+1)^3$.
$3k^3 > k^3 + 3k^2 + 3k + 1$.
This means we need $2k^3 - 3k^2 - 3k - 1 > 0$.
For $k=4$, $2(64) - 3(16) - 3(4) - 1 = 128 - 48 - 12 - 1 = 67 > 0$.
The function $f(k) = 2k^3 - 3k^2 - 3k - 1$ is increasing for $k \ge 2$.
Thus, the inductive step holds for $k \ge 4$.
The smallest integer $n_0$ is 4."
:::

:::question type="SUB" question="Prove by mathematical induction that for every positive integer $n$, $n^3 + 2n$ is divisible by $3$." answer="Divisibility by 3 proven" hint="In the inductive step, manipulate the expression for $(k+1)^3 + 2(k+1)$ to reveal $k^3+2k$ and a multiple of 3." solution="Let $P(n)$ be the statement that $n^3 + 2n$ is divisible by $3$.

Base Case:
For $n=1$:

Since $3$ is divisible by $3$, $P(1)$ is true.

Inductive Step:
Assume $P(k)$ is true for an arbitrary positive integer $k$.
This means $k^3 + 2k$ is divisible by $3$.
So, we can write $k^3 + 2k = 3m$ for some integer $m$. (Inductive Hypothesis)

Now, we must prove that $P(k+1)$ is true, i.e., $(k+1)^3 + 2(k+1)$ is divisible by $3$.
Consider the expression for $P(k+1)$:

Expand the terms:

Rearrange and group terms to reveal $k^3 + 2k$:


By the Inductive Hypothesis, $k^3 + 2k = 3m$. Substitute this into the expression:

Factor out $3$ from the second part:

Factor out $3$ from the entire expression:

Since $m$, $k^2$, $k$, and $1$ are all integers, their sum $(m + k^2 + k + 1)$ is also an integer.
Therefore, $(k+1)^3 + 2(k+1)$ is a multiple of $3$, which means it is divisible by $3$.
Thus, $P(k+1)$ is true.

Conclusion:
By the Principle of Mathematical Induction, $n^3 + 2n$ is divisible by $3$ for all positive integers $n$."
:::

:::question type="MSQ" question="Let $P(n)$ be the statement $n! > 2^n$. For which of the following values of $n$ is $P(n)$ true?" options=["A. $n=1$","B. $n=2$","C. $n=3$","D. $n=4$"] answer="D" hint="Calculate $n!$ and $2^n$ for each option." solution="Let's evaluate $n!$ and $2^n$ for each option:
A. $n=1$: $1! = 1$, $2^1 = 2$. $1 \not> 2$. So $P(1)$ is false.
B. $n=2$: $2! = 2$, $2^2 = 4$. $2 \not> 4$. So $P(2)$ is false.
C. $n=3$: $3! = 6$, $2^3 = 8$. $6 \not> 8$. So $P(3)$ is false.
D. $n=4$: $4! = 24$, $2^4 = 16$. $24 > 16$. So $P(4)$ is true.

Therefore, $P(n)$ is true only for $n=4$ among the given options. This inequality can be proven by induction for $n \ge 4$."
:::

:::question type="SUB" question="Prove by mathematical induction that for $n \ge 1$, $\sum_{i=1}^{n} (2i-1) = n^2$." answer="Sum of first $n$ odd integers is $n^2$ proven" hint="For the inductive step, add the $(k+1)$-th odd number, $2(k+1)-1$, to the sum for $k$ terms." solution="Let $P(n)$ be the statement $\sum_{i=1}^{n} (2i-1) = n^2$.

Base Case:
For $n=1$:
LHS: $\sum_{i=1}^{1} (2i-1) = 2(1)-1 = 1$
RHS: $1^2 = 1$
Since LHS = RHS, $P(1)$ is true.

Inductive Step:
Assume $P(k)$ is true for an arbitrary positive integer $k$.
This means $\sum_{i=1}^{k} (2i-1) = k^2$. (Inductive Hypothesis)

Now, we must prove that $P(k+1)$ is true, i.e., $\sum_{i=1}^{k+1} (2i-1) = (k+1)^2$.
Consider the LHS of $P(k+1)$:

By the Inductive Hypothesis, we substitute $\sum_{i=1}^{k} (2i-1) = k^2$:

Simplify the term in parentheses:


This expression is a perfect square:

This is the RHS of $P(k+1)$.
Thus, $P(k+1)$ is true.

Conclusion:
By the Principle of Mathematical Induction, $\sum_{i=1}^{n} (2i-1) = n^2$ is true for all positive integers $n$."
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Let $P(n)$ be the statement $\sum_{i=1}^{n} (2i-1) = n^2$. For which of the following steps is the reasoning correct in an inductive proof of $P(n)$ for all integers $n \ge 1$?" options=["A) To prove the base case, we show $P(0)$ is true, which is $0=0^2$.","B) Assuming $P(k)$ is true, we write $\sum_{i=1}^{k+1} (2i-1) = \left(\sum_{i=1}^{k} (2i-1)\right) + (2(k+1)-1) = k^2 + 2k+1 = (k+1)^2$. This proves $P(k+1)$ is true.","C) To prove the inductive step, we must show that $P(k+1)$ is true by substituting $k+1$ into the formula, i.e., $(k+1)^2$.","D) The inductive hypothesis states that $P(k)$ is true, so $P(k+1)$ must also be true by definition."
] answer="B" hint="Recall the two essential steps of induction: Base Case and Inductive Step. The Inductive Step requires using the assumption $P(k)$ to prove $P(k+1)$." solution="Solution:
Let's analyze each option:

* A) To prove the base case, we show $P(0)$ is true, which is $0=0^2$.
The problem statement specifies $n \ge 1$ (sum from $i=1$ to $n$). The correct base case is $P(1)$. For $n=1$, $\sum_{i=1}^{1} (2i-1) = 2(1)-1 = 1$, and $1^2 = 1$. So $P(1)$ is true. $P(0)$ is not the correct base case for this summation. Thus, A is incorrect.

* B) Assuming $P(k)$ is true, we write $\sum_{i=1}^{k+1} (2i-1) = \left(\sum_{i=1}^{k} (2i-1)\right) + (2(k+1)-1) = k^2 + 2k+1 = (k+1)^2$. This proves $P(k+1)$ is true.
This option correctly states the inductive hypothesis (assuming $P(k)$ is true, i.e., $\sum_{i=1}^{k} (2i-1) = k^2$). It then correctly breaks down the sum for $P(k+1)$, substitutes the inductive hypothesis ($k^2$), and performs the correct algebraic manipulation ($k^2 + 2k + 1 = (k+1)^2$) to arrive at the statement $P(k+1)$. This is a correct inductive step. Thus, B is correct.

* C) To prove the inductive step, we must show that $P(k+1)$ is true by substituting $k+1$ into the formula, i.e., $(k+1)^2$.
While the goal is to show $P(k+1)$ is true, simply stating the formula for $P(k+1)$ is not a proof. The proof requires showing that the sum $\sum_{i=1}^{k+1} (2i-1)$ equals $(k+1)^2$, using the inductive hypothesis. Thus, C is incorrect.

* D) The inductive hypothesis states that $P(k)$ is true, so $P(k+1)$ must also be true by definition.
This is a misunderstanding of induction. The inductive hypothesis assumes $P(k)$ is true; it does not automatically imply $P(k+1)$ is true. The entire purpose of the inductive step is to prove that $P(k+1)$ follows from $P(k)$. Thus, D is incorrect.

The final answer is $\boxed{B}$"
:::

:::question type="NAT" question="Prove that $n^3 - n$ is divisible by $3$ for all integers $n \ge 1$.
In the inductive step, we assume $k^3 - k$ is divisible by $3$ (i.e., $k^3 - k = 3m$ for some integer $m$). We then need to show that $(k+1)^3 - (k+1)$ is divisible by $3$.
When expanding and rearranging $(k+1)^3 - (k+1)$ to use the inductive hypothesis, we get:
$(k+1)^3 - (k+1) = (k^3 - k) + A k^2 + B k + C$
What is the value of $A+B+C$?" answer="6" hint="Expand $(k+1)^3 - (k+1)$ and subtract the term $(k^3-k)$ to find the polynomial $Ak^2+Bk+C$. Then sum its coefficients." solution="Solution:
We start with the expression for $P(k+1)$:
$(k+1)^3 - (k+1)$

First, expand $(k+1)^3$:
$(k+1)^3 = k^3 + 3k^2 + 3k + 1$

Now substitute this back into the expression for $P(k+1)$:
$(k+1)^3 - (k+1) = (k^3 + 3k^2 + 3k + 1) - (k+1)$
$= k^3 + 3k^2 + 3k + 1 - k - 1$
$= k^3 + 3k^2 + 2k$

We want to express this in the form $(k^3 - k) + A k^2 + B k + C$.
So we take our derived expression $k^3 + 3k^2 + 2k$ and subtract $(k^3 - k)$:
$(k^3 + 3k^2 + 2k) - (k^3 - k)$
$= k^3 + 3k^2 + 2k - k^3 + k$
$= 3k^2 + 3k$

Comparing $3k^2 + 3k$ with $A k^2 + B k + C$:
We have $A = 3$, $B = 3$, and $C = 0$.

Therefore, the sum of the coefficients $A+B+C = 3+3+0 = 6$.

To complete the inductive step, we would then show:
$(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k) = 3(m + k^2 + k)$.
Since $m + k^2 + k$ is an integer, $(k+1)^3 - (k+1)$ is divisible by $3$.

The final answer is $\boxed{6}$"
:::

:::question type="MCQ" question="Consider the inequality $n! > 2^n$. For which range of positive integers $n$ can this inequality be proven by mathematical induction?" options=["A) $n \ge 1$","B) $n \ge 2$","C) $n \ge 3$","D) $n \ge 4$"
] answer="D" hint="Test the inequality for small integer values of $n$ to find the smallest $n_0$ for the base case. Then, ensure the inductive step $k! > 2^k \implies (k+1)! > 2^{k+1}$ holds for $k \ge n_0$." solution="Solution:
We need to find the smallest integer $n_0$ for which the inequality $n! > 2^n$ holds, and for which the inductive step can be established.

Let's test small values of $n$:
* For $n=1$: $1! = 1$, $2^1 = 2$. $1 \ngtr 2$. (False)
* For $n=2$: $2! = 2$, $2^2 = 4$. $2 \ngtr 4$. (False)
* For $n=3$: $3! = 6$, $2^3 = 8$. $6 \ngtr 8$. (False)
* For $n=4$: $4! = 24$, $2^4 = 16$. $24 > 16$. (True)
* For $n=5$: $5! = 120$, $2^5 = 32$. $120 > 32$. (True)

From these tests, the smallest $n_0$ for which the base case $P(n_0)$ is true is $n_0=4$. So, $P(4)$ is our base case.

Now, let's consider the inductive step:
Assume $P(k)$ is true for some integer $k \ge n_0$, i.e., $k! > 2^k$ (Inductive Hypothesis).
We need to prove $P(k+1)$ is true, i.e., $(k+1)! > 2^{k+1}$.

Start with the left-hand side of $P(k+1)$:
$(k+1)! = (k+1) \cdot k!$

Using the Inductive Hypothesis ($k! > 2^k$):
$(k+1) \cdot k! > (k+1) \cdot 2^k$

Now we need to show that $(k+1) \cdot 2^k > 2^{k+1}$.
We can rewrite $2^{k+1}$ as $2 \cdot 2^k$. So we need to show:
$(k+1) \cdot 2^k > 2 \cdot 2^k$

Dividing both sides by $2^k$ (which is positive), we get:
$k+1 > 2$
This inequality is true if $k > 1$.

Since our base case is $n=4$, we are considering $k \ge 4$. For any $k \ge 4$, the condition $k > 1$ (and thus $k+1 > 2$) is certainly true. This means the inductive step holds for all $k \ge 4$.

Combining the base case ($n=4$) and the inductive step (holds for $k \ge 4$), the inequality $n! > 2^n$ can be proven by mathematical induction for all integers $n \ge 4$.

The final answer is $\boxed{D}$"
:::

:::question type="NAT" question="A sequence is defined by $a_1 = 1$ and $a_{n+1} = \frac{1}{2}a_n + 1$ for $n \ge 1$.
It can be proven by induction that $a_n = 2 - \frac{1}{2^{n-1}}$ for all $n \ge 1$.
What is the value of $a_4$?" answer="1.875" hint="You can either compute $a_4$ recursively using the definition or use the closed-form formula provided (which is proven by induction). Using the formula is generally faster." solution="Solution:
We are given the closed-form formula $a_n = 2 - \frac{1}{2^{n-1}}$.
We need to find the value of $a_4$. Substitute $n=4$ into the formula:

$a_4 = 2 - \frac{1}{2^{4-1}}$
$a_4 = 2 - \frac{1}{2^3}$
$a_4 = 2 - \frac{1}{8}$
$a_4 = 2 - 0.125$
$a_4 = 1.875$

Alternatively, we can compute it recursively using the definition $a_{n+1} = \frac{1}{2}a_n + 1$:
$a_1 = 1$
$a_2 = \frac{1}{2}a_1 + 1 = \frac{1}{2}(1) + 1 = 0.5 + 1 = 1.5$
$a_3 = \frac{1}{2}a_2 + 1 = \frac{1}{2}(1.5) + 1 = 0.75 + 1 = 1.75$
$a_4 = \frac{1}{2}a_3 + 1 = \frac{1}{2}(1.75) + 1 = 0.875 + 1 = 1.875$

Both methods yield the same result.

The final answer is $\boxed{1.875}$"
:::

---

What's Next?