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
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'