# HW4 #3: Small correction

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:

$(n+1)r_n = (6n-3)r_{n-1} - (n-2)r_{n-2}$

Thank

1. Brian Cruz

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

$nr_{n}=\left(6n-3\right)r_{n-1}-\left(n-1\right)r_{n-2}$.

That’s right now, right?

2. emac32

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.

3. Brian Cruz

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!