Online Course Discussion Forum

A II Combinatoric, problem 7.30

 
 
Picture of Areteem Professor
Re: A II Combinatoric, problem 7.30
by Areteem Professor - Monday, July 13, 2020, 6:41 PM
 

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.