The full set of rules and methods for proof by induction (series, divisibility, inequalities) and proof by contradiction — stripped of worked examples — so you can sit and learn the material.
Every proof by induction follows the same four lines.
1. Prove for n = 1
2. Assume for n = k
3. Prove for n = k+1
4. Conclusion.
Learn the four lines as a routine — they don’t change from question to question. Only the middle algebra changes.
Show the statement is true for n = 1 — or the first value stated (for some inequalities it starts higher, e.g. n = 4).
Sub the base value into both sides and check they agree.
Assume the statement is true for n = k.
This is the line you are allowed to use in Step 3. Write it down and label it the assumption.
Prove the statement for n = k+1.
Sub k+1 into the statement, then work it until you can bring in the assumption and reach the required result.
Write it every time:
Since true for n = 1 and n = k+1, then true for all n.
ap+q = ap · aq
This is how you peel one factor off the top power at n = k+1.
LHS = Series — the sum, written out.
RHS = Algebra — the formula.
The whole job is to show the two sides meet.
Put in the term before — the Tk+1 term — onto the assumption.
LHS becomes (the assumed sum to k) + Tk+1. RHS is the formula with k+1 subbed in for n.
Tidy the LHS algebra (common denominator, factor out) until it becomes identical to the RHS.
When the two sides match, LHS = RHS — done.
You’re proving an expression is divisible by a number (it has that number as a factor) for all n ∈ ℕ.
At n = k+1 you must end with a sum of pieces that are each clearly divisible.
Split the base to pull out the divisor, then use ap+q = ap · aq to break the top power apart.
One piece is divisible by the number (it has the divisor as a factor).
The other piece is the assumption.
The sum of two divisible things is divisible — so the result holds for k+1.
If the expression is a polynomial in n, substitute k+1 and expand.
Group it as (the assumption) + an extra piece, then show the extra piece is a clear multiple of the divisor.
Prove for the first value stated — not always n = 1.
If the question says n ≥ 4, start at n = 4.
Split off the assumed inequality, then show the leftover piece “must be” true.
Flip to compare denominators: a bigger denominator gives a smaller fraction.
To prove a statement is true, prove the opposite is false.
Assume the opposite, follow it logically until you hit something impossible — a contradiction. That kills the opposite, so the original stands.
An even number = 2n, n ∈ ℕ.
= can be divided by 2 = 2 is a factor.
Irrational ⇒ cannot be written as a fraction.
Assume the opposite: √2 is rational.
⇒ √2 = ab where a and b have no common factor.
2 = a2b2 ⇒ 2b2 = a2
a2 is even ⇒ a is even ⇒ a = 2k.
2b2 = (2k)2 = 4k2 ⇒ b2 = 2k2 ⇒ b is even.
So √2 is not rational ⇒ irrational.