If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?

Question

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible.

Why are the following statements true?

1. $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as long as the optimal path.
2. $h_2(n) + 1$ is guaranteed to be inadmissible for any $h_1(n)$

Answer 1

The sketch of the proof for your first question:

for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time for any node $n$, $f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function $h_1$ will be admissible (from Theorem 2 of Chapter 3 in "Heuristics Intelligent Search Strategies for Computer Problem Solving" book by Judera Pearl), i.e., for the node $n^*$ with optimal value, $f_1(n^*) \leqslant C^*$ that $C^*$ is the optimal value. Therefore, A* with $h_2$ will return a solution in node $n'$ by the cost of $f_2(n') \leqslant 3 f_1(n^*) \leqslant 3C^*$, as $f_1(n') \leqslant 3 f_1(n^*)$ (see more details of the proof in Theorem 13 of Chapter 13 in the same reference).

You can find more about $h_2$ under the title of $\epsilon$-admissibility as it is $(1 + \epsilon) h_1$ that $h_1$ is an admissible heuristic function. In your case, $\epsilon = 2$.