请证明

r1(n) = r2(n) = 1

r1(j) = r2(j) = r1(j+1) + r2(j+1)

Use above equations to show that r_i(j), the number of references made to f_i[j] in a recursive algorithm, equals 2^{n - j}.

证明如下：

第一步：n - j = 1
r1(j)=r2(j) = r1(j+1) + r2(j+1) = r1(n) + r2(n) = 2 = 2<sup>n - j

第二步：若n - j = k</sup>
r1(j)=r2(j) = r1(j+1) + r2(j+1) = 2^{n - j}

若当n - j = k + 1
r1(j) = r1(j+1) + r2(j+1)
因为 n - (j+1) = k，所以 r1(j) = 2^{n - (j +1)} + 2^{n - (j +1)} = 2<sup>n - j

综上，命题得证。
纪念，走出数学系后的第五个年头的一个归纳法证明。</sup>