  Denote by $\Sigma n^m$ the sum of the $m$-th powers of the first $n$ positive
integers $1^m+2^m+\ldots +n^m$. Similarly let $\Sigma^r n^m$ be the $r$-fold
sum of the $m$-th powers of the first $n$ positive integers, defined such that
$\Sigma^0 n^{m}=n^m$, and then recursively by $\Sigma^{r+1} n^{m}=\Sigma^{r}
1^{m}+\Sigma^{r} 2^{m}+\ldots + \Sigma^{r} n^{m}$. During the early
17th-century, polynomial expressions for the sums $\Sigma^r n^m$ and their
factorisation and polynomial basis representation properties were examined by
Johann Faulhaber, who published some remarkable theorems relating to these
$r$-fold sums in his Academia Algebrae (1631).
  In this paper we consider families of polynomials related to the Fibonacci
and Lucas polynomials which naturally lend themselves to representing sums and
differences of integer powers, as well as $\Sigma^r n^m$. Using summations over
polynomial basis representations for monomials we generalise this sum for any
polynomial $q(x)\in\mathbb{Q}[x]$, encountering some interesting coefficient
families in the process. Other results include using our polynomial expressions
to state some theorems of Fermat, where in particular, we obtain an explicit
expression for the quotient in Fermat's Little Theorem.
  In the final two sections we examine these sums in the context of the three
pairs of Stirling number varieties and binomial decompositions. We also derive
an expression for $\Sigma n^m$ in terms of the Stirling numbers and Pochhammer
symbols, leading to a seemingly new relation between the Stirling numbers and
the Bernoulli numbers.
