Proof by induction: a step-by-step template for HL AA

Proof by induction: a step-by-step template for HL AA

Proof by induction. This topic often appears on Paper 1 of the IB Maths HL AA exam. It requires precision and a clear understanding of the underlying principle. Many of my students initially find it challenging, not because the individual steps are hard, but because the structure needs to be exact. I've spent years refining how I teach this, and I've developed a template that helps students consistently earn full marks. This article outlines that step-by-step process. If you can follow this template, you'll be well-prepared for any induction question the IB throws at you.

The core idea of proof by induction is elegant: if you can show something is true for a starting case, and then show that if it's true for any case $k$, it must also be true for the next case $k+1$, then it's true for all cases after your start. Think of it like a line of dominoes: if the first domino falls, and if every falling domino knocks over the next one, then all dominoes will fall. This article focuses on sums and divisibility, which are the most common types of induction problems for HL AA.

Step 1: The Base Case ($n=1$)

Every proof by induction must start with a base case. For sums and divisibility, this almost always means showing the statement is true for $n=1$. Sometimes, the problem might specify a different starting integer, for example, "for all integers $n \ge 3$". In that situation, your base case would be $n=3$. Read the question carefully.

Let's take a common sum as an example: Prove that $1+2+3+...+n = \frac{n(n+1)}{2}$ for all positive integers $n$.

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

The right-hand side (RHS) is $\frac{1(1+1)}{2} = \frac{1(2)}{2} = 1$.

Since LHS = RHS, the statement is true for $n=1$. This step is usually straightforward but crucial for setting up the rest of the proof. If you miss this, or make a mistake here, the entire proof fails.

For a divisibility example, like "Prove that $n^3 + 2n$ is divisible by $3$ for all positive integers $n$":

For $n=1$, $1^3 + 2(1) = 1+2 = 3$. Since $3$ is divisible by $3$, the statement is true for $n=1$. This is the clear, concise way I expect my students to present this step.

Step 2: The Inductive Hypothesis ($n=k$)

This is where we assume the statement is true for some positive integer $k$. This assumption is the "if a domino falls" part of our analogy. We don't prove it for $k$; we simply state it as an assumption that allows us to move to the next step.

For the sum example: Assume that $1+2+3+...+k = \frac{k(k+1)}{2}$ for some positive integer $k$.

For the divisibility example: Assume that $k^3 + 2k$ is divisible by $3$ for some positive integer $k$. This can also be written as $k^3 + 2k = 3m$ for some integer $m$. This second form is often more useful when performing the algebraic manipulation in the next step.

Step 3: The Inductive Step ($n=k+1$)

This is the core of the proof, and usually the most algebraically intensive part. Here, we must show that IF the statement is true for $k$ (our hypothesis), THEN it must also be true for $k+1$. This is the "then it knocks over the next domino" part.

For the sum example: We want to show that $1+2+3+...+k+(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}$.

Start with the LHS of the $n=k+1$ statement:

$1+2+3+...+k+(k+1)$

From our inductive hypothesis, we know that $1+2+3+...+k = \frac{k(k+1)}{2}$. Substitute this into the expression:

$= \frac{k(k+1)}{2} + (k+1)$

Now, perform the algebra to manipulate this expression into the RHS for $n=k+1$. The common factor $(k+1)$ is a good place to start:

$= (k+1) \left( \frac{k}{2} + 1 \right)$

$= (k+1) \left( \frac{k+2}{2} \right)$

$= \frac{(k+1)(k+2)}{2}$

This matches the RHS for $n=k+1$. So, we have shown that if the statement is true for $n=k$, it is also true for $n=k+1$. The algebra here is often just careful expansion and factorisation. I remind my students that the target expression, $\frac{(k+1)(k+2)}{2}$, acts as a guide. Knowing where you need to end up can help you choose the right algebraic steps.

For the divisibility example: We want to show that $(k+1)^3 + 2(k+1)$ is divisible by $3$. Let's expand this expression:

$(k+1)^3 + 2(k+1) = (k^3 + 3k^2 + 3k + 1) + (2k + 2)$

$= k^3 + 3k^2 + 5k + 3$

Now, we need to try and incorporate our inductive hypothesis: $k^3 + 2k = 3m$. So, we need to rearrange our expression to pull out a $k^3 + 2k$ term:

$= (k^3 + 2k) + 3k^2 + 3k + 3$

Substitute $3m$ for $(k^3 + 2k)$ using our hypothesis:

$= 3m + 3k^2 + 3k + 3$

Now, factor out a $3$ from the entire expression:

$= 3(m + k^2 + k + 1)$

Since $m$, $k$, and $1$ are integers, $m + k^2 + k + 1$ is also an integer. Let's call it $P$.

$= 3P$

This shows that $(k+1)^3 + 2(k+1)$ is divisible by $3$. Therefore, if the statement is true for $n=k$, it is also true for $n=k+1$. This is a typical approach for divisibility proofs. Try to isolate the term from your inductive hypothesis. For more complex problems involving sequences or matrices, the algebraic manipulation might be different, but the principle of using the $n=k$ assumption remains the same. Students looking for additional practice with algebraic manipulation might find value in reviewing some of the content related to Paper 1 topics, like those on Paper 1 SL AA.

Step 4: The Conclusion

This step is often overlooked by students, but it's essential for a complete proof and typically carries a mark in IB examinations. It brings together all the previous steps and states the general conclusion. You're effectively saying, "Because of the base case, and because of the inductive step, the statement is true for all integers from the base case onwards."

The standard phrasing I teach my students is:

Since the statement is true for $n=1$ (or the appropriate base case), and if it is true for $n=k$ then it is true for $n=k+1$, by the principle of mathematical induction, the statement is true for all positive integers $n$ (or for all integers $n \ge \text{base case})$.

Make sure to explicitly state "by the principle of mathematical induction." This demonstrates a full understanding of the method you've used.

Common Pitfalls and How to Avoid Them

One common mistake I see is students trying to prove the $n=k$ case. Remember, for the inductive hypothesis, you assume it's true. Your job is to use that assumption to prove $n=k+1$. Another pitfall is algebraic errors in the inductive step. These proofs often involve careful manipulation of fractions, polynomial expansions, or rearranging terms. Double-check your algebra, especially when dealing with common factors or bringing terms to a common denominator.

Sometimes, questions might involve induction with inequalities or more complex sequences. While the algebra changes, the four-step template remains constant. For those aiming for top marks, exploring different types of induction problems beyond sums and divisibility is a good idea. My study notes often cover a broader range of examples for HL AA topics.

Proof by induction is a topic that truly tests your ability to follow a structure and apply algebraic skills. By using this step-by-step template, you can approach these problems with confidence. The key is consistent practice and attention to detail. Work through various examples, making sure each step is clearly articulated and mathematically sound. Mastering induction not only secures marks but also builds a deeper appreciation for mathematical rigour, which is a core aspect of HL AA.

Remember, the IB wants to see your logical flow. Don't skip steps, and be explicit in your reasoning. Practice this template, and you'll find that these problems, which once seemed daunting, become some of the most satisfying to solve. Keep working through past paper questions on this topic; consistency is what yields results in the long run.