Recursive definition construction

[dystplan]

Homework Statement
Construct a recursive definition for the following:

The number of ways to stack n red, white, green, and blue poker chips so that there are no two consecutive blue poker chips.

The attempt at a solution
The number of possible combinations is 4^n minus the number of combinations that involve at least two blue poker next to each other.
The number of combinations with blue poker chips next to each other for the first 6 steps is:
3 chips: BBB + BB* (x3 other chips) + *BB (x3 other chips) = 7
4 chips: BBBB + BBB* (x2 x3) + BB** (x3 x3 x3) = 34
5 chips: BBBBB + BBBB* (x2 x3) + BBB** (x3 x3 x3) + BB*** (x4 x3 x3 x3) + BB*BB (x3) = 145
6 chips: BBBBBB + BBBBB* (x2x3) + BBBB** (x3x3x3) + BBB*** (x4x3x3x3) + BB**** (x5x3x3x3x3) + BB**BB (x4x3x3) + BB*BBB (x2x3) = 1+6+27+108+405+36+6 = 589

X1 = 4
X2 = (4)(4) -1 = 15
X3 = 4^3 - 7 = 57
X4 = 4^4 - 34 = 222
X5 = 4^5 - 145 = 879
X6 = 4^6 - 589 = 3507

I'm fairly sure those are correct, but I can't see any recursive function

Thank-you in advance!

 

[Dick]

That's not really very 'inductive'. Why don't you try to split the number of ways to stack into ways that end in blue and ways that don't end in blue and write an inductive step for each separately?

 

[dystplan]

That's not really very 'inductive'. Why don't you try to split the number of ways to stack into ways that end in blue and ways that don't end in blue and write an inductive step for each separately?

You mean something like:
X1 = 4
X2 = 12 + 4 = 16;
x3 = 48 + 4*4 = 64
x4 = 192 + 4*4*4 = 256

X1 = 4
Xn = X(n-1)*4 + 4^(n-1)

The problem is that I don't see any correlation with the rate at which exclusions occur due to consecutive blue poker chips. 0, 1, 7, 34, 145 (unless I'm doing something wrong to get to that, but I don't think I am).

 

[Dick]

You mean something like:
X1 = 4
X2 = 12 + 4 = 16;
x3 = 48 + 4*4 = 64
x4 = 192 + 4*4*4 = 256

X1 = 4
Xn = X(n-1)*4 + 4^(n-1)

The problem is that I don't see any correlation with the rate at which exclusions occur due to consecutive blue poker chips. 0, 1, 7, 34, 145 (unless I'm doing something wrong to get to that, but I don't think I am).

No, I mean let B(n) be the number of ways to legally stack n chips ending in blue. Let N(n) be the number of ways that don't end in blue. Can you write B(n+1) and N(n+1) in terms of B(n) and N(n)? That would be recursive.

 

[dystplan]

I get
B(1) = 1
B(2) = 3
B(3) = 12
B(4) = 36
B(5) = 171
B(6) = 648

I still don't see any way that's recursive =[ This problem has been driving me nuts all day.

Where X represents any chip but B:
5 stack:
XXXXB x 81 possibilities
BXBXB x 9 possibilities
BXXXB x 27
XBXXB x 27
XXBXB x 27

6 stack:
XXXXXB x 243
XBXBXB x 27
BXXXXB x 81
XBXXXB x 81
XXBXXB x 81
XXXBXB x 81
BXBXXB x 27
BXXBXB x 27

 

[Dick]

I get
B(1) = 1
B(2) = 3
B(3) = 12
B(4) = 36
B(5) = 171
B(6) = 648

I still don't see any way that's recursive =[ This problem has been driving me nuts all day.

Where X represents any chip but B:
5 stack:
XXXXB x 81 possibilities
BXBXB x 9 possibilities
BXXXB x 27
XBXXB x 27
XXBXB x 27

6 stack:
XXXXXB x 243
XBXBXB x 27
BXXXXB x 81
XBXXXB x 81
XXBXXB x 81
XXXBXB x 81
BXBXXB x 27
BXXBXB x 27

The problem isn't asking you to count them. Suppose you KNOW B(n) and N(n). Can you write B(n+1) and N(n+1) in terms of those. That's all.

 

[dystplan]

The only way I know to discover B(n+1) is to have a starting place and identify a pattern to progression. I understand that the question isn't asking me to count them, but how can I calculate the recursion without a base set that indicates a recursive relationship?

 

[Dick]

The only way I know to discover B(n+1) is to have a starting place and identify a pattern to progression. I understand that the question isn't asking me to count them, but how can I calculate the recursion without a base set that indicates a recursive relationship?

Start with a chip pile in B(n) so it ends in blue. How many ways can you add another chip? Are the resulting piles in B(n+1) or N(n+1)? Now repeat the exercise for a chip pile in N(n).