1
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ By the way, it looks like Fibonacci numbers $F_0 = S_0, F_1 = T_0, F_2 = S_1, F_3 = T_1$, and so on $\endgroup$ – J.Exactor Nov 1 '15 at 22:54
0
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.