Step 1 (Base case): Verify P(n0) is true (usually n0 = 1). Step 2 (Inductive hypothesis): Assume P(k) is true for some arbitrary k >= n0. Step 3 (Inductive step): Prove P(k+1) is true using the assumption. Both steps are necessary — the base case without induction proves nothing for general n, and induction without a valid base case has no starting point (domino analogy: first domino must fall).