Here's an another proof based on the idea of dependencies. A dependency is a square you cannot fill until you've filled one or more other squares. If you maximize the dependencies, you minimize the number of starting pieces.

1. If you have an NxN grid, you can remove the top row and right column completely, removing (N + (N-1)) (or 2N-1) pieces. This will always work because you have N-1 pieces in every direction, thus allowing you to refill all them with no dependencies.
2. You can have up to 1 dependent piece in the right column, so you can remove a piece not in a diagonal on the second row. This makes the second piece down in the right column dependent on all the other pieces. (This also locks in the 3rd and subsequent rows to being N-1.) This brings us up to N pieces removed.
3. You can have up to 1 dependent piece in the upperleft/bottomright diagonal, so you can remove the piece in the second row correspdonding to that diagonal. (Remember, you cannot touch the 3rd and subsequent rows.) This brings us to 2N+1.
4. This leaves 2 pieces that end up being dependent in the top row. But, since they were already removed, we can't count them.