Recurrence relation for the number of “references” to two mutually recursive function


I was going through the Dynamic Programming section of Introduction to Algorithms(2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the assembly line scheduling portion.


$ (1),(2),(3)$ are three relations as shown.

$ $ f_{1}[j] = \begin{cases} e_1+a_{1,1} &\quad\text{if } j=1\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if} j\geq2\ \end{cases}\tag 1$ $

Symmetrically,

$ $ f_{2}[j] = \begin{cases} e_2+a_{2,1} &\quad\text{if } j=1\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if} j\geq2\ \end{cases}\tag 2$ $

(where $ e_i,a_{i,j},t_{2,j-1}$ are constants for $ i=1,2$ and $ j=1,2,3,…,n$ )

$ $ f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$ $


The text tries to find the recurrence relation of the number of times $ f_i[j]$ ($ i=1,2$ and $ j=1,2,3,…,n$ ) is referenced if we write a mutual recursive code for $ f_1[j]$ and $ f_2[j]$ . Let $ r_i(j)$ denote the number of times $ f_i[j]$ is referenced.

They say that,

From $ (3)$ ,

$ $ r_1(n)=r_2(n)=1.\tag4$ $

From $ (1)$ and $ (2)$ ,

$ $ r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$ $


I could not quite understand how the relations of $ (4)$ and $ (5)$ are obtained from the three corresponding relations.

Thought I could make out intuitively that as there is only one place where $ f_1[n]$ and $ f_2[n]$ are called, which is in $ f^\star$ , so probably in $ (4)$ we get the required relation.

But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition, however I would prefer an alternative to mathematical induction as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then I shall appreciate mathematical induction as well provided the intuition is explained to me properly).