Consider a valid tiling of a $1 \times (2n + 1)$ rectangle. There are two cases. The middle square of the rectangle is a $1 \times 1$ tile. If the tile is red, then there are $t_n^2$ ways to tile the remaining squares; similarly there are $t_n^2$ tilings if the tile is green. The middle square of the rectangle is covered by a $1 \times 2$ domino. There are 2 ways to do that, and we have a $1 \times (n - 1)$ and a $1 \times n$ remaining, which may be tiled in $t_{n - 1} t_n$ ways. Thus $t_{2n + 1} = 2t_n^2 + 2t_{n - 1}t_n = 2t_n(t_n + t_{n - 1})$, so $t_n \mid t_{2n + 1}$ as desired.

$$t_n=2t_{n-1}+t_{n-2} \implies t_n=\frac{\left(1+\sqrt2\right)^{n+1}-\left(1-\sqrt2\right)^{n+1}}{2\sqrt2}$$Now just divide $\frac{t_{2n+1}}{t_n}$

It's a simple case of recurrence relations and nothing else

Mate007 wrote: It's a simple case of recurrence relations and nothing else Well, i guess you do realise that your post makes absolutely no contribution to the topic.

I just did the same as rd 1452002

rd1452002 wrote: $$t_n=2t_{n-1}+t_{n-2} \implies t_n=\frac1{2\sqrt2}[(1+\sqrt2)^{n+1}-(1-\sqrt2)^{n+1}]$$Now just divide $\frac{t_{2n+1}}{t_n}$ Was it required to derive the result for the general solution of the recurrence relation or just stating that the general solution is of the given form was sufficient?

Deriving it is necessary, a short sketch should have sufficed.

rd1452002 wrote: Deriving it is necessary, a short sketch should have sufficed. I thought it is well known result and so i just wrote that the general solution is of the form $A(r_{1})^{n}$ $+$ $B(r_{2})^{n}$ where $r_{1}$ , $r_{2}$ are the roots of the characteristic equation and used this to find the general solution.

I doubt if too many marks would be cut for that.

I did it with matrices. I would have posted my solution but I have no idea how to write matrices in latex.

the_executioner wrote: rd1452002 wrote: $$t_n=2t_{n-1}+t_{n-2} \implies t_n=\frac1{2\sqrt2}[(1+\sqrt2)^{n+1}-(1-\sqrt2)^{n+1}]$$Now just divide $\frac{t_{2n+1}}{t_n}$ Was it required to derive the result for the general solution of the recurrence relation or just stating that the general solution is of the given form was sufficient? It depends on how much you've done. I think, you'll get full marks only you've solved the recurrence relation after stating the characteristics equation (or, difference equation).

Divisibility is only applicable for integers while the linear homogeneous recurrence contains irrational no.s So how can we prove divisibility through recurrences we would need to employ another method

@Above you can just show that the quotient is integer

But that would be the same as expanding it Can someone show the way the recurrence's solution was divided

ShivaSemwal wrote: Divisibility is only applicable for integers while the linear homogeneous recurrence contains irrational no.s So how can we prove divisibility through recurrences we would need to employ another method Note that $t_n$ is an integer, though $(1 + \sqrt{2})^{n + 1}$ may be irrational, note that the product of two irrationals or sum of two irrationals isn't necessarily irrational. \begin{align*} \frac{t_{2n+1}}{t_n} &= \frac{\left(1 + \sqrt{2}\right)^{2(n +1)} - \left(1 - \sqrt{2}\right)^{2(n +1)}}{\left(1 + \sqrt{2}\right)^{n + 1} - \left(1 - \sqrt{2}\right)^{n +1} } \\ &= \left(1 + \sqrt{2}\right)^{n + 1} + \left(1 - \sqrt2\right)^{n + 1} \\ &= \sum_{k = 0}^{n + 1} \binom{n + 1}{k} 2^{k/2} + \sum_{k = 0}^{n + 1} \binom{n + 1}{k} (-1)^k 2^{k/2} \\ &= \sum_{n + 1}^{k} \binom{n + 1}{k} 2^{k/2} \left(1+(-1)^k\right) \end{align*}If $k$ is even, $1 + (-1)^k$ is $2$ and $2^{k/2}$ is an integer, If $k$ is odd, $1 + (-1)^k$ is $0$ and hence the irrational term $2^{k/2}$ disappears.

What's the base case

we should found reccurence relation . At firt of all let'S assume we know $t_{n-1}$ and $t_{n-2}$. now foe first case we have colored $n-1$ boxes we are left with only boxes.Now we can colour either green or red to thiss box. For another case as we are left with two box we can color that box with blue, so our reccurence relation is , \[ t_n =2t_{n-1}+t_{n-2}\]. the charecterastic polynomial of the above reccurance relation is $x^2-2x-1=0$ which has two roots $1+\sqrt{2},1-\sqrt{2}$. so we can say that $t_n= \sigma (1+\sqrt{2})^n + \gamma (1-\sqrt{2})^n $ for all $n \in N$. we can count$t_2=5,t_1=2$. its enough to ensure that $t_n =\frac{1}{2\sqrt{2}}((\sqrt{2}+1)^n -(1-\sqrt{2})^{n+1}$ so $\frac{t_{2n+1}}{t_n} =(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}$. which is obviously an integer. $\Rightarrow t_n \mid t_{2n+1}$.

integrated_JRC wrote: For any natural number $n$, consider a $1\times n$ rectangular board made up of $n$ unit squares. This is covered by $3$ types of tiles : $1\times 1$ red tile, $1\times 1$ green tile and $1\times 2$ domino. (For example, we can have $5$ types of tiling when $n=2$ : red-red ; red-green ; green-red ; green-green ; and blue.) Let $t_n$ denote the number of ways of covering $1\times n$ rectangular board by these $3$ types of tiles. Prove that, $t_n$ divides $t_{2n+1}$. We have $t_n=2t_{n-1}+t_{n-2}$ for $n\geq 2$ with base case $t_1=2$ and $t_2=5$. Claim : $t_{2k+1}=t_k(t_{k-1}+t_{k+1})$ and $t_{2k}=t_k^2+t_{k-1}^2$ for all $k\geq 1$ Proof : We proceed by induction on $k$.Assume we have proved till $n\leq k$ now for $n=k+1$,we have \begin{align*}t_{2k+3} &=(2t_{2k+2}+t_{2k+1}) \\ &=2(2t_{2k+1}+t_{2k})+t_{2k+1} = 5t_{2k+1}+2t_{2k} \\ &= 5t_kt_{k-1}+5t_kt_{k+1}+2(t_k^2+t_{k-1}^2) \\ &= 5t_k(t_{k+1}-2t_k)+5t_kt_{k+1}+2t_k^2+2(t_{k+1}-2t_k)^2 \\ &= 2t_{k+1}(t_k+t_{k+1}) = t_{k+1}(t_k+t_{k+2})\end{align*}and also \begin{align*}t_{2k+2}&=2t_{2k+1}+t_{2k} \\ &= 2t_k(t_{k-1}+t_{k+1})+t_k^2+t_{k-1}^2 \\ &= 4t_k(t_k+t_{k-1})+t_k^2+t_{k-1}^2 \\ &=(2t_k+t_{k-1})^2+t_k^2 = t_{k+1}^2+t_k^2\end{align*} Hence by this claim we are done.$\square$

Lemma:$t_{n+1}=2t_n+t_{n-1}$ $$t_n =\frac{1}{2\sqrt{2}}((\sqrt{2}+1)^n -(1-\sqrt{2})^{n+1}$$

A Combinatorial Argument: Claim: $t_{2n+1} = t_{n}(t_{n+1} + t_{n-1})$ proof: Imagine a $1\times(2n+1)$ rectangular board and then write it as $n + (n+1)$. There are $t_{n}$ ways to cover the $n$ tiles and $t_{n+1}$ ways to cover the $n+1$ remaining tiles. Therefore, there are $t_{n}t_{n+1}$ ways to tile, in this manner. We can also tile the board by placing the $1\times2$ domino at the $[1,n]$ position which divides the board into an $n-1$ and an $n$, $1\times1$ tile. This gives $t_{n-1}t_{n}$ ways. Finally through addition principle we have, $t_{2n+1} = t_{n}t_{n+1} + t_{n}t_{n-1} = t_{n}(t_{n+1} + t_{n-1}) \Rightarrow t_{n}|t_{2n+1}$ as desired. $\blacksquare$

Overkill: Observe that $t_1=1$, $t_2=5$ and $tn=2t_{n-1}+t_{n-2}$. The Fibonacci Polynomials recurrence gives $t_n=F_{n+1}(2)$ for all $n\in \mathbb{N}$, hence $t_n=F_{n+1}(2)\mid F_{2(n+1)}(2)=t_{2n+1}$.

Taking the $t_{2n+1}$ case we consider the middle block. This can further be divided in 3 cases CASE 1 The middle tile is red then there will be $t_n$ ways of arranging the tile on the left and right of the middle block each SO $t_n . t_n$ This yields $t_n^2$ results. CASE 2 Similarly if the middle block is green we will again have $t_n^2$ results. CASE 3 If the middle block is the domino then the left and the right of the middle block will be split into $n$ and $n-1$ blocks. So this will yield $t_{n - 1} t_n$ results. Now the total cases will be $t_{2n + 1} = t_n^2 + t_n^2 + t_{n - 1}t_n$ $= t_n(2t_n + t_{n - 1}$ Hence proved

Note that $t_{n+1}=2t_n+t_{n-1}$ and also note and prove by induction $t_{n+k} \equiv t_{k-1}t_{n-1} \pmod{t_n}$

MV2 wrote: A Combinatorial Argument: Claim: $t_{2n+1} = t_{n}(t_{n+1} + t_{n-1})$ proof: Imagine a $1\times(2n+1)$ rectangular board and then write it as $n + (n+1)$. There are $t_{n}$ ways to cover the $n$ tiles and $t_{n+1}$ ways to cover the $n+1$ remaining tiles. Therefore, there are $t_{n}t_{n+1}$ ways to tile, in this manner. We can also tile the board by placing the $1\times2$ domino at the $[1,n]$ position which divides the board into an $n-1$ and an $n$, $1\times1$ tile. This gives $t_{n-1}t_{n}$ ways. Finally through addition principle we have, $t_{2n+1} = t_{n}t_{n+1} + t_{n}t_{n-1} = t_{n}(t_{n+1} + t_{n-1}) \Rightarrow t_{n}|t_{2n+1}$ as desired. $\blacksquare$ The Best and easiest solution here I was wondering why no one here found this.

Consider a 1x2n+1 rectangle, now Case1) theres no 1x2 domino covering the nth and n+1th square :- so no. of ways to fill = 1xn rectangle ways x 1xn+1 rectangle ways= t_n x t_n+1. Case2) otherwise (in particular there's a 1x2 domino), so number of ways = 1x(n-1) rectangle ways x 1x(n+1-1) rectangle ways = t_n-1 x t_n Summing them up we get t_2n+1 = t_n( t_n+1 + t_n-1) And its clearly divisible by t_n

It is easy to observe that $t_n=2t_{n-1}+t_{n-2}$ so just write the general term and bash it out.