We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
  Questions   
Sort: 
 #3
avatar+23575 
+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

 

laugh

Nov 17, 2019

14 Online Users

avatar