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!

Homework Help: Finding recurrance relationship for stacking blocks, can u see if my logic is right?

  1. Nov 21, 2006 #1
    Hello everyone.

    I"m having troubles figuring out this recurrance relationship. The problem is the following:

    A set of bloks contains blocks of heights 1, 2, and 4 inches. Imaigne constructing towers by piling blocks of dferent heights directly on top of one another. (A tower of height 6 inches could be obtained using six 1 inch blocks, 3 2 inch blocks, one 2 inch block with one 4 inch block on top, one 4 inch block with one 2 inch block on top, and so oforth.)

    Let t_n be the number of ways to construct a tower of height n inches using blocks from the set. (assume an inifinte supply of block of each size.) Find a recurrence relation for t_1, t_2, t_3......

    Okay so i had no idea where to start so i started at
    well to form a tower of height 1, u only have 1 way, which is to place a 1 inch block, so
    t_1 = 1
    t_2 = 2
    you can either stack 2, 1 inch blocks, or one 2 inch block, so 2 ways
    t_3 = 3
    you can stack 3, 1 inch blocks or one 2 inch block with a 1 inch block or stack a 1 inch block then stack a 2 inch block, so i'm getting 3
    t_4 = 4
    you can stack, four 1 inch blocks = 1 or two 2 inch blocks = 2 or two 2 inch blocks and two 1 inch blocks = 3, or the oppposite which would be 4, or one 4 inch block = 4.
    which would be 4 total ways.

    It looks like [tex]t_n = t_{n-1} + t_{n-2} + t_{n-4}[/tex]
    but now i need the base cases, so would
    t_1 = 1
    t_2 = 2
    t_3 = 3
    t_4 = 4
    then i can find t_5 by:
    t_5 = T_4 + t_3 + t_1 = 4 + 3 + 1 = 7
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted