Verifying a recurrence relation

In the previous lesson we learned how to derive a recurrence relation through a five-step procedure that instantiated the Bellman optimality equation for a specific problem. The procedure is simple but each step has subtleties, and an error introduced at any one of them produces a recurrence that compiles but quietly computes the wrong answer.

In this lesson we will learn a verification procedure that takes the derived recurrence and pushes back against it systematically, surfacing any remaining mistakes while they are still cheap to fix.

What is a completion?

Before diving deeper into the verification steps it is important to understand what we call a completion for dynamic programming problems. Simply put, a completion is a concrete and unique solution to the original problem. It is important to note that is completely unrelated to the recurrence or the state space DAG. For a given small problem, all its completions can be written without every designing the recurrence. As we will see later, in a correctly designed recurrence one unique path in the state space DAG generally represents one completion.

Consider the example of the climbing stairs problem introduced earlier in the course which asks us to count the number of ways to reach the nth stair if we are only restricted to jump one or two steps at a time. For that problem, one completion is one unique sequence of steps from the ground to the nth stair. Note that it has nothing to do with the state space DAG or the recurrence, it is simply a unique valid solution to the original problem.