Proof by induction generally requires 3 steps, as outlined below. The first step, while critical, is often assumed in most definitions you come across, but I point it out here for the sake of being thorough.

Let m ∈ ℤ. To prove that P(n) is true for all integers n ≥ m, perform the following steps... 

1. Clearly define the statement you are trying to prove for all n, P(n). It may simply be a verbal statement, like "n is prime," or it may be a mathematical statement that some recursive function definition, f(n), is equivalent to the calculation you're trying to represent recursively.

2. Prove that P(m) is true. This is equivalent to saying "prove P for all minimal elements in the set" if you're dealing with a well-founded set, or "prove the basis case" if you're dealing with a recursive function. 

3. Make an assumption and use it to prove P(n). Assume that n is an is an arbitrary integer n > m, and assume that P(k) is true for all k in the interval m ≤ k < n. Prove that P(n) is true.

Suppose we came up with the following recursive definition for 2 + 4 + … + 2n.

f(n) = if n = 0 then 0 else f(n-1) + 2n

We would like to show that our recursive function definition is correct using the inductive proof process described above. What is step 1?