\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}

\title{Series with Applications to Finance}
\author{Burton Rosenberg}
\begin{document}
\maketitle

\subsection*{Calculus of Finite Differences}

\begin{definition}[Finite Difference]
Let $f:X\rightarrow Y$ be a function. The finite difference of $f$, $\Delta f$, is defined:
\[
\Delta f(n) = f(n+1) - f(n)
\]
\end{definition}
%
The ``telescoping sum'' gives the following analog of the Fundamental Theorem of
Calculus,
%
\begin{theorem}[Fundamental Theorem of Finite Differentials]
\[
\sum_{a \le i < b} \Delta f(i) = f(b) - f(a)
\]
\end{theorem}
%
Carefully note the bounds of the summation: non-strict at the lower
limit, strict at the upper limit. The infinitesimal calculus is not concerned,
when adding to integrals, about the infinitesimal overlap of integrals at
their boundaries. In the finite world, this is significant. The strictness of
the upper limit gives us the proper result.
%
\begin{theorem}
\[
   \sum_{a\le i < b} f(i) + \sum_{b\le i< c} f(i) = \sum_{a \le i < c} f(i)
\]
\end{theorem}
%
For the purpose of manipulation of finite differences and their summation,
the falling power gives neater results than the more familiar $n^k$. 
%
\begin{definition}[Falling Power]
The for every integer $k\ge0$, the $k$-th falling power is defined,
\[
    n^{(k)} = \left\{ \begin{array}{lll} 
                         1 & \mbox{    } & \mbox{for $k=0$} \\                            
                         n( n-1) \cdots ( n-k+1 ) & \mbox{    } & \mbox{for $k>0$} \\
                 \end{array}\right.
\]
\end{definition}
%
The following two results should be quickly recognized as analogues of the
infinitesimal calculus:
%
\begin{theorem}[Difference of Falling Powers]
For $k>0$, $\Delta n^{(k)} = k n^{(k-1)}$.
\end{theorem}
%
The proof of this is easily accomplished using the following observation:
\[
    (n+1)^{(k)} - n^{(k)} = (n+1) n^{(k-1)} - n^{(k-1)}(n-k+1)  
\]
%
\begin{corollary}[Summation of Falling Powers]
\[
   \sum_{a\le i<b} i^{(k)} =  \left. \frac{i^{(k+1)}}{(k+1)}\;\;\right |_{i=a}^b
\]
\end{corollary}
%
\begin{example}
We have yet another proof that $\sum_{i=1}^k i = (k+1)k/2$.
\end{example}
%
\begin{example}
An easy exercise in algebra gives the relation $n^2=n^{(2)}+n$.
With this substitution, the summation of $i^2$ is obvious:
\[
\sum_{1\le i<k+1} i^2 = \frac{ (k+1)^{(3)}}{3} + \frac{(k+1)^{(2)}}{2}.
\]
\end{example}
%
{\em Note:} I don't know much about $n^{(k)}$ except when $n$ and $k$ are
well positive. It would be useful in proofs to push the limits and understand
the notation better.


\subsection*{Sequences}

\begin{theorem}For $x\ne 1$,
\[
\sum_{0\le i < k} x^i = 
         \frac{1-x^k }{1-x}
\]
The series,
\[
\sum_{0\le i}^\infty x^i = \frac{1 }{1-x} 
\]
is convergent for $-1<x<1$.
\end{theorem}
%
For $x$ greater than 1 in absolute value, the series does not converge, but it can be
considered anyway as a ``formal'' series. For instance,
\[ 
   \sum_{0\le i<k}x^i = \sum_{0\le i}^\infty x^i - x^k\sum_{0\le i}^\infty x^i
   = \frac{1}{1-x} - \frac{x^k}{1-x}
\]
which at least leads to the correct final result with less memorization.

\subsection*{Applications to Finance}

\begin{example}[Simple Interest Loan]
A simple rate loan of money is paid back in equal installments,
as interest accrues on the outstanding balance. The money paid each
month goes partly to paying the monthly interest on the loan,
and partly to paying down the outstanding balance of the loan.
The payment is adjusted so that after a certain number of payments,
the loan term, the balance is zero.
The outstanding balance is also called the``principal.''
The number of payment installments is called the ``term.''
The monthly payment is called the ``rent''.
\end{example}
The formula for these loans looks complicated, but it reveals an
interesting fact, which has much meaning. Making a simple interest
loan and paying it off in installments is mathematically 
equivalent to making two seperate deals: 
\begin{enumerate}
\item Make a simple interest loan 
which you pay off with a lump sum payment at the end of the loan,
letting the interest on the initial principal accumulate.
\item Open a savings account which pays the same interest as the
loan, and make monthly installments to the account.
\end{enumerate}
At the end of the loan, the amount in the savings account equals
the amount due on the loan, so you pay off the loan with the account
balance, closing both.

At an interest $i$ per term, the amount due on a loan of
principal $p$, paid as a lump sum at the end of $n$ terms is
the principal compound with its interest $n$ times,
\[
    p(1+i)^n
\]
At the same interest, a rent of $r$ paid per term results after $n$
terms in an amount compounded by the interest according to the
length of time that rent has stayed in the bank,
\begin{eqnarray*}
    r(1+i)^{n-1}+r(1+i)^{n-2}+\ldots+r &=& r \sum_{0\le \tau < n} (1+i)^\tau \\
    &=& r \frac{1-(1+i)^n}{1-(1+i)}
\end{eqnarray*}
%
At the end of $n$ terms we now pay of the loan with the savings.
We set the above two sums equal, and by taking ratios arrive
at the amortization constant $a_{n\rceil i}$,
\[
      p/r = (1-(1+i)^{-n})/i = a_{n\rceil i} 
\]
%
The amortization constant $a_{n\rceil i}$ depends only on the ``structure'' of
the loan, the number of payments and the per term interest. It gives a
fixed ratio between principal and rent. The amortization constant can
be described as the amount of principal bought per each dollar of rent.
Its reciprocal $1/a_{n\rceil i}$ is the amount of rent required for each dollar of
principal.

Traditionally, the interest rate $i$ and term $n$ is expressed annually,
although accrued and paid monthly. Standard practice is to state the
interest rate as twelve times $i$, the true per term rate, and the 
term as one-twelfth $n$, to state by years, rather than by months.

For mathematics, the constant $a_{n\rceil i}$ pretty much exhausts the
topic. For economics, on the other hand, the game has just begun
its play. A look at the newspapers for interest rates will show that 
there is a relationship between $i$ and $n$. Usually, the longer the
loan the higher the interest rate. Sometimes, even the amount of
principal is involved, the higher the principal the higher the interest rate.

Economists try to understand the rational behind the relationship of
interest to term. These relationships are established and continuously
renegotiated by a market mechanism in which lenders bid for borrowers.
Which reminds me of the following joke.
An economist returns to his Alma Mater many years later.
Looking at a final exam he is puzzled,  ``but these
are the same questions as when I studied here!'' 
To which the professor responds, ``Yes, but the answers are all different.''

\begin{example}[APR and Junk Fees]
An often quoted figure is a loan's APR. It is an adjustment of the
stated interest rate to compensate for payments made by the borrower
to establish the loan. 
Kindly termed ``junk fees'', which we will denote by $j$ for junk,
these fees are subtracted from the 
principal $p$ and a new amortization ratio is calculated,  $a^*=(p-j)/r$ . The APR
is the interest $i^*$ such that $a^*=a_{n\rceil i^*}$.
\end{example}

When a loan is made, there are three exchanges: the lender gives the
borrower the principal $p$; the borrower might pay the lender for the
costs of making the loan, the affectionately termed junk fees $j$; 
finally, there is the mortgage: a promise for a stream of payments from the
borrower to the lender. 
The mortgage is calculated on principal $p$, but the borrower did not get $p$, rather
$p^*=p-j$, the principal net the junk fees. For this reason, it is altogether proper
to consider the stream of payments against $p^*$ rather than $p$.
Note that ``points'' are here also considered junk fees.

I am indebted to Jack M. Guttentag, Professor Emeritus of Finance at the Wharton
School, on whose web site I found this interesting relationship regarding junk fees.
Setting rents equal,
\[
   p^* = (a_{n\rceil i^*}/a_{n\rceil i})p
\]
This allows a calculation of junk fees per dollar of stated principal:
\[
   j/p = (p-p^*)/p=(1 - a_{n\rceil i^*}/a_{n\rceil i})
\]
This formula is handy. Banks vary widely in what they consider a junk fee.
For what they should, but often don't, consider junk fees, see US Code, Title 15, Chapter 41,
Section 1605, {\em Determination of finance charge.}


\begin{example}[Rule of 78]
An Auto loan, and many other consumer loans, use the Rule of 78
to calculate the balance in cases where you wish to pay off the loan
early. In that case, the outstanding balance is more than
is calculated by simple interest. 
\end{example}

The Rule of 78 begins by calculating rent from the principal and the amortization
constant. From these, a finance fee $f$ amount is deduced, $f = nr-p$, the excess
of all $n$ rent payments over the loaned principal. 
For payment $k = 1, 2, 3, \dots, n$ the amount
\[
       f_k = f \;\frac{n+1-k}{(n+1)^{(2)}/2}
\]
is first deducted from the rent to credit the finance fee. What remains is subtracted
from the principal. The denominator insures that $\sum f_k = f $. For a one year
loan, $n=12$, and the denominator equals 78, hence the name ``Rule of 78.''

This sort of loan accelerates the payment of the finance fee at the expense of
the principal. A simple interest loan at interest $i$ remains at that interest throughout
the life of the loan. A loan according to the Rule of 78 slowly decreases the interest
rate as the loan progresses. The loan is said to be ``front loaded'' --- you pay 
interest charges ahead of actually incurring the interest charge.

For simplicity, let $n$ be even. Then the unpaid finance fee after payment $n/2$ is,
\[
    f_{@n/2} = \sum_{n/2 < k \le n} f_k = f \; \frac{(n/2+1)^{(2)}/2   }{(n+1)^{(2)}/2}
    = f \; \frac{n+2}{4(n+1)}
\]
The unpaid principal is,
\begin{eqnarray*}
   p_{@n/2} &=& p - nr/2 + (f - f_{@n/2}) \\
    &=& p-nr/2 + (nr-p)(1 - (n+2)/(4(n+1))) \\
    &\approx& p-nr/2 + (3/4)(nr-p)\\
    &=& (p  + nr)/4
\end{eqnarray*}
%
Halfway through the loan the new amortization constant is then,
\[
  p_{@n/2}/r \approx ( a_{n\rceil i} + n )/4
\]
The current interest on the loan is the $i^*$ satisfying,
\[
     a_{n/2\rceil i^*} = (a_{n\rceil i}+n)/4
\]
As a numerical example, consider a 4 year 9\% loan.
The amortization constant is $a_{48|9/12\%}=40.18$, 1 dollar of rent buys a little over 40 
dollars of principal. 
After two years we find the new interest rate of the loan,
\[
(a_{48\rceil 9/12\%}+48)/4=22.05 = a_{24\rceil 8.29/12\%}
\]
The accelerated payment of finance charges has bought down the interest
rate of this loan for the remaining two years to $8.29\%$ . 

%===========================================


\subsection*{Falling and ordinary powers}

{\bf Stirling numbers.}
It is possible to transform ordinary powers into a sum of falling powers
and back again with the help of combinatorial coefficients called Stirling numbers.
To express an ordinary power as a falling power use the Stirling numbers of
the second kind. 
These are combinatorial quantities in some ways similar to the binomial coefficients.
The binomial coefficient $k$ choose $j$ is the number of ways of choosing $j$ 
objects from a set of $k$ objects. The Stirling number of the second kind $k$ subset
$j$ is the 
number of ways of forming $j$ non-empty subsets from $k$ items. 
It is denoted
$
{k\brace j}.
$

Similar to the binomial coefficient, the Stirling numbers of the second kind follow a
recurrence relation. We count the partitions of $\{1,\ldots,k\}$ by counting separately
those partitions which place $k$ in a set by itself and those which do not. For the former,
there are as many such partitions as ways to partition $\{1,\ldots,k-1\}$ into $j-1$
non-empty subsets. For the later, partition $\{1,\ldots,k-1\}$ into $j$ subsets and then
form $j$ partitions of $\{1,\ldots,k\}$ by inserting $k$ into each of the $j$ subsets.
Therefore,
\[
  {k\brace j} = j{k-1\brace j}+{k-1\brace j-1}
 \]
 It is clear that 
 $k$ subset $1$ and $k$ subset $k$ are 1; also $k$ subset $j$ is zero for $j$ equal to
 one or greater than $k$.
 
With this we can build a table, similar in spirit to the construction of Pascal's triangle, but
with a modified recurrence,
\begin{center}
\begin{tabular}{cccccc}
 &&&&&1 \\
 &&&&1&1 \\
 &&&1&3&1\\
 &&1&6&7&1\\
 &1&10&25&15&1\\
 1&15&65&90 &31&1\\
\end{tabular}
\end{center}
and so forth.
 
 {\bf Exercise:} Show $k$ subset $2$ is $2^{k-1}-1$ and $k$ subset $k-1$ is $k$ choose $2$.

\begin{theorem}[Ordinary Power Expansion]
For any integer $n\ge1$,
\[
  n^k = \sum_{j=1}^k {k\brace j} n^{(j)}
\]
\end{theorem}

{\bf  Proof:}
The result is trivial for $k=1$.
Rearranging $n^{(k+1)}=n^{(k)}(n-k)$ as
$n\,n^{(k)}=n^{(k+1)}+kn^{(k)}$ we can complete the induction,
\begin{eqnarray*}
n^{k}&=& n\,\sum_{j=1}^{k-1}{k-1\brace j}n^{(j)}\\
&=& \sum_{j=1}^{k-1}{k-1\brace j}(n^{(j+1)}+jn^{(j)})\\
&=& \sum_{j=2}^k {k-1\brace j-1}n^{(j)} + \sum_{j=1}^{k-1}j{k-1\brace j}n^{(j)}\\
&=& { k-1 \brace k-1}n^{(k)}+\sum_{j=2}^{k-1}{k\brace j}n^{(j)} + {k-1\brace 1}n^{(1)}\\
&=& \sum_{j=1}^k{k \brace j}n^{(j)}
\end{eqnarray*}

As a concluding note, the inverse relationship uses the Stirling numbers of the first kind,
\[
  n^{(k)} = \sum_{j=1}^k {k\brack j} (-1)^{n-k}n^j
\]
The Stirling number of the first kind is the number of
ways to arrange $k$ elements into $j$ non-empty cycles. For this
reason it is read $k$ cycle $j$.
Its recurrence is,
\[
    {k\brack j} = (k-1){k-1\brack j} + {k-1\brack j-1}
\]

{\bf Exercise:} List the 11 possible ways of creating two cycles out of a set of four elements.


%===========================================


\subsection*{The $n$-th Moment of the Geometric Distribution and Stirling Numbers}


(With Robert Chen) We point out this curious relationship:
the $n$-th moment of a geometric distribution with $p=q=1/2$
 is twice the number of ordered partitions of $n$.
Define the falling power, 
\[
      k^{(j)}=k(k-1)\ldots(k-j+1)
\]
which is related to ordinary powers by the sum,
\[
   k^n = \sum_{j=1}^n { n \brace j }k^{(j)}.
\]
where the quantities ${n\brace j}$ are the Stirling numbers of the second kind, 
 defined combinatorically as the
number of ways to partition $n$ elements into $j$ sets.
A familiar infinite series can then be written in terms of falling powers,
\begin{eqnarray*}
 \sum_{k=1}^\infty k^n t^k 
&=& \sum_{k=1}^\infty \sum_{j=1}^n {n\brace j}k^{(j)}t^k\\
&=&\sum_{j=1}^n {n\brace j} \sum_{k=1}^\infty k^{(j)}t^k \\
\end{eqnarray*}
Taking repeated derivatives of the series $\sum t^k=1/(1-t)$,
we have a closed form for the innermost sums,
\[
   \sum_{k=1}^\infty  k^{(j)}t^k = \frac{j!\,t^j}{(1-t)^{j+1}}
\]
Letting $t=1/2$, the infinite sum of $k^n t^k$ is the $n$-th moment of a geometric
distribution with $p=q=1/2$,
\[
   E(X^n)=2\sum_{j=1}^n j!\,{n\brace j}
\]
The right-hand side of this equality is the  the number of ordered partitions of $n$,
the sum of the number of $j$ partitions of $n$ times $j$-factorial, summed over $j$.

For instance, the set of two elements $\{1,2\}$ has 3 ordered partitions, $\{\{1,2\}$,
$\{1\}\{2\},\{2\}\{1\}\}$. The second moment of the geometric distribution is 6.
The set of three elements has 13 ordered partitions, 
\[
\{1,2,3\},\,\{1\}\{2,3\},\,\{2,3\}\{1\},\,\ldots,\,\{3\}\{1\}\{2\},\,\{3\}\{2\}\{1\}
\]
and the third moment is 26.



 \end{document}
