Interesting Random Thought For The Day 3: Why Does This Work?

This is a classic "dynamic programming" problem that job applicants in the software industry are sometimes given. The problem is this:

Given a staircase with n steps, how many different ways can you climb it, assuming that your stride is large enough to take steps 1, 2, or 3 at a time?

The solution that people pursue most easily is the recursive solution, looking something like this:

var steps = 14;
var solution = possibilities(steps, 1) +
			possibilities(steps, 2) + possibilities(steps, 3);

function possibilities(remaining, thisStride) {
	remaining -= thisStride;
	if (remaining < 0) { return 0; }
	if (remaining == 0) { return 1; }
	return possibilities(remaining, 1) +
		possibilities(remaining, 2) + possibilities(remaining, 3);
}

(This is JavaScript by the way.)

But, there is another way to find the answer, that runs in linear time -- that is, for a given value of n, the program takes around n iterations to find the answer. It involves keeping track of the last several values calculated in the loop, and it looks something like this:

var steps = 14;
var solution = stepCombinations(steps);

function stepCombinations(g) {
	var pattern = [-1,0,0,1];
	if (g < 1) { return 0; }
	var iter = 0;
	var total = 0;
	while (iter < g) {
		total = (total * 2) - (pattern[iter % 4]);
		pattern[iter % 4] = total;
		iter++;
	}
	return total;
}

The ten dollar question is: Why does this second method work?