Online Course Discussion Forum

A II Combinatoric, problem 7.30

 
 
ZhengClaire的头像
A II Combinatoric, problem 7.30
ZhengClaire - 2020年07月5日 Sunday 18:40
 

Hi, 

I am confused the location of the first 2.   

Fn+2 => has n+1 1's                                   1

          => has (n+1) - 2 1's & one 2             11  of them with different allocation of 2 

          => has (n+1) -4  1's & two 2's           9 of them

          => has (n+1) - 6 1's & three 2's        7 of them

     .....

         => start with 2 at the beginning     38th position

I don't think this is correct since the first 2 will appear at 38th position. n-2-j+1 will be negative number. What do you mean the 'first 2'?

Thank you for your help.

 
ProfessorAreteem的头像
Re: A II Combinatoric, problem 7.30
ProfessorAreteem - 2020年07月13日 Monday 18:41
 

Hi Claire,

Let's look at an example. Say $n = 6$. So we would like to show that $$F_{1} + F_{2} + F_{3} + F{4} + F_{5} + F_{6}  = F_{8} - 1. $$

We know $F_{8}$ is the number of ways we can write $8 - 1 = 7$ as the sum of $1$'s and $2$'s. Let's list them in order, depending on where the first $2$ appears.

  • There is $1$ way to write $7$ as a sum of only $1$'s: $$1 + 1 + 1+ 1+ 1+ 1+ 1.$$
  • There are $8 = F_{6}$ sums that start with $2$: $$\begin{aligned} & 2 + 1 + 1 + 1 + 1 + 1 \\ & 2 + 2 + 1 + 1 + 1 \\ & 2 + 1 + 2 + 1 + 1 \\ & 2 + 1 + 1 + 2 + 1 \\ & 2 + 1 + 1 + 1 + 2 \\ & 2 + 2 + 2 + 1 \\ & 2 + 2 + 1 + 2 \\ & 2 + 1 + 2 + 2. \\ \end{aligned}$$
  • There are $5 = F_{5}$ sums that have their first $2$ in the second position: $$\begin{aligned} & 1 + 2 + 1 + 1 + 1 + 1 \\ & 1 + 2 + 2 + 1 + 1 \\ & 1 + 2 + 1 + 2 + 1 \\ & 1 + 2 + 1 + 1 + 2 \\ & 1 + 2 + 2 + 2. \\ \end{aligned}$$
  • There are $3 = F_{4}$ sums that have their first $2$ in the third position: $$\begin{aligned} & 1 + 1 + 2 + 1 + 1 + 1 \\ & 1 + 1 + 2 + 2 + 1 \\ & 1 + 1 + 2 + 1 + 2. \\ \end{aligned}$$
  • There are $2 = F_{3}$ sums that have their first $2$ in the fourth position: $$\begin{aligned} & 1 + 1 + 1 + 2 + 1 + 1 \\ & 1 + 1 + 1 + 2 + 2. \\ \end{aligned}$$
  • There is $1 = F_{2}$ sum that has its first $2$ in the fifth position: $$1 + 1 + 1 + 1 + 2 + 1.$$
  • There is $1 = F_{1}$ sum that has its first $2$ in the sixth position: $$1 + 1 + 1 + 1+ 1+ 2.$$
Thus, $F_{8} = 1 + F_{1} + F_{2} + F_{3} + F_{4} + F_{5} + F_{6}$, as we wanted.

The idea in general is the same: there is $1$ way to have all $1$'s, thus the rest will have at least one $2$. Ignoring the $1$'s that appear before the first $2$, the sum of all $1$'s and $2$'s would be $n + 1 - j$ if the first $2$ is in the $j$th position.