title: Proof of A* algorithm's optimality when heuristics always underestimates
body: <p>I understand why A* algorithm always gives the most optimal path to a goal state when the heuristic always underestimates, but I can't create a formal proof for it.</p>
  
  <p>As far as I understand, for each path considered as it goes deeper and deeper the accuracy of <code>f(n)</code> increases until the goal state, where it is 100% accurate. Also, no incorrect paths are ignored, as estimation is less than the  actual cost; thus leading to the optimal path. But how should I create a proof for it?</p>