# Recursion Is Stupid

#### sjaguar13

A set of blocks contains blocks of heights 1, 2, and 4 inches. Imagine constructing towers of piling block of different heights directly on top of one another. Let t(n) be the number of ways to construct a tower of height n inches. Find a recurrence relation for t(1), t(2), t(3)...

Here's what I got:
There are 5 ways to make a tower of 4 inches,
There are 6 ways to make a tower of 5 inches,
There are 10 ways to make a tower of 6 inches.

t(1) = 1, t(2) = 2, and t(3) = 4

t(k) = t(k-1) + t(k-2) - 1, k >= 4

Is that right? I would guess there should be a t(k-3) in there somewhere just because they give you three numbers.

Related Introductory Physics Homework Help News on Phys.org

#### AKG

Homework Helper
First, let's say we're making a tower of 3 inches. Do we count a 2-inch block on top of a 1-inch block different from a 1-inch block on top of a 2-inch block? In other words, does the order of blocks from top to bottom matter? If so, then:

t(1) = 1
t(2) = 2
t(3) = 3
t(4) = 6
t(5) = 10
t(6) = 18
t(7) = 31
t(8) = 50

If order doesn't matter:

t(1) = 1
t(2) = 2
t(3) = 2
t(4) = 4
t(5) = 4
t(6) = 6
t(7) = 6

I can't seem to find a recurrence relation that works.

#### sjaguar13

2 on 1 is different then 1 on 2.

I got nothing. I thought it could be t(k) = t(k-1) + t(k-2) + t(k-3) -1, but that quits working near the end. Then I thought it had something to do with powers of 2, but t(5) and t(6) are too close to each other.

#### e(ho0n3

AKG said:
If order doesn't matter:

t(1) = 1
t(2) = 2
t(3) = 2
t(4) = 4
t(5) = 4
t(6) = 6
t(7) = 6

I can't seem to find a recurrence relation that works.
Assuming order doesn't matter then for n > 1

t(n) = n if n is even
t(n) = n - 1 if n is odd

It seems the recurrence relation is t(n) = t(n - 2) + 2 for n > 3. I'll play around with this some more and see what happens.

#### AKG

Homework Helper
When I said I can't seem to find a relation that works, I wrote that after deleting some other stuff, but I guess I forgot I deleted that stuff. Anyway, that stuff said that order probably matters, as the problem wouldn't be much of a problem otherwise. Since order matters, I think the first thing would be to make sure my numbers t(1) through t(8) are right. If those are wrong, then trying to find a relation with wrong numbers will just be a waste of time. Anyways, let me know if you guys agree with that, then we can see where we want to go.

I have a guess:

$$\forall n > 6,\ \ t(n) = t(n-1) + t(n-2) + t(n-3) - 3^{n-6}$$

Actually, that doesn't work either, t(9) = 96 as far as I can tell.

#### Hurkyl

Staff Emeritus
Gold Member
Well, your problem is that you're trying to guess the recurrence by looking at the numbers. It's far easier to deduce the recurrence based on the problem.

#### AKG

Homework Helper
Hurkyl said:
Well, your problem is that you're trying to guess the recurrence by looking at the numbers. It's far easier to deduce the recurrence based on the problem.
That's actually not true. I tried to deduce it, it wasn't easy at all. In fact, I got nowhere good, so I didn't post any of those attempts. After that I started looking at the number. I reviewed my numbers, I think I had it wrong, specifically, t(8) should have been 55. Anyways, how should this be deduced then?

#### Hurkyl

Staff Emeritus
Gold Member
Something can be far easier, yet still not be easy. Maybe it's clearer to say that it's far harder to try and guess the recurrence based on the numbers.

(Oh, and t(8) = 55)

You've conjectured several times that t(n) = t(n - 1) + (other stuff). So tell me, in what ways can a tower of size n-1 relate to a tower of size n?

#### e(ho0n3

I agree. I tried deducing the recurrence also but it gets complex and complicated very quickly.

#### AKG

Homework Helper
Hurkyl said:
You've conjectured several times that t(n) = t(n - 1) + (other stuff). So tell me, in what ways can a tower of size n-1 relate to a tower of size n?
Lots of ways. If n is odd, then the following algorithm can give t(n).

Find all combinations that give a height of n-1. Let the number of combinations be c. For each combination, let b(i) be the number of blocks in the i'th combination, let O(i) be the number of 1's in the i'th combination, and let p(i) be the number of permutations possible with the i'th combination.

$$t(n) = \sum _{i = 1} ^{c} p(i)\frac{b(i) + 1}{O(i) + 1}$$

#### Hurkyl

Staff Emeritus
Gold Member
Can you think of an easier way to make a tower of size n out of a tower of size n-1?

#### AKG

Homework Helper
Hurkyl said:
Can you think of an easier way to make a tower of size n out of a tower of size n-1?
Adding a 1-inch thing. If n is odd, then the only thing you can do is add a 1-inch block to any of the existing combinations. But to find the number requires the calculation I've given. But not only does it not work for n being even, it has nothing to do with recurrence as far as I can tell.

#### Hurkyl

Staff Emeritus
Gold Member
I'm not sure why you're making a distinction between even and odd... you can make a size n tower out of a size (n-1) tower by adding a one inch block to the top, no matter what n is...

#### NateTG

Homework Helper
AKG said:
That's actually not true. I tried to deduce it, it wasn't easy at all. In fact, I got nowhere good, so I didn't post any of those attempts. After that I started looking at the number. I reviewed my numbers, I think I had it wrong, specifically, t(8) should have been 55. Anyways, how should this be deduced then?
Hmm, if you don't care about the ordering, then the tower is a soltion to:
$$t(n)=4f+2t+1o$$
where $$f,t$$ and $$o$$ are the four, two and one inch blocks respectively.

If you're having trouble, can you figure out?
$$t'(n)=2t+1o$$

Similarly, you might have an easier time figuring out the ordered case using only blocks with size 1 and 2 instead of 1, 2 and 4.

#### e(ho0n3

Yes, but you can also take one 1-in. block from the n-1 in. tower and add a 2-in. block. Etc.

#### AKG

Homework Helper
Hurkyl said:
I'm not sure why you're making a distinction between even and odd... you can make a size n tower out of a size (n-1) tower by adding a one inch block to the top, no matter what n is...
I said:

If n is odd, then the only thing you can do is add a 1-inch block

It's not so with even n, so there is reason for distinction. Anyways, where is this going? This is a trivial fact we all certainly realized, we just haven't understood where to go with it. That, if you don't mind, is what we'd like to explore, and I think it'd be better that you guide us onwards there (you can assume we know things like n-1 + 1 = n).

#### Hurkyl

Staff Emeritus
Gold Member
Maybe if I phrase it the other way around, it will spark ideas...

Every tower of size n that has a one inch block on top can be made by taking a tower of size (n-1) and putting a one inch block on top of it...

#### NateTG

Homework Helper
e(ho0n3 said:
Yes, but you can also take one 1-in. block from the n-1 in. tower and add a 2-in. block. Etc.
I'm not sure if there is a nice recurrance for the unordered case, but as sjaguar indicated, the question is about the ordered case.

P.S. sjaguar, you're really close, so I'll give you a hint: Whats t(0) equal to?

#### e(ho0n3

NateTG said:
I'm not sure if there is a nice recurrance for the unordered case, but as sjaguar indicated, the question is about the ordered case.
What are you talking about? Read the first three posts.

#### AKG

Homework Helper
Hurkyl

Sorry, what you said doesn't help

NateTG

I think what you said gave me a hint for some reason, although I can't really say what it was that helped. Acutally, I looked at sjaguar's post and noticed that he mentioned there should be three terms because there are three number, namely 1, 2, and 4. It seems to work given the numbers:

t(n) = t(n-1) + t(n-2) + t(n-4)

This works all the way up to t(10), and it is pretty close to what sjaguar had before (which you, NateTG, said was close). Why this works I'd like to know. Actually, I'm not certain that it works.

#### Hurkyl

Staff Emeritus
Gold Member
Ok, you have the right form. Now to figure out why! I was trying not to spoil the deduction... but consider this: there are three ways to have a tower of size n: the top block could be size 1, size 2, or size 4.

#### NateTG

Homework Helper
I think what you said gave me a hint for some reason, although I can't really say what it was that helped.
There was a tacit assumption that t(0)=0 which is why sjaguar added 1 in his formula to make the result come out right for the first few terms.

#### e(ho0n3

Thanks to Hurkyl's last hint, I've figured it out. I think the best hint to give to figure out the problem is:

What are the possible choices for the top (or bottom) block of each n-inch tower config.?

#### AKG

Homework Helper
NateTG I don't think he assumed t(0) = 0, since he only gave is equation for n>3 or 4 anyways (i.e. t(0) never entered the picture).

Hurkyl, yeah, it all makes sense now, it all seems so simple.

#### AKG

Homework Helper
e(ho0n3 said:
Thanks to Hurkyl's last hint, I've figured it out. I think the best hint to give to figure out the problem is:

What are the possible choices for the top (or bottom) block of each n-inch tower config.?
But that gives it away entirely. I suppose he had little choice to either give it away or give us hints that seemed like they wouldn't help at all. Some problems, you can't really give a hint without giving it away.

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving