A friend of mine taught me the following question. He said he created the question by himself and conjectured the answer, but couldn't prove it. Though I've tried to solve the question, I've been facing difficulty.
The question is about piling rectangles. (The following is an example when we pile thirteen $1\times 2$ rectangles.)
Question : For a positive integer $n$, how many ways are there to pile $n$ $1\times 2$ rectangles ("$1$ row and $2$ columns" only) under the following conditions?
The rectangles at the bottom are next to each other.
A rectangle not at the bottom and another rectangle right below it "overlap" only half.
Let $f(n)$ be the number of such ways. Then, interestingly, we have $$f(1)=1,\quad f(2)=3,\quad f(3)=9,\quad f(4)=27,\quad f(5)=81,\cdots$$
We have $f(3)=9$ because
So, it seems that we can have $f(n)=3^{n-1}$. However, I have not been able to prove that.
I've tried to use induction. However, I have not been able to find a way to use the induction hypothesis. Since the answer seems very simple, there should be something that I'm missing. Can anyone help?