In the lecture, Professor Nisan says this about the the incrementer:
But this is a special case, so it may be worthwhile to actually note what happens, how do we add a sin, 1 to a number. Well, if you look what happens if you just do addition, well, you start adding 1, if the left, rightmost bit is 0, you just turn 0 to 1 and you've got your new number. If it's 1, you turn the 1 to a 0 because you add 1 plus 1, and then you have a carry. And you move to the next bit from the right. And again, if it's 0, you turn it to 1. If it's 1 you turn it to 0, but you need to keep on going because you have another carry. So in general basically, in general what you do for the special case of adding 1 to a given number, you start from the rightmost bit. You keep on flipping bits until you reach a 0 that you flip to 1. And at that point you stop. And that's the very simple hardware to manipulate, you don't, to actually build. You don't need to write the completely general addition circuitry although you may.
Is this just the "carry select adder" with a hard coded input of 1?