Proving Combinatorial Identities with Induction

The Core Idea: The Domino Effect

At its heart, mathematical induction is a very intuitive idea. Imagine you have an infinite line of dominoes, numbered 1, 2, 3, and so on. How can you be certain that all of them will fall? You don't need to watch them all topple. You only need to know two things:

1. The first domino will fall. (You give it a push.)
2. If any domino falls, it will knock over the next one. (The dominoes are spaced correctly.)

If these two conditions are met, you can confidently conclude that every single domino will eventually fall.

This "domino effect" is precisely the logic behind mathematical induction. We use it to prove that a statement, let's call it $P(n)$, is true for all positive integers $n$.

To get a clear overview of this process, let's start with a short video from Khan Academy.

The Formal Structure of an Inductive Proof

Now that you have the intuition, let's formalize the structure. As the video explained, a proof by induction consists of two parts. A valuable resource for Olympiad-level material is the booklet "Mathematical Induction for the Olympiad Enthusiast." We'll be referencing it throughout our course.

Let's read the formal definition of the Principle of Mathematical Induction (PMI) and see its components in action.

To summarize the reading, every proof by induction follows this template:

1. State the Proposition: Clearly define the statement $P(n)$ that you want to prove.
2. Base Case: Prove that $P(n_0)$ is true for the first value, which is usually $n_0=1$. This is like tipping the first domino.
3. Inductive Step:
   • Inductive Hypothesis: Assume that $P(k)$ is true for some arbitrary integer $k\ge n_0$. This is like assuming an arbitrary domino $k$ has fallen.
   • Prove the next case: Using the inductive hypothesis, prove that $P(k+1)$ must also be true. This shows that the falling domino $k$ knocks over the next one, $k+1$.

Once you have successfully completed these steps, the Principle of Mathematical Induction allows you to conclude that $P(n)$ is true for all integers $n\ge n_0$.

A Complete Walk-Through: Sum of the First $n$ Integers

Let's solidify this structure by walking through the most classic example: proving the formula for the sum of the first $n$ positive integers.

Let's recap the steps shown in the video for the proposition $P(n):1+2+\cdots +n=\frac{n(n+1)}{2}$.

• Base Case ($n=1$):
  The sum on the left is just 1. The formula on the right gives $\frac{1(1+1)}{2}=1$. Since $1=1$, the base case holds.

• Inductive Step:

  • Inductive Hypothesis: Assume $P(k)$ is true for some integer $k\ge 1$. That is, assume $1+2+\cdots +k=\frac{k(k+1)}{2}$.
  • Goal: Prove $P(k+1)$ is true. That is, prove $1+2+\cdots +k+(k+1)=\frac{(k+1)((k+1)+1)}{2}$.

  The proof proceeds by starting with the left side of the $P(k+1)$ equation and using the inductive hypothesis to transform it into the right side:

  $$\underset{\text{This is }\frac{k(k+1)}{2}\text{ by our assumption}}{\underbrace{1+2+\cdots +k}}+(k+1)$$ $$=\frac{k(k+1)}{2}+(k+1)$$ $$=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}=\frac{(k+1)((k+1)+1)}{2}$$

  This is exactly the right-hand side of the equation for $P(k+1)$. The proof is complete.

Practice Problems

The only way to become comfortable with proofs is to write them yourself. Here are a few problems to work through. This is the most important part of the lesson, so take your time and be rigorous. Structure your answers just like the example above.

1. Arithmetic Series: Prove that for all integers $n\ge 1$, the following formula holds:
   $3+7+11+\cdots +(4n-1)=n(2n+1)$
   If you get stuck, the video "Mathematical Induction Practice Problems" solves this exact problem in its first few minutes.

2. Geometric Series: Prove that for all integers $n\ge 1$:
   $1+2+4+\cdots +2^{n-1}=2^n-1$

3. The Pizza Problem: You mentioned an interest in the "pizza cutting problem." This is a classic question in combinatorial geometry. Let $R(n)$ be the maximum number of regions a pizza can be divided into by $n$ straight cuts. The formula is $R(n)=\frac{n^2+n+2}{2}$. Prove this formula is correct for all $n\ge 1$ using mathematical induction.

   • Hint: When you add the $n$-th cut, it can intersect the $n-1$ previous cuts. This means the new line passes through $n$ existing regions, splitting each one into two. This gives the recurrence $R(n)=R(n-1)+n$. Use this fact in your inductive step.

4. A Divisibility Problem: You have a background in number theory, so this should be a nice application. Prove that for all integers $n\ge 1$, the number $7^n-1$ is divisible by 6.

   • Hint: In the inductive step, try to algebraically manipulate the expression for $k+1$ to reveal the expression for $k$. For example, $7^{k+1}-1=7\cdot 7^k-1$.

Conclusion

In this lesson, we have laid the first and most important stone in our foundation for combinatorial proof. You have learned the principle of mathematical induction, understood its logical basis through the domino analogy, and seen how to structure a formal inductive proof. We have applied this method to prove identities for arithmetic and geometric series, and even made our first foray into combinatorial geometry with the pizza problem.

Key Takeaways:

• Mathematical induction is a two-step process for proving a statement $P(n)$ for all $n\ge n_0$.
• Base Case: You must first prove $P(n_0)$ is true.
• Inductive Step: You must prove that if $P(k)$ is true (the inductive hypothesis), then $P(k+1)$ must also be true.
• The structure of these proofs is a rigid but powerful template. Mastering it is key to formal mathematical reasoning.

In our next lesson, we will explore a subtle but powerful variant of this technique called strong induction. While regular induction assumes the $k$-th case is true to prove the $(k+1)$-th, strong induction allows us to assume that all cases up to $k$ are true. This will open the door to solving an even wider class of problems, particularly those involving recurrence relations.