View Single Post
Mar9-12, 02:54 AM
P: 7
So my professor gave us this recurrence relation to prove combinatorially for extra credit, but I was unable to figure it out.

h(n) = 5h(n-1) - 6h(n-2) + 1

This was my solution, but I couldn't figure out how to factor in the +1:
Let hn be the number of ways to arrange 0,1,2,3,4 on a 1xn string where 01,02,31,32,41,42 doesn't appear in the string.
5h(n-1) counts the # of ways to arrange the string where it begins with 0,1,2,3, or 4.
6h(n-2) counts the # of ways to arrange the string when it begins with 01,02,31,32,41 or 42.

No matter what I thought of, I couldn't solve that +1.
Phys.Org News Partner Mathematics news on
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)