Proof/induction (HL emphasis)

Think of Mathematical Induction like setting up a line of dominoes. You want to prove that all the dominoes will fall down if you push the first one. You can't actually push every single domino in an infinite line, right?

So, what do you do?

• Step 1: The First Domino (Base Case): You make sure the very first domino (or the starting point) actually falls. This is like proving your statement is true for the smallest possible number, usually 1.
• Step 2: The Chain Reaction (Inductive Step): You then prove that if any domino falls (let's call it the 'k-th' domino), then the very next domino (the 'k+1-th' domino) will also fall. This is like showing that the dominoes are spaced correctly so that one falling always knocks over the next.

If you can show both of these things, then you've proven that all the dominoes will fall! You've proven your statement is true for all the numbers that come after your starting point. It's a really clever way to prove something for an endless number of possibilities without doing endless work!

Let's imagine you're trying to prove that every step on a very long, magical staircase is safe to walk on. This staircase goes on forever!

1. Base Case (The First Step): You check the very first step. You step on it, and it holds your weight. You've proven the first step is safe. This is like proving your mathematical statement works for the starting number.

2. Inductive Step (The Chain Reaction): Now, you need to prove that if you are standing on any safe step (let's call it step 'k'), then the next step (step 'k+1') will also be safe. You don't need to check every single step; you just need to show that the way the stairs are built, if one is safe, the next one automatically is too.

   • You might notice a pattern: if step 'k' is safe, maybe it means the magical builders used a special super-strong material for the next step too. So, if step 'k' is safe, step 'k+1' is also safe.

Because you've shown the first step is safe, AND you've shown that safety always leads to the next step's safety, you can confidently say that every single step on that magical, endless staircase is safe! That's exactly how Mathematical Induction works.

Here's how you use Mathematical Induction to prove a statement, usually a formula or a rule, is true for all positive integers (whole numbers like 1, 2, 3, and so on).

1. State the Proposition (P(n)): Clearly write down the statement you want to prove, usually in terms of 'n'. This 'n' represents any positive integer.
2. Base Case (P(1)): Show that the statement is true for the smallest possible value of 'n', which is usually n=1. Substitute 1 into your statement and show both sides are equal.
3. Assume P(k) is True (Inductive Hypothesis): Pretend for a moment that the statement is true for some arbitrary positive integer 'k'. This means you assume P(k) is true.
4. Prove P(k+1) is True: Using your assumption from step 3, you must now show that the statement is also true for the next integer, 'k+1'. This is the trickiest part, where you use algebra to transform P(k) into P(k+1).
5. Conclusion: Write a clear concluding statement. Explain that because the base case is true and the inductive step works, the statement P(n) is true for all positive integers 'n'.