The Padovan sequence \((P_n)_{n\geq 0}\) is defined by the third-order linear recurrence \(P_n=P_{n-2}+P_{n-3}\) for \(n\geq 3\), with initial terms \(P_0=1\) and \(P_1=P_2=0\). We derive closed forms for the weighted finite sums \(\sum\limits_{i=1}^{n} i^mP_i\) for all integers \(m\geq 0\) and \(n\geq 1\). The construction introduces an alternating integer sequence \((\mathcal{A}^{(m)})_{m\geq 0}\) and a family of coefficient polynomials \(\mathcal{C}^{(m)}(x)\) whose shifted evaluations determine the coefficients of \(P_n\), \(P_{n+1}\), and \(P_{n+2}\). The resulting formula unifies the cases \(m=0,1,2,\ldots\) and provides an effective recurrence, together with an exponential generating function, for the coefficients. The same polynomial family also gives explicit weighted-sum identities for arbitrary sequences satisfying the Padovan recurrence, including the Perrin and Van der Laan sequences.
The evaluation of weighted sums involving linear recurrence sequences is a classical topic in enumerative and algebraic number theory. A representative problem was posed by Brother Alfred Brousseau [3] in 1963, who asked for a closed form for \[\sum\limits_{i=1}^{n} i^3F_i, \label{eq:brousseau-problem} \tag{1}\] where \(F_i\) denotes the \(i\)th Fibonacci number (OEIS A000045 [16]). Erbacher and Fuchs [7] showed that \[\sum\limits_{i=1}^{n} i^3F_i =\bigl(n^3+6n-12\bigr)F_{n+2} +\bigl(-3n^2+9n-19\bigr)F_{n+3}+50 . \label{eq:erbacher-fuchs} \tag{2}\]
Subsequent work by Brousseau [4], Ledin [11], and Zeitlin [18] placed such identities in the broader problem of evaluating \(\sum\limits_{i=1}^{n} i^mF_i\) for arbitrary positive integers \(m\). Ledin’s form of (2) is \[\sum\limits_{i=1}^{n} i^3F_i =\bigl(n^3-6n^2+24n-50\bigr)F_{n+1} +\bigl(n^3-3n^2+15n-31\bigr)F_n+50 . \label{eq:ledin-form} \tag{3}\]
The coefficient polynomials in these identities have been studied through Stirling numbers, Eulerian numbers, Bernoulli numbers, and binomial coefficients; see, for example, [1, 6, 9, 10, 14, 15].
A useful feature of (3) is that the two coefficient polynomials are shifted values of a single polynomial. Specifically, as observed in [13], \[\sum\limits_{i=1}^{n} i^3F_i =\bigl(\mathcal{P}^{(3)}(n)\bigr)F_{n+1} +\bigl(\mathcal{P}^{(3)}(n+1)\bigr)F_n-\mathcal{P}^{(3)}(0), \label{eq:fibonacci-shifted} \tag{4}\] where \[\mathcal{P}^{(3)}(n)=n^3-6n^2+24n-50.\]
This structural property motivates the corresponding question for the Padovan recurrence \[P_i=P_{i-2}+P_{i-3}\qquad (i\geq 3),\] with \(P_0=1\) and \(P_1=P_2=0\) (OEIS A000931 [16]). The cubic Padovan identity obtained in [5] is \[\begin{aligned} \sum\limits_{i=1}^{n} i^3P_i ={}&\bigl(n^3-6n^2+48n-170\bigr)P_n +\bigl(n^3-12n^2+84n-298\bigr)P_{n+1} \\ &+\bigl(n^3-9n^2+63n-225\bigr)P_{n+2}+170 . \end{aligned} \label{eq:padovan-cubic} \tag{5}\]
It can be written in the shifted form \[\sum\limits_{i=1}^{n} i^3P_i =\bigl(\mathcal{C}^{(3)}(n)\bigr)P_n +\bigl(\mathcal{C}^{(3)}(n-2)\bigr)P_{n+1} +\bigl(\mathcal{C}^{(3)}(n-1)\bigr)P_{n+2} -\mathcal{C}^{(3)}(0), \label{eq:padovan-cubic-shifted} \tag{6}\] where \[\mathcal{C}^{(3)}(n)=n^3-6n^2+48n-170.\]
The main contribution of this paper is the identification of the polynomial family \(\mathcal{C}^{(m)}(x)\) that makes (6) valid for every \(m\geq 0\). More precisely, we prove \[\sum\limits_{i=1}^{n} i^mP_i =\bigl(\mathcal{C}^{(m)}(n)\bigr)P_n +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)P_{n+1} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)P_{n+2} -\mathcal{C}^{(m)}(0), \label{eq:main-preview}\] where \(\mathcal{C}^{(m)}(x)\) is a polynomial of degree \(m\). We give an explicit construction of these polynomials from a single alternating integer sequence. We then use the same coefficient polynomials to obtain formulas for arbitrary initial values in the Padovan recurrence.
The following identity is the recursive starting point.
Theorem 1.1([12, Corollary 2.6]).For all integers \(n,m\geq 1\), \[\begin{aligned} \sum\limits_{i=1}^{n} i^mP'_i={}&(n+1)^mP'_n+(n-1)^mP'_{n+1}+n^mP'_{n+2} -P'_0-(-1)^mP'_1 \\ &-\sum\limits_{j=1}^{m}\bigl(1-(-2)^j\bigr)\binom{m}{j} \left(\sum\limits_{i=1}^{n} i^{m-j}P'_i\right), \end{aligned}\] where \((P'_n)_{n\geq 0}\) is any sequence satisfying \(P'_n=P'_{n-2}+P'_{n-3}\) for \(n\geq 3\), with initial terms \(P'_0\), \(P'_1\), and \(P'_2\) not all zero.
Two important instances are the Perrin sequence \((Q_n)_{n\geq 0}\), defined by \(Q_0=3\), \(Q_1=0\), and \(Q_2=2\), and the Van der Laan sequence \((V_n)_{n\geq 0}\), defined by \(V_0=1\), \(V_1=0\), and \(V_2=1\). Table 1 lists the first terms used throughout the paper. We adopt the conventions \(\binom{0}{0}=1\) and \(0^0=1\).
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(P_n\) | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 | 12 |
| \(Q_n\) | 3 | 0 | 2 | 3 | 2 | 5 | 5 | 7 | 10 | 12 | 17 | 22 | 29 | 39 | 51 | 68 |
| \(V_n\) | 1 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 | 12 | 16 | 21 | 28 |
We first determine the weighted sums \[\sum\limits_{i=1}^{n} i^mP_i,\] for the Padovan sequence. The case \(m=0\) follows from the standard identity \[\sum\limits_{i=1}^{n} P_i=P_n+P_{n+1}+P_{n+2}-1. \label{eq:padovan-sum} \tag{8}\]
Theorem 2.1. For all integers \(n,m\geq 1\), \[\begin{aligned} \sum\limits_{i=1}^{n} i^mP_i =&n^mP_{n+2}+(n-1)^mP_{n+1}+(n+1)^mP_n-1\notag\\ &-\sum\limits_{j=1}^{m}\bigl(1-(-2)^j\bigr)\binom{m}{j} \left(\sum\limits_{i=1}^{n} i^{m-j}P_i\right). \label{eq:padovan-recursive-sum} \end{aligned} \tag{9}\]
Proof. Set \((P'_0,P'_1,P'_2)=(1,0,0)\) in Theorem 1.1. ◻
For \(m=1\), (9) gives \[\sum\limits_{i=1}^{n} iP_i=nP_{n+2}+(n-1)P_{n+1}+(n+1)P_n-1 -3\sum\limits_{i=1}^{n}P_i.\]
Substituting (8) yields \[\sum\limits_{i=1}^{n} iP_i=(n-2)P_n+(n-4)P_{n+1}+(n-3)P_{n+2}+2. \label{eq:m1-padovan} \tag{10}\]
Similarly, \[\sum\limits_{i=1}^{n} i^2P_i =\bigl(n^2-4n+16\bigr)P_n +\bigl(n^2-8n+28\bigr)P_{n+1} +\bigl(n^2-6n+21\bigr)P_{n+2}-16, \label{eq:m2-padovan} \tag{11}\] and \[\begin{aligned} \sum\limits_{i=1}^{n} i^3P_i ={}&\bigl(n^3-6n^2+48n-170\bigr)P_n +\bigl(n^3-12n^2+84n-298\bigr)P_{n+1} \\ &+\bigl(n^3-9n^2+63n-225\bigr)P_{n+2}+170. \end{aligned} \label{eq:m3-padovan} \tag{12}\]
The coefficients in (10)–(12) are shifted values of one polynomial for each fixed exponent: \[\begin{aligned} \sum\limits_{i=1}^{n} iP_i &=(n-2)P_n+((n-2)-2)P_{n+1}+((n-2)-1)P_{n+2}+2,\\ \sum\limits_{i=1}^{n} i^2P_i &=\bigl(n^2-4n+16\bigr)P_n+\bigl((n-2)^2-4(n-2)+16\bigr)P_{n+1}\\ &\qquad +\bigl((n-1)^2-4(n-1)+16\bigr)P_{n+2}-16,\\ \sum\limits_{i=1}^{n} i^3P_i &=\bigl(n^3-6n^2+48n-170\bigr)P_n\\ &\qquad +\bigl((n-2)^3-6(n-2)^2+48(n-2)-170\bigr)P_{n+1}\\ &\qquad +\bigl((n-1)^3-6(n-1)^2+48(n-1)-170\bigr)P_{n+2}+170. \end{aligned}\]
This shift pattern is the central algebraic feature captured by the next definitions.
Definition 2.2. Define the integer sequence \((\mathcal{A}^{(m)})_{m\geq 0}\) by \[\mathcal{A}^{(m)}= \begin{cases} 1, & m=0,\\[2mm] 1-\displaystyle\sum\limits_{j=1}^{m}\bigl(1-(-2)^j\bigr)\binom{m}{j}\mathcal{A}^{(m-j)}, & m>0. \end{cases} \label{eq:A-recurrence} \tag{13}\]
The first terms are \[1,\ -2,\ 16,\ -170,\ 2416,\ -42962,\ 916696,\ldots .\]
The exponential generating function of \((\mathcal{A}^{(m)})_{m\geq 0}\) is \[\sum\limits_{m\geq 0}\mathcal{A}^{(m)}\frac{x^m}{m!}=\frac{1}{1+e^{-x}-e^{-3x}}.\]
Consequently, \(((-1)^m\mathcal{A}^{(m)})_{m\geq 0}\) is OEIS A355408 [16], whose exponential generating function is \(1/(1+e^x-e^{3x})\).
The coefficients displayed above satisfy \[\begin{aligned} n-2&=1\binom{1}{0}n-2\binom{1}{1},\\ n^2-4n+16&=1\binom{2}{0}n^2-2\binom{2}{1}n+16\binom{2}{2},\\ n^3-6n^2+48n-170&=1\binom{3}{0}n^3-2\binom{3}{1}n^2+16\binom{3}{2}n-170\binom{3}{3}. \end{aligned}\]
Thus the coefficient of \(n^{m-j}\) is governed by \(\binom{m}{j}\mathcal{A}^{(j)}\).
Definition 2.3. For integers \(m\geq 0\) and \(x\), define the coefficient polynomial \[\mathcal{C}^{(m)}(x)=\sum\limits_{j=0}^{m}\mathcal{A}^{(j)}\binom{m}{j}x^{m-j}. \label{eq:C-polynomial} \tag{14}\]
Then \(\mathcal{C}^{(m)}(0)=\mathcal{A}^{(m)}\) and \(\mathcal{C}^{(0)}(x)=1\). Tables 2 and 3 give representative values.
| \(m\) | \(\mathcal{A}^{(m)}\) | \(\mathcal{C}^{(m)}(n)\) |
|---|---|---|
| 0 | 1 | \(1\) |
| 1 | \(-2\) | \(n-2\) |
| 2 | 16 | \(n^2-4n+16\) |
| 3 | \(-170\) | \(n^3-6n^2+48n-170\) |
| 4 | 2416 | \(n^4-8n^3+96n^2-680n+2416\) |
| 5 | \(-42962\) | \(n^5-10n^4+160n^3-1700n^2+12080n-42962\) |
| 6 | 916696 | \(n^6-12n^5+240n^4-3400n^3+36240n^2-257772n+916696\) |
| \(n\) | \(-1\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\mathcal{C}^{(0)}(n)\) | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| \(\mathcal{C}^{(1)}(n)\) | \(-3\) | \(-2\) | \(-1\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| \(\mathcal{C}^{(2)}(n)\) | 21 | 16 | 13 | 12 | 13 | 16 | 21 | 28 | 37 | 48 | 61 |
| \(\mathcal{C}^{(3)}(n)\) | \(-225\) | \(-170\) | \(-127\) | \(-90\) | \(-53\) | \(-10\) | 45 | 118 | 215 | 342 | 505 |
| \(\mathcal{C}^{(4)}(n)\) | 3201 | 2416 | 1825 | 1392 | 1105 | 976 | 1041 | 1360 | 2017 | 3120 | 4801 |
Theorem 2.4. For all integers \(m\geq 0\) and \(n\geq 1\), \[\begin{aligned} \label{eq:theorem5-expanded} \sum\limits_{i=1}^{n} i^mP_i ={}&\left(\sum\limits_{j=0}^{m}\mathcal{A}^{(j)}\binom{m}{j}n^{m-j}\right)P_n +\left(\sum\limits_{j=0}^{m}\mathcal{A}^{(j)}\binom{m}{j}(n-2)^{m-j}\right)P_{n+1} \notag\\ &+\left(\sum\limits_{j=0}^{m}\mathcal{A}^{(j)}\binom{m}{j}(n-1)^{m-j}\right)P_{n+2} -\mathcal{A}^{(m)}. \end{aligned} \tag{15}\]
Equivalently, (7) holds.
Proof. We use induction on \(m\). The case \(m=0\) is (8). Let \(m\geq 1\) and assume the assertion for all non-negative integers less than \(m\). By (9), \[\begin{aligned} \label{eq:proof-step1} \sum\limits_{i=1}^{n} i^mP_i={}&(n+1)^mP_n+(n-1)^mP_{n+1}+n^mP_{n+2}-1 \notag\\ &-\sum\limits_{j=1}^{m}\bigl(1-(-2)^j\bigr)\binom{m}{j} \left(\sum\limits_{i=1}^{n} i^{m-j}P_i\right). \end{aligned} \tag{16}\]
For \(j=1,2,\ldots,m\), the induction hypothesis gives \[\sum\limits_{i=1}^{n} i^{m-j}P_i =\bigl(\mathcal{C}^{(m-j)}(n)\bigr)P_n +\bigl(\mathcal{C}^{(m-j)}(n-2)\bigr)P_{n+1} +\bigl(\mathcal{C}^{(m-j)}(n-1)\bigr)P_{n+2} -\mathcal{C}^{(m-j)}(0). \label{eq:induction-hypothesis} \tag{17}\]
Define, for an integer \(x\), \[X(x)=\sum\limits_{j=1}^{m}\bigl(1-(-2)^j\bigr)\binom{m}{j}\mathcal{C}^{(m-j)}(x). \label{eq:X-def} \tag{18}\]
Substitution of (17) into (16) gives \[\begin{aligned} \label{eq:X-substitution} \sum\limits_{i=1}^{n} i^mP_i={}&\bigl((n+1)^m-X(n)\bigr)P_n +\bigl((n-1)^m-X(n-2)\bigr)P_{n+1} \notag\\ &+\bigl(n^m-X(n-1)\bigr)P_{n+2}-\bigl(1-X(0)\bigr). \end{aligned} \tag{19}\]
Using (14) and (18), \[X(x)=\sum\limits_{j=1}^{m}\sum\limits_{r=0}^{m-j} \bigl(1-(-2)^j\bigr)\mathcal{A}^{(r)}\binom{m}{j}\binom{m-j}{r}x^{m-j-r}.\]
Set \(r\) equal to \(r-j\) in the inner index after collecting the coefficient of \(x^{m-r}\). Then the identity \[\binom{m}{j}\binom{m-j}{r-j}=\binom{m}{r}\binom{r}{j},\] from [2, Identity 134] yields \[X(x)=\sum\limits_{r=1}^{m}\binom{m}{r} \left(\sum\limits_{j=1}^{r}\bigl(1-(-2)^j\bigr)\binom{r}{j}\mathcal{A}^{(r-j)}\right)x^{m-r}. \label{eq:X-rearranged} \tag{20}\]
By (13), \[\sum\limits_{j=1}^{r}\bigl(1-(-2)^j\bigr)\binom{r}{j}\mathcal{A}^{(r-j)}=1-\mathcal{A}^{(r)} \qquad (r>0).\]
Hence \[X(x)=\sum\limits_{r=1}^{m}\binom{m}{r}\bigl(1-\mathcal{A}^{(r)}\bigr)x^{m-r}.\]
Since \(\mathcal{A}^{(0)}=1\), the summation may start at \(r=0\), and therefore \[\begin{aligned} X(x)&=\sum\limits_{r=0}^{m}\binom{m}{r}\bigl(1-\mathcal{A}^{(r)}\bigr)x^{m-r} \\ &=\sum\limits_{r=0}^{m}\binom{m}{r}x^{m-r} -\sum\limits_{r=0}^{m}\binom{m}{r}\mathcal{A}^{(r)}x^{m-r} \\ &=(x+1)^m-\mathcal{C}^{(m)}(x). \end{aligned}\]
Consequently, \[\begin{aligned} \label{eq:X-values} X(n)&=(n+1)^m-\mathcal{C}^{(m)}(n),\notag\\ X(n-1)&=n^m-\mathcal{C}^{(m)}(n-1),\notag\\ X(n-2)&=(n-1)^m-\mathcal{C}^{(m)}(n-2),\notag\\ X(0)&=1-\mathcal{C}^{(m)}(0). \end{aligned} \tag{21}\]
Substituting (21) into (19) proves (15). ◻
| \(m=1,\ n=3\) | \(\displaystyle \sum\limits_i=1^3 iP_i=1(0)+2(0)+3(1)=3\) |
| [1mm] | \(\displaystyle (\mathcal{C}^(1)(3))P_3+(\mathcal{C}^(1)(1))P_4+(\mathcal{C}^(1)(2))P_5- \mathcal{C}^(1)(0)=1(1)+(-1)(0)+0(1)-(-2)=3\) |
| \(m=2,\ n=5\) | \(\displaystyle \sum\limits_i=1^5 i^2P_i=1(0)+4(0)+9(1)+16(0)+25(1)=34\) |
| [1mm] | \(\displaystyle (\mathcal{C}^(2)(5))P_5+(\mathcal{C}^(2)(3))P_6+(\mathcal{C}^(2)(4))P_7- \mathcal{C}^(2)(0) =21(1)+13(1)+16(1)-16=34\) |
| \(m=3,\ n=7\) | \(\displaystyle \sum\limits_i=1^7 i^3P_i=1(0)+8(0)+27(1)+64(0)+125(1)+216(1)+343(1)=711\) |
| [1mm] | \(\displaystyle (\mathcal{C}^(3)(7))P_7+(\mathcal{C}^(3)(5))P_8+(\mathcal{C}^(3)(6))P_9- \mathcal{C}^(3)(0) =215(1)+45(2)+118(2)-(-170)=711\) |
The evaluations in Table 4 illustrate the role of the shifted arguments \(n\), \(n-2\), and \(n-1\). Once \(\mathcal{C}^{(m)}\) is known, the three coefficients in the Padovan identity require no separate computation. The boundary term is also determined by the same polynomial, since \(\mathcal{C}^{(m)}(0)=\mathcal{A}^{(m)}\).
Theorem 2.5. For all integers \(m,r\geq 0\) and \(n\geq 1\), \[\begin{aligned} \label{eq:shifted-padovan} \sum\limits_{i=1}^{n} i^mP_{r+i} ={}&\bigl(\mathcal{C}^{(m)}(n)\bigr)P_{n+r} +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)P_{n+r+1} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)P_{n+r+2} \notag\\ &-\bigl(\mathcal{C}^{(m)}(0)\bigr)P_r -\bigl(\mathcal{C}^{(m)}(-2)\bigr)P_{r+1} -\bigl(\mathcal{C}^{(m)}(-1)\bigr)P_{r+2}. \end{aligned} \tag{22}\]
Proof. The case \(r=0\) follows from Theorem 3.1. Let \(r\geq 1\). By the binomial theorem, \[\begin{aligned} \sum\limits_{i=1}^{n} i^mP_{i+r} &=\sum\limits_{i=r+1}^{n+r} (i-r)^mP_i =\sum\limits_{i=r+1}^{n+r}\sum\limits_{j=0}^{m}\binom{m}{j}i^{m-j}(-r)^jP_i \\ &=\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j \sum\limits_{i=r+1}^{n+r}i^{m-j}P_i. \end{aligned}\]
Thus \[\sum\limits_{i=1}^{n} i^mP_{i+r} =\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j \left(\sum\limits_{i=1}^{n+r}i^{m-j}P_i-\sum\limits_{i=1}^{r}i^{m-j}P_i\right). \label{eq:shift-proof-start} \tag{23}\]
Applying Theorem 3.1 with \(n\) replaced by \(n+r\) and \(m\) replaced by \(m-j\) gives \[\begin{aligned} \label{eq:sum-n-plus-r} \sum\limits_{i=1}^{n+r} i^{m-j}P_i ={}&\bigl(\mathcal{C}^{(m-j)}(n+r)\bigr)P_{n+r} +\bigl(\mathcal{C}^{(m-j)}(n+r-2)\bigr)P_{n+r+1} \notag\\ &+\bigl(\mathcal{C}^{(m-j)}(n+r-1)\bigr)P_{n+r+2} -\mathcal{C}^{(m-j)}(0). \end{aligned} \tag{24}\]
Similarly, \[\begin{aligned} \label{eq:sum-r} \sum\limits_{i=1}^{r} i^{m-j}P_i ={}&\bigl(\mathcal{C}^{(m-j)}(r)\bigr)P_r +\bigl(\mathcal{C}^{(m-j)}(r-2)\bigr)P_{r+1} \notag\\ &+\bigl(\mathcal{C}^{(m-j)}(r-1)\bigr)P_{r+2} -\mathcal{C}^{(m-j)}(0). \end{aligned} \tag{25}\]
Substituting (24) and (25) into (23) yields \[\begin{aligned} \label{eq:shift-proof-expanded} \sum\limits_{i=1}^{n} i^mP_{i+r} ={}&\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j\mathcal{C}^{(m-j)}(n+r)P_{n+r} \notag\\ &+\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j\mathcal{C}^{(m-j)}(n+r-2)P_{n+r+1} \notag\\ &+\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j\mathcal{C}^{(m-j)}(n+r-1)P_{n+r+2} \notag\\ &-\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j\mathcal{C}^{(m-j)}(r)P_r \notag\\ &-\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j\mathcal{C}^{(m-j)}(r-2)P_{r+1} \notag\\ &-\sum\limits_{j=0}^{m}\binom{m}{j}(-r)^j\mathcal{C}^{(m-j)}(r-1)P_{r+2}. \end{aligned} \tag{26}\]
For an integer \(x\), put \[X^*(x)=\sum\limits_{j=0}^{m}(-r)^j\binom{m}{j}\mathcal{C}^{(m-j)}(x).\]
Then (26) becomes \[\begin{aligned} \label{eq:Xstar-form} \sum\limits_{i=1}^{n} i^mP_{i+r} ={}&\bigl(X^*(n+r)\bigr)P_{n+r} +\bigl(X^*(n+r-2)\bigr)P_{n+r+1} +\bigl(X^*(n+r-1)\bigr)P_{n+r+2} \notag\\ &-\bigl(X^*(r)\bigr)P_r -\bigl(X^*(r-2)\bigr)P_{r+1} -\bigl(X^*(r-1)\bigr)P_{r+2}. \end{aligned} \tag{27}\]
Using (14), \[X^*(x)=\sum\limits_{j=0}^{m}\sum\limits_{k=0}^{m-j} (-r)^j\mathcal{A}^{(k)}\binom{m}{j}\binom{m-j}{k}x^{m-j-k}.\]
After changing the order of summation and applying Gould’s identity [8, Identity 3.118, p. 36], one obtains \[X^*(x)=\sum\limits_{k=0}^{m}\mathcal{A}^{(k)}\binom{m}{k}(x-r)^{m-k} =\mathcal{C}^{(m)}(x-r).\]
Therefore,
\[\begin{aligned} \label{eq:Xstar-values} X^*(n+r)&=\mathcal{C}^{(m)}(n),\notag\notag\\ X^*(n+r-2)&=\mathcal{C}^{(m)}(n-2),\notag\\ X^*(n+r-1)&=\mathcal{C}^{(m)}(n-1),\notag\\ X^*(r)&=\mathcal{C}^{(m)}(0),\notag\\ X^*(r-2)&=\mathcal{C}^{(m)}(-2),\notag\\ X^*(r-1)&=\mathcal{C}^{(m)}(-1). \end{aligned} \tag{28}\]
Substitution into (27) proves (22). ◻
Let \((P'_n)_{n\geq 0}\) be any sequence satisfying the Padovan recurrence \(P'_n=P'_{n-2}+P'_{n-3}\) for \(n\geq 3\). The sequence \((P'_n)\) is related to the basic Padovan sequence by [17] \[P'_i=P'_0P_i+P'_2P_{i+1}+P'_1P_{i+2}\qquad (i\geq 0). \label{eq:generalized-relation} \tag{29}\]
This representation shows that arbitrary initial values affect only the boundary terms in the weighted-sum formula, while the coefficient polynomials remain unchanged.
Theorem 3.1. For all integers \(m\geq 0\) and \(n\geq 1\), \[\begin{aligned} \label{eq:generalized-sum} \sum\limits_{i=1}^{n} i^mP'_i ={}&\bigl(\mathcal{C}^{(m)}(n)\bigr)P'_n +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)P'_{n+1} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)P'_{n+2} \notag\\ &-\bigl(\mathcal{C}^{(m)}(0)\bigr)P'_0 -\bigl(\mathcal{C}^{(m)}(-2)\bigr)P'_1 -\bigl(\mathcal{C}^{(m)}(-1)\bigr)P'_2. \end{aligned} \tag{30}\]
Proof. Multiplying (29) by \(i^m\) and summing over \(1\leq i\leq n\) gives \[\sum\limits_{i=1}^{n} i^mP'_i =P'_0\sum\limits_{i=1}^{n} i^mP_i +P'_2\sum\limits_{i=1}^{n} i^mP_{i+1} +P'_1\sum\limits_{i=1}^{n} i^mP_{i+2}. \label{eq:generalized-proof-start} \tag{31}\]
By Theorem 2.5, \[\sum\limits_{i=1}^{n} i^mP_i =\bigl(\mathcal{C}^{(m)}(n)\bigr)P_n +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)P_{n+1} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)P_{n+2} -\mathcal{C}^{(m)}(0), \label{eq:r0-case} \tag{32}\] \[\sum\limits_{i=1}^{n} i^mP_{i+1} =\bigl(\mathcal{C}^{(m)}(n)\bigr)P_{n+1} +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)P_{n+2} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)P_{n+3} -\mathcal{C}^{(m)}(-1), \label{eq:r1-case} \tag{33}\] and \[\sum\limits_{i=1}^{n} i^mP_{i+2} =\bigl(\mathcal{C}^{(m)}(n)\bigr)P_{n+2} +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)P_{n+3} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)P_{n+4} -\mathcal{C}^{(m)}(-2). \label{eq:r2-case} \tag{34}\]
Substituting (32)–(34) into (31) and applying (29) to the indices \(n\), \(n+1\), and \(n+2\) gives (30). ◻
Corollary 3.2. For all integers \(m\geq 0\) and \(n\geq 1\), \[\begin{aligned} \label{eq:perrin-sum} \sum\limits_{i=1}^{n} i^mQ_i ={}&\bigl(\mathcal{C}^{(m)}(n)\bigr)Q_n +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)Q_{n+1} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)Q_{n+2}\notag\\& -3\mathcal{C}^{(m)}(0)-2\mathcal{C}^{(m)}(-1), \end{aligned} \tag{35}\] and \[\begin{aligned} \label{eq:vanderlaan-sum} \sum\limits_{i=1}^{n} i^mV_i ={}&\bigl(\mathcal{C}^{(m)}(n)\bigr)V_n +\bigl(\mathcal{C}^{(m)}(n-2)\bigr)V_{n+1} +\bigl(\mathcal{C}^{(m)}(n-1)\bigr)V_{n+2} -\mathcal{C}^{(m)}(0)-\mathcal{C}^{(m)}(-1). \end{aligned} \tag{36}\]
| \(m=1,\ n=3\) | \(\displaystyle \sum\limits_i=1^3 iQ_i=1(0)+2(2)+3(3)=13\) |
| [-1mm] | \(\displaystyle (\mathcal{C}^(1)(3))Q_3+(\mathcal{C}^(1)(1))Q_4+(\mathcal{C}^(1)(2))Q_5 -3\mathcal{C}^(1)(0)-2\mathcal{C}^(1)(-1) =1(3)+(-1)(2)+0(5)-3(-2)-2(-3)=13\) |
| [1mm] | \(\displaystyle \sum\limits_i=1^3 iV_i=1(0)+2(1)+3(1)=5\) |
| [-1mm] | \(\displaystyle (\mathcal{C}^(1)(3))V_3+(\mathcal{C}^(1)(1))V_4+(\mathcal{C}^(1)(2))V_5 -\mathcal{C}^(1)(0)-\mathcal{C}^(1)(-1) =1(1)+(-1)(1)+0(2)-(-2)-(-3)=5\) |
| \(m=2,\ n=5\) | \(\displaystyle \sum\limits_i=1^5 i^2Q_i=1(0)+4(2)+9(3)+16(2)+25(5)=192\) |
| [-1mm] | \(\displaystyle (\mathcal{C}^(2)(5))Q_5+(\mathcal{C}^(2)(3))Q_6+(\mathcal{C}^(2)(4))Q_7 -3\mathcal{C}^(2)(0)-2\mathcal{C}^(2)(-1) =21(5)+13(5)+16(7)-3(16)-2(21)=192\) |
| [1mm] | \(\displaystyle \sum\limits_i=1^5 i^2V_i=1(0)+4(1)+9(1)+16(1)+25(2)=79\) |
| [-1mm] | \(\displaystyle (\mathcal{C}^(2)(5))V_5+(\mathcal{C}^(2)(3))V_6+(\mathcal{C}^(2)(4))V_7 -\mathcal{C}^(2)(0)-\mathcal{C}^(2)(-1) =21(2)+13(2)+16(3)-16-21=79\) |
| \(m=3,\ n=7\) | \(\displaystyle \sum\limits_i=1^7 i^3Q_i=1(0)+8(2)+27(3)+64(2)+125(5)+216(5)+343(7)=4331\) |
| [-1mm] | \(\displaystyle (\mathcal{C}^(3)(7))Q_7+(\mathcal{C}^(3)(5))Q_8+(\mathcal{C}^(3)(6))Q_9 -3\mathcal{C}^(3)(0)-2\mathcal{C}^(3)(-1)=215(7)+45(10)+118(12)-3(-170)-2(-225)=4331\) |
| [1mm] | \(\displaystyle \sum\limits_i=1^7 i^3V_i=1(0)+8(1)+27(1)+64(1)+125(2)+216(2)+343(3)=1810\) |
| [-1mm] | \(\displaystyle (\mathcal{C}^(3)(7))V_7+(\mathcal{C}^(3)(5))V_8+(\mathcal{C}^(3)(6))V_9 -\mathcal{C}^(3)(0)-\mathcal{C}^(3)(-1) =215(3)+45(4)+118(5)-(-170)-(-225)=1810\) |
The second identity also follows from Theorem 2.5 with \(r=3\), since \(V_n=P_{n+3}\) for all \(n\geq 0\). Table 5 gives numerical evaluations for the Perrin and Van der Laan cases. They show that the same polynomial coefficients govern all three sequences; only the constant terms reflect the initial values.
Example 3.3. Setting \(m=3\) in (35) gives \[\sum\limits_{i=1}^{n} i^3Q_i =\bigl(\mathcal{C}^{(3)}(n)\bigr)Q_n +\bigl(\mathcal{C}^{(3)}(n-2)\bigr)Q_{n+1} +\bigl(\mathcal{C}^{(3)}(n-1)\bigr)Q_{n+2} -3\mathcal{C}^{(3)}(0)-2\mathcal{C}^{(3)}(-1),\] where \[\mathcal{C}^{(3)}(n)=n^3-6n^2+48n-170.\]
Thus \[\begin{aligned} \sum\limits_{i=1}^{n} i^3Q_i ={}&\bigl(n^3-6n^2+48n-170\bigr)Q_n +\bigl(n^3-12n^2+84n-298\bigr)Q_{n+1} \\ &+\bigl(n^3-9n^2+63n-225\bigr)Q_{n+2}+960. \end{aligned} \label{eq:perrin-cubic} \tag{37}\]
Likewise, setting \(m=3\) in (36) yields \[\begin{aligned} \sum\limits_{i=1}^{n} i^3V_i ={}&\bigl(n^3-6n^2+48n-170\bigr)V_n +\bigl(n^3-12n^2+84n-298\bigr)V_{n+1} \\ &+\bigl(n^3-9n^2+63n-225\bigr)V_{n+2}+395. \end{aligned} \label{eq:vanderlaan-cubic} \tag{38}\]
These are the cubic identities stated in [12, Example 2.8].
The paper establishes closed polynomial expressions for Brousseau sums associated with the Padovan recurrence. The alternating sequence \((\mathcal{A}^{(m)})_{m\geq 0}\) determines the coefficient polynomial \(\mathcal{C}^{(m)}(x)\) through a binomial transform, and the shifted values \(\mathcal{C}^{(m)}(n)\), \(\mathcal{C}^{(m)}(n-2)\), and \(\mathcal{C}^{(m)}(n-1)\) give the complete coefficients of \(P_n\), \(P_{n+1}\), and \(P_{n+2}\) in \(\sum\limits_{i=1}^{n}i^mP_i\). This provides a uniform formula for every non-negative exponent \(m\) and clarifies why the low-degree cases exhibit parallel polynomial coefficients.
The same coefficient polynomials determine the corresponding sums for every sequence with the Padovan recurrence and arbitrary initial values. In this form, the dependence on the initial data is confined to three boundary terms, while the polynomial part of the identity is universal. The Perrin and Van der Laan formulas therefore follow from the same algebraic structure rather than from separate calculations. These identities supply exact finite-sum formulas for third-order recurrence sequences and give a compact method for computing higher-power weighted sums.
No potential conflict of interest was reported by the author.