This follows from Theorem 1 by induction on n+m.

The inductive base:

F(0,1) = 1 (by defn) and F(1,0) = 1, hence F(0,1) = F(1,0) Hence Theorem 2 is true for the pairs 0 ,1 and 1, 0 so the induction starts.

The inductive step:

If Theorem 2 is true for all values of m, n up to the pairs of values, n-1 and m, n and m-1, then for these values:

F(n-1,m) = F(m, n-1) and F(n,m-1) = F(m-1,n)

Hence (adding these together):

F(n-1,m) + F(n,m-1) = F(m, n-1) + F(m-1,n)

and from Theorem 1 applied to both sides,

F(n,m) = F(m,n)

so the result is proved by induction.

Back to NumberOfCoefficients.