TVM solve for interest rate, revisited

[Albert Chan]

(06-25-2022 01:39 AM)Albert Chan Wrote:  h is a polynomial, so does all its derivatives.

g'' = n*(h^-1)''

(h^-1)'' = (-h^-2 * h')' = (-h^-2 * h'' + 2*h^-3 * h'^2)
(h^-1)'' * h^3 = 2*h'^2 - h*h''

RHS looks promising to be positive; it is Halley's correction denominator.
But, all we needed is to show RHS never touch 0.

Direct way is to expand RHS polynomial, and make sure no negative coefficients.
Example, say n=5

h = 1 + x + x^2 + x^3 + x^4
h' = 1 + 2 x + 3 x^2 + 4 x^3
h'' = 2 + 6 x + 12 x^2

kth column = kth term coefs. (polynomial with increasing power).

Code:

    1   2   3   4       = h'
*   1   2   3   4       = h'
-----------------   
  1*1 1*2 1*3 1*4
      2*1 2*2 2*3 2*4
          3*1 3*2 3*3 3*4
              4*1 4*2 4*3 4*4
-----------------------------
    1   4  10  20  25  24  16 = h'^2
    2   8  20  40  50  48  32 = 2*h'^2

h' has (n-1) terms ⇒ (2*h'^2) has 2*(n-1)-1 = (2n-3) terms.
For k ≤ (n-1), (2*h'^2) k-th coeff = 2*sum(j*(k+1-j), j=1..k) = 2*comb(k+2,3)

Code:

  1*2 2*3 3*4           = h''
*   1   1   1   1   1   = h
---------------------
  1*2 2*3 3*4
      1*2 2*3 3*4
          1*2 2*3 3*4
              1*2 2*3 3*4
                  1*2 2*3 3*4
-----------------------------
    2   8  20  20  20  18  12 = h*h''

For k ≤ (n-2), (h*h'') k-th coeff = sum(j*(j+1), j=1..k) = 2*comb(k+2,3)

2 sides coefs matched, (n-2) terms, from the front.
Lets flip the order, and check differences from the back, (2n-3) - (n-2) = (n-1) terms.

(2*h'^2 - h*h''), k-th coeff, from the back
= sum(2*(n-j)*(n-(k+1-j)) - (n-j)*(n-(j+1)), j=1..k)
= sum(n^2 - n*(1+2*(k-j)) + (2*j*(k+1-j) - j*(j+1)), j=1..k)
= n^2*k - n*(k^2) + 0
= n*k*(n-k)

With k = 1 .. n-1, RHS coeffs all positive; other coeffs all zero.
With no sign changes, RHS have no positive roots.      QED

Just to confirm, with bigger n

XCAS> h := (x^n - 1)/(x - 1)
XCAS> n := 10
XCAS> e2r(2*h'^2 - h*h'')

[90, 160, 210, 240, 250, 240, 210, 160, 90, 0, 0, 0, 0, 0, 0, 0, 0]

XCAS> makelist(k -> n*k*(n-k), 1, n-1)

[90, 160, 210, 240, 250, 240, 210, 160, 90]