Prove using well ordering principle that for all $n\ge 0$, the number $T_n$ of tilings of a $n \times 2$ tetris board is : $\frac{3^{n+1} + (-1)^{n}}{4}$
I am using MIT OCW to learn this on my own.
My approach: Let there be a non empty set S with a lowest number m not satisfying the above equation. $m>0$ because $n=0$ clearly satisfies the above equation. Therefore all numbers smaller than m will satisfy the above equation. Therefore m-1 will satisfy. Then I substitute m-1 in the above equation. But after doing that I get no useful result.
What should I be doing instead ?
With the information provided alone, one cannot solve this problem. You have to add which tiles are available. As I have seen this problem before here at page 41, the tiling could be used to derive the following:
$T_{n}=2 \cdot T_{n-1} + 3\cdot T _{n-2}$.
Without this information, you cannot prove anything.
Let $P(n)$ be the statement that $T_{n}=2 \cdot T_{n-1} + 3\cdot T _{n-2}$
Now let $C$ be the set of counterexamples where $P(n)$ does not hold.
By WOP, there is a least element $m$ in $C$.
Now take $P(m-1) + P(m-2) = 2 \cdot \frac{3^{m-1+1} + (-1)^{m-1}}{4} + 3 \cdot\frac{3^{m-2+1} + (-1)^{m-2}}{4}$
Simplifying and rearranging the terms, you will get
$P(m-1) + P(m-2) = \frac{3^{m} + (-1)^{m}}{4}$ which shows that $P(n)$ holds for $m$ which is a contradiction to our original assumption.