View Single Post
AvgStudent
AvgStudent is offline
#1
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 Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race