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 context of assembly line scheduling
(Note: Assembly line scheduling or dynamic programming is not required to answer to the question though, it is just for information so that it shall help relating the context).
$(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. (directly without any proof, is it so trivial?)
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.
[Note: However an alternative to mathematical induction shall be more helpful 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 even mathematical induction is appreciated if I can get the intuition behind the proof)].