Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?