Addition Chain Methods for the Evaluation of Specific Polynomials

Addition chains are considered for specific polynomials. It is shown that for a wide class of polynomials the evaluation of their first n terms requires at least $n + O(n^{2/3} )$ additions. Included in this class are the first n squares, the first n cubes, $ \cdots $, the first nkth powers. The results are established by making contact with results in combinatorics.