#How Does Induction Work
T is a theorem with a parameter n ≥ 1.
• If we show that:
- T holds for n = 1 (or a small number d, if n ≥ d)
- For every n ≥ 1
If T holds for n
then T holds for n + 1
• Then theorem T holds for all n ≥ 1. The assumption that T holds for n is called induction hypothesis
#Strong Induction
A statement T with a parameter n is true for n = 1 and
if, for every n ≥ 1 the following holds:
T being true for every natural number m ≤ n implies that T is true for n + 1, then T is true for all natural numbers
Also, power(2) induction: induction on natural numbers that are integer powers of 2 Multiple induction: base case for one parameter required another induction on another parameter.