Proof: Let be any consistent heuristic, and let be the corresponding step cost of moving from the state x to another state y. Then by the definition of consistency. To show that h is admissible, we must show that where p is the path cost of x.
Suppose there is no path from x to the goal state. In this case, is infinite, and satisfies that for any finite .
Now suppose that there is some path form x to a goal state g. Let us call intermediate nodes of a shortest path . So the shortest path from x to g is expressed as .
Now consider . Since h is consistent, since . Similarly, . By induction on n, we obtain for any k between 1 and n-1. But because is a shortest path, so that as desired.