Emily and Hannah pointed out a small mistake in Problem 3b on HW 4. (Thank you!) The subindices are shifted by one. The correct recurrence should be:

Thank

Advertisements

Emily and Hannah pointed out a small mistake in Problem 3b on HW 4. (Thank you!) The subindices are shifted by one. The correct recurrence should be:

Thank

Advertisements

%d bloggers like this:

For a while I thought I was going crazy because this wasn’t working for the first three numbers (1,3,13,…), which I was pretty sure I had right. Then I realized it should be

.

That’s right now, right?

I have r_0 = 1, r_1 = 2, and r_3 = 6, …

These agree with the updated version of the recurrence relation that Federico posted above.

Oh, I misread the problem. I thought we were counting all of the paths (not just the non-negative ones)! 1, 2, 6, … sounds right to then. In fact, you can use the 1-2-6-… generating function to count all of the paths in a cool way (getting 1, 3, 13, …), and then solve a recurrence that looks like the one I gave above!