Combinatorial Proof

**shawn** · March 15th 2008, 12:49 PM

Thanks in advance.

**Plato** · March 15th 2008, 03:38 PM

From the way you put the question, I assume that part (a) is no problem.
Any string in $a_n$ is a string in $a_{n-1}$ with one of 1,2, or 3 added. To avoid repetition we can use only two of three. Therefore $a_n = 2 a_n$ , because $a_1 = 3$ the given result easily follows.

EDIT:
Clearly any string in $b_n$ with the last number removed is a string in $a_{n-1}$ . Therefore, taking any string in $a_{n-1}$ that is not in $b_{n-1}$ and adding the same number as it begins with gives a string in $b_n$ . Thus $b_n=a_{n-1}-b_{n-1}$ .
.

**shawn** · March 17th 2008, 04:40 PM

Plato, how would I go about proving part a?
The basis would be when n=2, so their should be 6 A-sequences. How would I show that this is true? just list them?

Then what would I do for the inductive step?

Thanks!

Thread: Combinatorial Proof

LinkBack

Thread Tools

Display