1

Given the recurrence system: \begin{equation*} \begin{cases} T_n = T_{n-1} + S_n, &\\ S_n = T_{n-1} + S_{n-1} & \end{cases} \end{equation*}

And we know $T_0 = 1, S_0 = 0$.

I tried to solve it the following way:

Using generating functions I represent the system as \begin{equation*} \begin{cases} \mathfrak{T}(t) - 1 = \mathfrak{T}(t) + \mathfrak{S}(t), &\\ \mathfrak{S}(t) = \mathfrak{T}(t) + \mathfrak{S}(t) & \end{cases} \end{equation*}

But solving obtained system of equation I conclude that $\mathfrak{T} = 0$ and $\mathfrak{S} = -t$. It seems wrong for me. Possibly is my way of solving wrong?

J.Exactor
  • 215

1 Answers1

0

Use generating functions, $S(z) = \sum_{n \ge 0} S_n z^n$ and similarly $T(z)$. Shift indices:

$\begin{align} S_{n + 1} &= S_n + T_n \\ T_{n + 1} &= S_{n + 1} + T_n \end{align}$

Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:

$\begin{align} \frac{S(z) - S_0}{z} &= S(z) + T(z) \\ \frac{T(z) - T_0}{z} &= \frac{S(z) - S_0}{z} + T(z) \end{align}$

Plug in initial values $T_0 = 1, S_0 = 0$ and solve:

$\begin{align} S(z) &= \frac{z}{1 - 3 z + z^2} \\ T(z) &= \frac{1 - z}{1 - 3 z + z^2} \end{align}$

Next step is to split into partial fractions (ugly, quadratic irrationalities) and read off the coefficients.

vonbrand
  • 27,812