Seeking a combinatorial proof $F_{mn}$ always a multiple of $F_m$ I would appreciate if somebody could help me with the following problem
Q: Let $F_n$ the sequence of Fibonacci numbers, given by $F_1 = 1, F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$
Seeking a combinatorial proof 
$F_{mn}$ always a multiple of $F_m$
 A: Note that $F_n$ is the number of ways to tile a $1$-by-$(n-1)$ array with monominos and dominos.  Hence, $F_{mn}$ is the number of ways to tile a $1$-by-$(mn-1)$ array in such a manner.  However, there are two possibilities: 
(1) The squares $\big(m(n-1)-1\big)$ and $m(n-1)$ are not tied up together by a domino; in this case, there are $F_{m(n-1)}F_{m+1}$ ways to do so.
(2) The squares $\big(m(n-1)-1\big)$ and $m(n-1)$ are tiled by a single domino; in this case, there are $F_{m(n-1)-1}F_m$ ways to do so.
Hence, $F_{mn}=F_{m(n-1)}F_{m+1}+F_{m(n-1)-1}F_m$.  We can induct on $n$ to show that $F_m\mid F_{mn}$.
A: Consider the number of binary string of length $n$ with no consecutive $1$s. Denote it $b(n)$. By fixing the first bit to $1$ or $0$ we can get $b(n)=b(n-1)+b(n-2)$ and also from initial $b(1)=2,b(2)=3$ we know $b(n-2)=F_n$.
Now consider $b(n-2)$ and $b(mn-2)$. We can write $mn-2=m(n-2)+(m-1)(2)$ so we can divide the $mn-2$ bits to $m$ groups of $n-2$ bits and $m-1$ groups of $2$ bits, with each of the $2$-bit group in between two $(n-2)$-bit groups. For example if $m=3,n=6$ we have $n-2=4,mn-2=16$ and we group as $XXXX,XX,XXXX,XX,XXXX$.
Now we use the inclusion-exclusion principle to count the number of binary strings of length $mn-2$.
First we count each group separately we have $b(n-2)^m\cdot 3^{m-1}$. However we did not consider the boundary cases (for example like $XX01,10,...$) so we need to minus them out.
By inclusion-exclusion principle, the final result will be 
$b(n-2)^m\cdot 3^{m-1}-($Number of strings fixing one place to be $01,10$$)+($Number of string fixing two places to be $01,10$$)-($Number of strings fixing three places to be $01,10$$)...$
However no matter how we fix the $2$-bit groups, since they cannot simultaneously be both $01$ and $10$ we must have at least one $(n-2)$-bit group that is not a neighbour of any $1$. (If both the first and last groups both have bits fixed then there must be a group in the middle that are surrounded by two zeros) That is, when counting the number of strings while fixing some places to be $01,10$, there must be at least one $(n-2)$-bit group without any bit fixed. 
So the numbers we minus out and plus back each time during the inxlusion-exclusion must always be a multiple of $b(n-2)$ and hence the final result must be a multiple of $b(n-2)$ as well.
Hence $b(n-2)|b(mn-2)\implies F_n | F_{mn}$
