Choosing a Proof Strategy

The Art and Science of Proof

Before diving into a proof, it's essential to have a plan of attack. Proving a theorem is not a random walk; it's a strategic process. A great proof often begins with understanding the claim's structure, playing with examples, and then consciously selecting a method that is most likely to succeed.

The following video provides an excellent high-level overview of this strategic process. It offers practical tips that are valuable for any mathematician, regardless of their specific field.

As the video suggests, your choice of strategy is deeply connected to the structure of the statement you're trying to prove. Let's formalize this by creating a "playbook" of the strategies we've learned and the telltale signs that suggest when to use them.

A Strategic Playbook for Combinatorial Proofs

A significant part of becoming proficient at proofs is pattern recognition. Certain types of problems are naturally suited to certain types of proofs. The following reading provides a fantastic and detailed summary of various proof strategies, why they work, and when to use them.

Let's synthesize the information from the video and the reading into a practical guide for combinatorial problems.

When to Use...

• Direct Proof:

  • Signal: The claim is a simple implication $P\to Q$, and you can see a clear, step-by-step path from the definitions in $P$ to the conclusion $Q$.
  • Example: "If $n$ is an odd integer, then $n^2$ is an odd integer." You can directly use the definition of an odd number ($n=2k+1$), perform algebra, and arrive at the definition of an odd number for $n^2$.
  • In Combinatorics: This is often used for proving basic properties or as part of a larger proof by cases.

• Proof by Contrapositive:

  • Signal: The claim is $P\to Q$, but the hypothesis $P$ is broad or abstract, while the negation of the conclusion, $\neg Q$, is specific and concrete. This is your go-to strategy if a direct proof seems difficult to start.
  • Example: "If $n^2$ is even, then $n$ is even." The contrapositive is "If $n$ is odd, then $n^2$ is odd," which is the straightforward direct proof we just saw.
  • In Combinatorics: "If a graph does not contain a cycle, then it is a tree." The contrapositive might be easier to handle.

• Proof by Contradiction:

  • Signal: The statement seems obviously true, but there's no clear starting point. It's especially powerful for proving non-existence ("There is no..."), uniqueness, or statements involving infinity ("There are infinitely many primes"). Assuming the opposite gives you a powerful extra hypothesis to work with.
  • Example: Proving that $\sqrt{2}$ is irrational. You assume it is rational ($p/q$) and derive a logical impossibility.
  • In Combinatorics: The "handshake lemma" example from the Formal Proof document, proving an even number of people have an odd number of friends, can be framed as a proof by contradiction. The video Proving Things by Counting then Counting Again also shows a great example where double counting leads to a contradiction.

• Proof by Mathematical Induction:

  • Signal: The claim is a statement about all natural numbers $n$ (or all integers $n\ge n_0$). The structure of the problem for size $n$ is often built upon the case for size $n-1$. This is your primary tool for proving formulas for sums (like $\sum i^2$) and properties of recursively defined objects.
  • Example: Proving ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$.
  • In Combinatorics: Proving identities over Pascal's triangle, properties of recurrence relations (a dead giveaway for strong induction), or properties of graphs as the number of vertices grows. Since you've noted struggles with induction on unfamiliar problems, a key step is to always ask: "Does this problem depend on $n$? Can I solve the $n=k+1$ case if I assume the $n=k$ case is true?"

• Combinatorial Proof (Bijective or Double Counting):

  • Signal: The claim is an identity that equates two expressions involving quantities that count things (binomial coefficients, factorials, powers, etc.). These proofs are often the most elegant and provide the most insight into why an identity is true.
  • Double Counting: Use this when you can invent a single counting question or story that both sides of the identity answer in different ways.
  • Bijective: Use this when you can identify two distinct sets whose sizes are given by the left-hand side and right-hand side of the identity, respectively. (As covered in our previous lesson).

The video below provides an excellent refresher on the double counting technique, which is a powerful way to put this strategy into practice.

Case Studies: Choosing Your Weapon

Let's apply this framework to a few novel claims. For each, we'll walk through the thought process of selecting a strategy.

Claim 1: For $n\ge 1$, prove that $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$.

• Analysis: This is an identity involving binomial coefficients.
• Candidate Strategies:
  1. Algebraic Proof: We could write out the factorial definitions of $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ and $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ and show that both sides simplify to the same expression. This is mechanical and guaranteed to work if the identity is true, but might not be insightful.
  2. Combinatorial Proof (Double Counting): This looks extremely promising. Both sides are products of integers and binomial coefficients. Can we devise a story? The expression $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ suggests a two-step process: first, choose a committee of $k$ people from $n$, then choose one of the $k$ members to be the chairperson. The expression $n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ also suggests a two-step process: first, choose one of the $n$ people to be the chairperson, then choose the remaining $k-1$ committee members from the remaining $n-1$ people.
• Verdict: A double counting proof is the most elegant and explanatory approach. It tells us why the identity is true in a way that pure algebra does not.

Claim 2: In any set of $n\ge 2$ people, there are at least two people with the same number of friends within the set. (Assume friendship is mutual).

• Analysis: This is an existence claim ("there are at least two..."). It holds for all $n\ge 2$. The number of friends is a person's "degree".
• Candidate Strategies:
  1. Induction: We could try to prove this by induction on $n$. The base case $n=2$ is trivial (both have 0 or 1 friend). The inductive step seems complicated: adding a new person changes everyone's potential friend count. It might work, but it doesn't feel natural.
  2. Contradiction: This seems like a strong candidate. The opposite would be "Assume there exists a set of $n$ people where everyone has a different number of friends." This gives us a very specific structure to work with and look for a contradiction.
  3. Direct Proof (Pigeonhole Principle): If you've seen the Pigeonhole Principle (which we will cover in a future module!), this problem screams for it. What are the possible number of friends (degrees) a person can have in a group of $n$ people? The values can range from 0 (friends with no one) to $n-1$ (friends with everyone). That's $n$ possible values. We have $n$ people (pigeons) and we want to assign them a degree (pigeonhole). But wait! Can a person have 0 friends and another have $n-1$ friends in the same group? If person A has $n-1$ friends, they are friends with everyone. If person B has 0 friends, they are friends with no one. This is a contradiction if A and B are in the same group. So, the $n$ people can only have degrees from a set of at most $n-1$ possible values. By the Pigeonhole Principle, at least two people must have the same degree.
• Verdict: Both proof by contradiction and a direct proof using the Pigeonhole Principle are excellent strategies. The choice between them depends on what tools you're expected to use. The contradiction approach is more fundamental if you haven't formally learned the Pigeonhole Principle yet.

The web resource below explores many identities and presents different proof strategies side-by-side, which is an excellent way to practice this kind of strategic thinking.

Conclusion

You have now completed the foundational module on proof techniques. You have not only learned the mechanics of constructing different types of proofs but have also started developing the strategic wisdom to select the best approach for a new problem.

Here are the key takeaways for your strategic playbook:

• Analyze the Claim: Is it an implication, an identity, an existence claim, or a statement over all natural numbers? The structure of the claim is your first clue.
• Start with Definitions: Always translate the words of the claim into precise mathematical definitions. This clarifies the start and end points of your proof.
• Consider the Candidates:
  • For if-then statements, think Direct, Contrapositive, or Contradiction.
  • For statements "for all $n$", think Induction.
  • For equations involving counting formulas, think Combinatorial (Double Counting or Bisection).
• Seek Insight, Not Just Verification: While an algebraic proof might verify an identity, a combinatorial proof often explains it. Aim for the proof that provides the most understanding.

This concludes our module on proof techniques. You've built a robust logical foundation. In our next module, "Fundamental Counting Principles," we will shift our focus from how to prove to how to count. We'll start with the Addition and Multiplication Principles, which form the bedrock of almost all combinatorial problem-solving. Your well-honed proof skills will be invaluable as we justify these new counting methods.