1.15 (


) www In this exercise and the next, we explore how the number of independent parameters in a polynomial grows with the orderM of the polynomial and with the dimensionality D of the input space. We start by writing down the Mth order term for a polynomial in D dimensions in the form

D i1=1

D i2=1

· · ·

D iM=1 wi1i2···iMxi1xi2

· · · xiM. (1.133)

The coefficients wi1i2···iM comprise DM elements, but the number of independent parameters is significantly fewer due to the many interchange symmetries of the factor xi1xi2

· · · xiM. Begin by showing that the redundancy in the coefficients can be removed by rewriting this Mth order term in the form

D i1=1

i1 i2=1

· · ·

iM−1 iM=1

wi1i2···iMxi1xi2

· · · xiM. (1.134)

Note that the precise relationship between the w coefficients and w coefficients need not be made explicit. Use this result to show that the number of independent parameters n(D,M), which appear at order M, satisfies the following recursion relation n(D,M) = D i=1 n(i,M − 1). (1.135)
Next use proof by induction to show that the following result holds D i=1 (i +M − 2)!
(i − 1)! (M − 1)!
= (D +M − 1)!
(D − 1)!M!
(1.136)
which can be done by first proving the result for D = 1 and arbitrary M by making use of the result 0! = 1, then assuming it is correct for dimension D and verifying that it is correct for dimension D + 1. Finally, use the two previous results, together with proof by induction, to show n(D,M) = (D +M − 1)!
(D − 1)!M! . (1.137)
To do this, first show that the result is true for M = 2, and any value of D  1, by comparison with the result of Exercise 1.14. Then make use of (1.135), together with (1.136), to show that, if the result holds at orderM −1, then it will also hold at order M