pervognsen, 6 months ago (edited 6 months ago)

@shachaf Have you seen the bijective proof of that formula based on tilings? It's very simple and pretty.

pervognsen, 6 months ago (edited 6 months ago)

@shachaf You can define F(n) as the number of tilings of a 1xn board (n-tilings) with 1x1 tiles (1-tiles) and 1x2 tiles (2-tiles). Then an (m+n)-tiling comes in two cases based on whether or not a 2-tile bridges the m part and the n part. If there's a 2-tile bridge then there's a m-1 remainder in the m part and a n-1 remainder in the n part, hence the F(m-1) F(n-1) term. Else it's a clean split and you get the F(m) F(n) term.