We ought never to allow ourselves to be persuaded of the truth of anything unless on the evidence of our own reason – René Descartes
Proof: every consistent heuristic is also admissible
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.