hi, im stucked at this problem and i dont know, how to move on.
The problem sounds like:
we have N stacked triangles (picture) We color edges of these triangles,that way where at least one edge in each triangle is colored.How many ways we have to color these edges.
In the picture you can see, there is help. That sounds:
Finding recursion divide into two cases- a)edge 1,2 is not colored.
b) atleast one of 1,2 edge is colored
I appreciate every help.
On
Consider that the stack of triangles is growing from left to right, so that the next triangle added will include edge $2$. We call the edge that will be shared with then next triangle (edge $2$ in the picture) the "last edge".
Let $c_n$ be the number of admissible stacks of $n$ triangles in which the last edge is colored, and let $u_n$ be the number of admissible stacks of $n$ triangles in which the last edge is uncolored.
Now if the last edge is colored, all $4$ ways to color the two remaining edges of the next triangle give an admissible stack of $n+1$ triangles. In two cases the last edge of the augmented stack is colored, and in two it is not. On the other hand, if the last edge is uncolored, then there are only $3$ ways to color the two remaining edges, as we must color at least one of them. Two ways give a stack whose last edge is colored, and one gives a stack with the last edge uncolored.
We can summarize the last paragraph as $$\begin{align} c_{n+1}&=2c_n+2u_n\tag1\\ u_{n+1}&=2c_n+u_n\tag2 \end{align}$$
The initial conditions are $$c_1=4\\u_1=3$$ as may easily be verified.
The number of admissible $n$-triangle stacks is $a_n:=c_n+u_n$
As Calvin Lin suggests in a comment, rewrite $(2)$ as $$2c_n=u_{n+1}-u_n$$ and substitute this in $(1)$: $$\frac{u_{n+2}-u_{n+1}}2 = u_{n+1}-u_n+2u_n\implies u_{n+2}=3u_{n+1}+2u_n\tag3$$
Subtracting $(2)$ from $(1)$ gives $$\begin{align} c_{n+1} &=u_{n+1}+u_n\\ &=3u_n+2u_{n-1}+3u_{n-1}+2u_{n-2}\\ &=3u_n+5u_{n-1}+2u_{n-2}\\ &=3(u_n+u_{n-1})+2(u_{n-1}+u_{n-2})\\ &=3c_n+2c_{n-1}\tag4 \end{align}$$
Now the recurrences $(3)$ and $(4)$ clearly give
$$a_{n+2}=3a_{n+1}+2a_n$$
Given the initial conditions, this can be solved in the to give an explicit formula for $a_n$. It's a second-order linear difference equation (recurrence relation) with constant coefficients.
Computation give the initial sequence $$7, 25, 89, 317, 1129, 4021, 14321, 51005, 181657, 646981, 2304257$$
I put this into OEIS and found A007484. The page gives the explicit formula, so you can check.
Instead of linear recurrence relation, one can analyze this problem using transfer matrix.
Let $T_1,\ldots,T_n$ be the $n$ triangles from left to right.
For $1 \le k \le n$, let $e_{k-1}$ be the left edge, $e_k$ be the right edge and $h_k$ be the horizontal edges of triangle $T_k$.
For $0 \le k \le n$, let $u_k = 1$ if $e_k$ is colored and $0$ otherwise.
For each triangle, let $N_k(u_{k-1},u_k)$ be the possible choices to coloring of $h_k$ to meet the constraint (at least one edge of $T_k$ is colored) given $u_{k-1}$ and $u_{k}$.
It is easy to see
$$N_k(u_{k-1},u_k) = \begin{cases}1, & u_{k-1} = u_k = 0\\ 2,& \text{otherwise}\end{cases}$$
The total number of triangles we want, let's call it $\mathcal{N}_n$, equals to following sum over all possible choices of $u_0,\ldots,u_n$. $$\mathcal{N} = \sum_{u_0,\ldots,u_n \in \{0,1\}} N_1(u_0,u_1)N_2(u_1,u_2)\cdots N_n(u_{n-1},u_n)$$
Let $\Delta$ be the $2 \times 2$ matrix $\begin{bmatrix}1 & 2\\2 & 2\end{bmatrix}$ (with indices running over $0$ and $1$). In terms of $\Delta$, above sum can be rewritten as
$$\mathcal{N}_n = \sum_{u_0,\ldots,u_n \in \{0,1\}} \Delta_{u_0u_1}\Delta_{u_1u_2}\ldots\Delta_{u_{n-1}u_n}$$
Replace inner sums by matrix product and let $U$ be the $2 \times 2$ matrix with all entries $1$, we can rewrite above sum as
$$\mathcal{N}_n = \sum_{u_0,u_n\in\{0,1\}} (\Delta^n)_{u_0u_n} = {\rm Tr}(\Delta^n U)\tag{*1}$$
$\Delta$ has two simple eigenvalues $\lambda_{\pm} = \frac{3 \pm \sqrt{17}}{2}$. By Cayley Hamiltion theorem, we have
$$(\Delta - \lambda_+ I_2)(\Delta - \lambda_- I_2) = 0 \quad\implies\quad \Delta (\Delta - \lambda_{\pm}I_2) = \lambda_{\mp}(\Delta - \lambda_{\pm}I_2)\tag{*2} $$ Decompose $I_2$ as $\frac{1}{\lambda_{-}-\lambda_{+}}((\Delta - \lambda _{+}I_2) - (\Delta - \lambda_{-}I_2))$ and apply $\Delta^n$ on both sides. $(*2)$ tell us
$$\Delta^n = \frac{1}{\lambda_{-} - \lambda_{+}}\left(\lambda_{-}^n(\Delta - \lambda_{+}I_2) - \lambda_{+}^n(\Delta - \lambda_{-}I_2)\right)$$
Substitute this into $(*1)$ and notice ${\rm Tr}(\Delta U) = 7$ and ${\rm Tr}(U) = 2$, we obtain following closed form of $\mathcal{N}_n$:
$$\begin{align}\mathcal{N}_n &= \frac{1}{\lambda_{+} - \lambda_{-}} \left(\lambda_{+}^n (7 - 2\lambda_{-}) - \lambda_{-}^n(7 - 2\lambda_{+})\right)\\ &= \frac{1}{\sqrt{17}} \left[(4 + \sqrt{17})\left(\frac{3+\sqrt{17}}{2}\right)^n - (4-\sqrt{17})\left(\frac{3-\sqrt{17}}{2}\right)^n\right] \end{align} $$
For the first few $n$, this redproduces the number on OEIS A007484 $$(\mathcal{N}_1,\mathcal{N}_2,\ldots) = (7,25,89,317,1129,4021,14321,51005,181657,646981,...)$$