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

    tiny-tim

    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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorial Proof of a Recurrence Relation
  1. Recurrence Relation (Replies: 11)

  2. Recurrence relation (Replies: 7)

  3. Recurrence relation (Replies: 6)

  4. A recurrence relation (Replies: 7)

Loading...