#3**+2 **

**There are 8 ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 5 grid:**

**Find the number of ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 50 grid.**

\(\begin{array}{|c|c|c|c|} \hline & \text{Starts with} & \text{Starts with} \\ \text{grid:} & 2\times 1 & 2\times 2 & \text{sum} \\ \hline 2 \times 1 & 1 & 0 & 1 = F_{2} \\ \hline 2 \times 2 & 1 & 1 & 2 = F_{3} \\ \hline 2 \times 3 & 2 & 1 & 3 = F_{4} \\ \hline 2 \times 4 & 3 & 2 & 5 = F_{5} \\ \hline 2 \times 5 & 5 & 3 & 8 = F_{6} \\ \hline 2 \times 6 & 8 & 5 & 13 = F_{7} \\ \hline 2 \times 7 & 13 & 8 & 21 = F_{8} \\ \hline \ldots & \ldots \\ 2 \times 10 & 55 & 34 & 89 = F_{11} \\ \hline \ldots & \ldots \\ \hline 2 \times k & F_k & F_{k-1} & F_{k+1} \\ \hline 2\times 50 & F_{50} & F_{49} & 20365011074= F_{51} \\ \hline \end{array}\)

\(\begin{array}{|lrcll|} \hline \mathbf{ F_k \text{ is the } k^{th} \text{ Fibonacci Number:}} \\ F_1 = 1,\ F_2 = 1,\ F_3 = 2,\ F_4 = 3,\ F_5 = 5, \\ F_6 = 8,\ F_7 = 13,\ F_8 = 21,\ F_9 = 34,\ F_{10} = 55,\ldots , \\ F_{49} = 7778742049,\ F_{50} =12586269025,\ F_{51} = 20365011074 \\ \hline \end{array}\)

hint:

**Fibonacci Number as Sum of Binomial Coefficients:**

\(\begin{array}{rcll} \displaystyle F_n &=& \displaystyle \sum_{k \mathop = 0}^{\Big\lfloor {\dfrac {n - 1} 2}\Big\rfloor } \dbinom {n - k - 1} k \\ &=&\displaystyle \binom {n - 1} 0 + \binom {n - 2} 1 + \binom {n - 3} 2 + \dotsb + \binom {n - j} {j - 1} + \binom {n - j - 1} j \quad \text{ where } \quad j = \Big\lfloor {\dfrac {n - 1} 2} \Big\rfloor \\ \end{array}\)

source: https://proofwiki.org/wiki/Fibonacci_Number_as_Sum_of_Binomial_Coefficients

heurekaNov 17, 2019