Anyway,the recursion of Xn should be changed to Xk+1=aXk-bYk.

Alas, I think the problem statement is incorrect. If $a = 2$ and $b = 1$, then $x_3 = 6$, but \[ \sum_{\ell = 0}^{[3/2]} (-1)^{\ell} 2^{3 - 2 \ell} 5^{\ell} \lambda_{k,\ell} = 2 . \]If someone could fix the problem statement, that would be much appreciated.

I have done some sleuthing on the internet and found the correct problem statement. It should be as follows orl wrote: a.) Let $a,b$ be positive real numbers. Define sequence $x_k$ and $y_k$ such that \[x_0 = 1, y_0 = 0, x_{k+1} = a x_k - b y_k, \quad y_{k+1} = x_k + ay_k \text{ for } k = 0,1,2, \ldots \] Prove that \[x_k = \sum^{[k/2]}_{l=0} (-1)^l a^{k - 2 l} \left(a^2 + b \right)^l \lambda_{k,l}\] where $\lambda_{k,l} = \sum^{[k/2]}_{m=l} \binom{k}{2m} \binom{m}{l}$ In short, the recurrence relation for $y_k$ should be $y_{k+1} = x_k + ay_k$. (I also fixed the typos in the original problem statement.) We will use generating functions. We will use the fact that \[ \frac{X^m}{(1-X)^{m+1}} = \sum_{k \geq m} \binom{k}{m} X^k \tag{1} \]liberally. This fact is well known, so we shall not prove it. Let $F(X) = \sum_{k \geq 0} x_k X^k$ and $G(X) = \sum_{k \geq 0} y_k X^k$. Then \[ F(X) = 1 + \sum_{k \geq 1} (ax_{k-1} - by_{k-1}) X^k = 1 + aXF(X) - bxG(X). \]Likewise \[ G(X) = XF(X) + aXG(X) . \]We follow the standard elimination procedure to solve for $F(X)$: \[ F(X) = \frac{1-aX}{1 -2aX + (a^2+b)X^2} . \]Mow we just want to show that $F(X) = F_1(X)$, where \[ F_1(X) == \sum_{k \geq 0} \sum_{\ell = 0}^{\lfloor k/2 \rfloor} (-1)^{\ell} a^{k - 2\ell} (a^2 + b)^{\ell} \sum_{m=\ell}^{\lfloor{k/2} \rfloor} \binom{k}{2m} \binom{m}{ \ell} X^k. \]Swapping sums, we obtain that that \[ F_1(X) = \sum_{\ell \geq 0} (-1)^{\ell} (a^2 + b)^{\ell} a^{-2\ell} \sum_{m \geq \ell} \binom{m}{\ell} \sum_{k \geq 2m} \binom{k}{2m} (aX)^k. \]From (1), we have that \[ \sum_{k \geq 2m} \binom{k}{2m} (aX)^k = \frac{(aX)^{2m}}{(1 - aX)^{2m+1}} . \]Let $Y = \frac{(aX)^2}{(1-aX)^2}$. Then \[ F_1(X) = \sum_{\ell \geq 0} (-1)^{\ell} (a^2 + b)^{\ell} a^{-2\ell} \sum_{m \geq \ell} \binom{m}{\ell} \frac{(aX)^{2m}}{(1-aX)^{2m+1}} = (1-aX)^{-1} a^{-2\ell} \sum_{m \geq \ell} \binom{m}{\ell} Y^m. \]Applying (1) again gives \begin{align*} F_1(X) &= (1-aX)^{-1} \sum_{\ell \geq 0} (-1)^{\ell}(a^2+b)^{\ell} a^{-2\ell} \frac{Y^\ell}{(1-Y)^{\ell+1}} \\ &= (1-aX)^{-1} \sum _{\ell \geq 0} (-1)^{\ell} (a^2+b)^{\ell} a^{-2\ell} \frac{\frac{(aX)^{2\ell}}{(1-aX)^{2\ell}}}{(1 - \frac{(aX)^2}{(1-aX)^2})^{\ell+1}} \\ &= (1 - aX) \sum_{\ell \geq 0} (-1)^{\ell} (a^2+b)^{\ell} \frac{X^{2\ell}}{(1 - 2aX)^{\ell + 1}} \\ &= \frac{1-aX}{1 - 2aX} \sum_{\ell \geq 0} (-1)^{\ell} (a^2+b)^{\ell} \left( \frac{X^2}{1 - 2aX}\right)^{\ell} \\ &= \frac{1-aX}{1-2aX} \cdot \frac{1}{1 + (a^2+b) \frac{X^2}{1-2aX} } \\ &= \frac{1- aX}{1 - 2aX + (a^2+b) X^2} = F(X). \end{align*}Done.

I have translated the official solutions if anyone is interested. Hopefully, it is clear. Solution 1: Trigonometry Because \begin{align*} x_{k+1} + i \sqrt{b} y_{k+1} &= (a + i \sqrt b) x_k + (i a \sqrt{b} - b)y_k \\ &=(a + i \sqrt{b})x_k + i \sqrt{b} ( a + i \sqrt{b}) y_k \\ &= (x_k + i \sqrt b y_k) (a + i \sqrt b) \end{align*}and $x_0 = 1, y_0 = 0$, then \[ x_k + i \sqrt{b} y_k = (a + i \sqrt b)^k . \]Similarly, $x_k - i \sqrt{b} y_k = (a - i \sqrt{b})^k$. Therefore \[ x_k = \frac{1}{2} (( a + i \sqrt{b})^k + (a - i \sqrt{b})^k.) \]Take $\theta \in [0, \pi]$ such that \[ \cos \theta = \frac{a}{\sqrt{a^2+b}}, \cos \theta = \frac{\sqrt{b}}{\sqrt{a^2 +b}} . \]Then $x_k = (\sqrt{a^2+b})^k cos k \theta. $ Because $\cos k\theta + i \sin k \theta = (\cos \theta + i \sin \theta)^k$, \begin{align*} \cos k \theta &= \sum_{m=0}^{[k/2]} \binom{k}{2m} (i \sin \theta)^{2m} (\cos \theta)^{k - 2m} \\ &= \sum_{m=0}^{[k/2]} \binom{k}{2m}(\cos \theta)^{k-2m} (\cos^2 \theta - 1)^m \\ &= \sum_{m=0}^{[k/2]} \binom{k}{2m} (\cos \theta)^{k - 2m} \sum_{\ell =0}^m \binom{m}{\ell} (-1)^{\ell} (\cos \theta)^{m - \ell} \\ &= \sum_{\ell =0}^{[k/2]} (-1)^{\ell} (\cos\theta)^{k - 2\ell} \sum_{m = \ell}^{[k/2]} \binom{k}{2m} \binom{m}{\ell} \\ &= \sum_{\ell = 0}^{[k/2]} (-1)^{\ell} (\cos \theta)^{k - 2\ell} \lambda_{k,\ell} . \end{align*}Therefore \begin{align*} x_k &= (\sqrt{a^2+b})^k \sum_{\ell = 0}^{[k/2]} (-1)^{\ell} \left( \frac{a}{\sqrt{a^2+b}} \right)^{k - 2\ell} \lambda_{k,\ell} \\ &= \sum_{\ell = 0}^{[k/2]} (-1)^{\ell} a^{k-2\ell}(a^2 + b)^{\ell} \lambda_{k,\ell} . \end{align*} Solution 2: Characteristic Equations From the first recursive relation, we rewrite $y_k = \frac{1}{b} (ax_k - x_{k+1})$. Substituting this back into the second recursive relation gives \[ \frac{1}{b} (x_{k+1} - x_{k+2}) = x_k + \frac{a}{b} (ax_k - x_{k+1}) . \]Simplifying, \[ x_{k+2} = 2ax_{k+1} - (a^2 +b) x_k. \]This recursive relation has the characteristic polynomial \[ t^2 - 2at + a^2 +b . \]It has two distinct roots $a \pm i \sqrt{b}$. Using the initial values $x_0 =1$ and $x_1 = ax_0 - by_0 = a$ gives \begin{align*} x_k &= \frac{1}{2} (( a + i \sqrt{b})^k + (a - i \sqrt{b})^k). \\ &= \sum_{s=0}^{[k/2]} (-1)^s \binom{k}{2s} a ^{k - 2s} b^s . \end{align*}To finish the proof, we just need to compute the coefficient of $a^{k-2s} b^s$ in the second expression. Because $(a^2+b)^{\ell} = \sum_{r = 0}^{\ell} \binom{\ell}{r} a^{2(\ell - r)} b^r$, each term contributes to the $a^{k-2s} b^s$ only when $r = s$. From this, we determine the coefficient of $a^{k-2s} b^s$ is \begin{align*} &\sum_{\ell =0}^{[k/2]} (-1)^{\ell} \binom{\ell}{s} \lambda_{k,\ell} \\ &= \sum_{\ell = s}^{[k/2]} (-1)^{\ell} \binom{l}{s} \sum_{m=1}^{[k/2]} \binom{k}{2m} \binom{m}{\ell} \\ &= \sum_{\ell = s}^{[k/2]} \sum_{m=1}^{[k/2]} (-1)^{\ell} \binom{\ell}{s} \binom{k}{2m} \binom{m}{\ell} \\ &= \sum_{m=1}^{[k/2]} \binom{k}{2m} \sum_{\ell =0}^m (-1)^{\ell} \binom{\ell}{s} \binom{m}{\ell}. \end{align*}It is easy to see that $\binom{\ell}{s} \binom{m}{\ell} = (-1)^{\ell} \binom{m}{s} \binom{m-s}{\ell - s}$. So when $m > s$, \begin{align*} &\sum_{\ell = s}^m (-1)^{\ell} \binom{\ell}{s} \binom{m}{\ell} \\ &= (-1)^s \binom{m}{s} \sum_{\ell = s}^m (-1)^{\ell - s} \binom{m - s}{\ell - s} \\ &= (-1)^s \binom{m}{s}(1-1)^{m-s} = 0. \end{align*}Thus our coefficient is the desired $(-1)^s \binom{k}{2s}$.

And now the solution for b) Let $T_n$ be the length of the period of $z_{n,k}$. The answer is \[ T_n = \begin{cases} 2^{n-1} &\text{if $n \neq 2$,} \\ 4 &\text{if $n = 2$.} \end{cases} \] For $n \leq 3$, we check this by hand. Henceforth, assume that $n > 3$. First, swap sums to obtain \[ u_k = \sum_{m = 0}^{\lfloor k/2 \rfloor} \binom{k}{2m} \sum_{\ell = 0}^m \binom{m }{\ell} = \sum_{m=0}^{\lfloor k/2 \rfloor} \binom{k}{2m} 2^m . \]Immediately, we have $u_0 = u_1 = 1$. From the binomial theorem, $u_k = \frac{1}{2} ( (1 + \sqrt{2})^k + (1 - \sqrt{2})^k).$ Then $u_k$ satisfies the recurrence relation \[ u_{k+2} = 2u_{k+1} + u_k . \]This straight away implies periodicity of $z_{n,k}$; what is left is to find the length of the period. We are going to show that $z_{n,2^{n-1}} = z_{n,2^{n-1}+1} = 1$. This will imply that the period divides $2^{n-1}$ because $z_{n,k}$ is decided entirely by the two preceding terms of the sequence. Let $f(a,b) = \binom{a}{2b} 2^b$. We claim that $\nu_2(f(a,m)) \geq n$, where $a \in \{ 2^{n-1}, 2^{n-1} + 1\}$ with equality if and only if $m = 4$. First, we deal with $a = 2^{n-1}$. Then \[ \nu_2(f(2^{n-1},m)) = \nu_2 \left( \binom{2^{n-1}}{2m} 2^m \right) = m + n - 1 - \nu_2(2m) + \sum_{\ell =1}^{2m-1} \nu_2(2^{n-1} - \ell) - \nu_2(\ell) . \]Since $\nu_2(\ell) < n-1$, it follows that $\nu_2(2^{n-1} - \ell) = \nu_2(\ell)$, so this reduces to \[ \nu_2(f(2^{n-1},m)) = m + n - 2 - \nu_2(m) .\]It is easy to verify that $m \geq 2 + \nu_2(m)$ for $m \geq 3$ with equality if and only if $m = 4$. We repeat an identical line of logic for $a = 2^{n-1}+1$. This establishes the claim. Next, we show that $2^{n}$ divides $f(2^{n-1}, 1) + f(2^{n-1}, 2)$. Just directly compute that \[ f(2^{n-1}, 1) + f(2^{n-1}, 2) = 2 \binom{2^{n-1}}{2} + 4 \binom{2^{n-1}}{4} = 2^{n-1} \cdot \frac{3 \cdot( 2^{n-1}-1) + (2^{n-1}-1)(2^{n-2}-1)(2^{n-1}-3) }{3}. \]The coefficient of $2^{n-1}$ here is clearly even, so we get that $2^n$ divides the whole thing. These facts taken together show that $2^n$ divides \[ u_{2^{n-1}} - 1 = \sum_{k=1} f(2^{n-1}, m) . \]This implies that $z_{n,2^{n-1}} = 1$, as desired. Our argument about $z_{n, 2^{n-1}+1}$ will be little more subtle. We shall show that $\nu_2(u_{2^{n-1}+1-1})$ is exactly $n$. This will prove that the period is precisely $2^{n-1}$ since $2^n$ does not divide $u_{2^{n-2} + 1} - 1$. To do this, we first show that $2^{n+1}$ divides $f(2^{n-1}+1,1) + f(2^{n-1}+1,2)$.Like before, this is a direct computation. \[ f(2^{n-1}+1,1) + f(2^{n-1}+1,2) = 2 \binom{2^{n-1}+1}{2} + 4 \binom{2^{n-1}+1}{4} = 2^{n-1} \cdot \frac{ 3 \cdot (2^{n-1} + 1) + (2^{n-1} + 1)(2^{n-1} - 1)(2^{n-2} + 1)}{3} . \]Since \[ 3 \cdot (2^{n-1} + 1) + (2^{n-1} + 1)(2^{n-1} - 1)(2^{n-2} + 1) \equiv 3 + 1 \equiv 0 \pmod{4}, \]the conclusion follows. Then $f(2^{n-1} + 1, 4)$ is the only term in the sum \[ ( f(2^{n-1} + 1, 1) + f(2^{n-1} + 1, 2) ) + f(2^{n-1} + 1, 3) + f(2^{n-1} + 1, 4) + \cdots + f(2^{n-1} + 1, 2^{n-2}) = u_{2^{n-1} + 1} - 1 \]whose exponent of 2 is equal to $n$. It follows then that $\nu_2(u_{2^{n-1}+1} - 1) = 2^n$, so we are done.