1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial Proof of a Recurrence Relation

  1. Mar 9, 2012 #1
    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.
  2. jcsd
  3. Mar 9, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi AvgStudent! Welcome to PF! :smile:

    Can you find a "particular solution" to this recurrence relation the usual way?

    If so, just add that to your present solution. :wink:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook