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}




  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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: