Proof by induction

The typical method

Test when n=1:
- LHS: \frac1{1\times2}=\frac12
- RHS: \frac1{1+1}=\frac12
- LHS = RHS
- So it’s true for n=1
Assume that the statement is true for n=k:
- \frac1{1\times2}+\frac1{2\times3}+\frac1{3\times4}+\cdots+\frac1{k(k+1)}=\frac k{k+1}
Test for n=k+1:
- LHS: \frac1{1\times2}+\frac1{2\times3}+\frac1{3\times4}+\cdots+\frac1{k(k+1)}+\frac1{(k+1)(k+2)}
- Check if we can make the new sum of end terms equal our expected result (\frac{k+1}{k+1+1}=\frac{k+1}{k+2}):
  - \frac k{k+1}+\frac1{(k+1)(k+2)}
  - =\frac{k(k+2)+1}{(k+1)(k+2)}
  - =\frac{k^2+2k+1}{(k+1)(k+2)}
  - =\frac{(k+1)^2}{(k+1)(k+2)}
  - =\frac{k+1}{k+2}
- So LHS: \frac{k+1}{k+2}
- RHS: \frac{k+1}{(k+1)+1}=\frac{k+1}{k+2}
- LHS = RHS
- So it’s true for n=k+1
In conclusion:
- It’s true for n=1
- IF it’s true for n=k, then it’s also true for $n=k+1
- Since it is true for n=1, by induction, it’s true for all integers n (where n \ge 1)

You might be a bit confused as to how we can get from knowing that n=1 is true, to knowing that all integers are true.

If n=k is true for a specific value of k, then the next integer must also be true. So:

We know that n=1
let k=n=1
Because the value of k is satisfied, the value of k+1 also is:
- k+1=1+1=2
Now let k=n=2
- We can do exactly the same as above to find that n=3 is also true
…and so on, for all positive integers.

Check when n=1:
- LHS: 1^2=1
- RHS: \frac16(1)(1+1)(2(1)+1)=1
- So n=1 is satisfied as it holds true!
We now assume that n=k also holds true.
Find RHS when n=k:
- =\frac16k(k+1)(2k+1)
- =\frac16(2k^2+3k+1)
- $=\frac13k^2-
Check if n=k+1 holds true:
- LHS:
  - 1^2+2^2+3^2+\cdots+k^2+(k+1)^2
  - …which is (k+1)^2 more than when n=k, or k^2+2k+1 more.
- RHS:
  - \frac16(k+1)((k+1)+1)(2(k+1)+1)
  - =\frac16(k+1)(k+2)(2k+3)
  - =\frac16(k+1)(2k^2+7k+6)
  - =\frac16(2k^3+9k^2+13k+6)
  - =\frac13k^3+\frac32k^2+\frac{13}6k+1

Question	Answer
Prove that \frac1{1\times2}+\frac1{2\times3}+\cdots+\frac1{n(n+1)} = \frac n{n+1}	Test when n=1: LHS =\frac12, RHS =\frac12. Base case true. Then for n=k assume it holds. Show for n=k+1: LHS becomes \frac k{k+1} + \frac1{(k+1)(k+2)} = \frac{k+1}{k+2}, RHS =\frac{k+1}{k+2}. Both match, so true by induction.
If n=1 is true, how do we know all integers n \ge 1 are covered?	We know n=1 true. Assuming n=k true implies n=k+1 true. Letting k=1 gives n=2 true, then k=2 gives n=3 true, and so on for all positive integers.
How do you verify the base case?	Show that the statement holds for n=1 by evaluating both sides and confirming they are equal.
What is the inductive hypothesis?	Assume the statement is true for some natural number n=k, meaning the formula holds when n=k.
What do you check in the inductive step?	Using the assumption for n=k, prove the statement is true for n=k+1, often by adding the next term to the existing sum and simplifying to the required form.
Prove 1^2+2^2+3^2+\cdots+n^2 = \frac16 n(n+1)(2n+1)	Check n=1: LHS=1, RHS=\frac16(1)(2)(3)=1. Assume true for n=k. For n=k+1: LHS becomes \frac16k(k+1)(2k+1)+(k+1)^2 = \frac16(2k^3+9k^2+13k+6). RHS becomes \frac16(k+1)(k+2)(2k+3) = \frac16(2k^3+9k^2+13k+6). Both equal, so by induction formula holds.