More fun in 2015, Part 6

I'm going straight for the generalization.

Claim : For any positive integer $m$ , the coefficients of $a_n$ and $b_n$ for the polynomial $\displaystyle f_m (n) = \sum_{j=1}^n j^m = a_n n^{m+1} + b_n n^{m} + \ldots$ is equals to $\frac1{m+1}$ and $\frac12$ respectively.

Proof : By method of differences, it's easy to see that the leading coefficient of the polynomial $\displaystyle f_m (n) = \sum_{j=1}^n j^m$ equals to $\frac1{m+1}$ .

Consider the telescoping sum and considering the first two terms of the binomial expansion:

$\begin{aligned} \displaystyle \sum_{k=1}^n \left [ (k+1)^{m+1} - k^{m+1} \right ] & = & \displaystyle \dbinom{m+1}{1} \sum_{k=1}^n k^m + \dbinom{m+1}{2} \sum_{k=1}^n k^{m-1} + \ldots \\ \displaystyle (n+1)^{m+1} - 1 - \left ( \dbinom{m+1}{2} \sum_{k=1}^n k^{m-1} + \ldots \right ) & = & \displaystyle \dbinom{m+1}{1} \sum_{k=1}^n k^m \\ n^{m+1} + n^m \left ( \dbinom{m+1}{1} - \frac 1m \cdot \dbinom{m+1}{2} \right) + \ldots & = & \displaystyle (m+1) ( a_n n^{m+1} + b_n n^{m} + \ldots ) \end{aligned}$

Comparing the coefficients of $n^m$ :

$(m+1)b_n = (m+1) - \frac1m \cdot \frac{ m(m+1)}2 \Rightarrow b_n = \frac12 \ \ \ \ \blacksquare$

In this case, $a = a_{2015} = \frac1{2016}, b = b_{2016} = \frac12 \Rightarrow \frac ba = \boxed{1008}$ .

Note that using the same approach, we can work out the coefficients of $n^{m-1}, n^{m-2}, \ldots , n$ for the polynomial $\displaystyle f_m (n) = \sum_{j=1}^n j^m$ .

The solution I had in mind is essentially the same as Pi Han's:

Let $S_m(n)=\sum_{k=1}^{n}k^m$ . We will show by induction on $m$ that
(a) $S_m(n)$ is a polynomial of degree $m+1$ ,
(b) the leading coefficient is $\frac{1}{m+1}$ , and
(c) the second highest coefficient is $\frac{1}{2}$ .
We know these claims to be true for $S_1(n)=\frac{n(n+1)}{2}$ . Let's assume they hold for all integers $<m$ .

Now $n^{m+1}=\sum_{k=1}^{n}\left(k^{m+1}-(k-1)^{m+1}\right)$ $=(m+1)\sum_{k=1}^{n}k^m-{{m+1}\choose{2}}\sum_{k=1}^{n}k^{m-1}+...$ $=(m+1)S_m(n)-{{m+1}\choose{2}}S_{m-1}(n)+...$

We know, by induction, that the later terms are polynomials of degree $<m$ and the leading term of ${{m+1}\choose{2}}S_{m-1}(n)$ is $\frac{m+1}{2}n^m$ . Thus $S_m(n)=\frac{1}{m+1}n^{m+1}+\frac{1}{2}n^m+...$ , proving our three claims.

Now $\frac{b}{a}=\frac{m+1}{2}=\boxed{1008}$

The question becomes easy if one knows that $\displaystyle \sum_{k=1}^n k^m$ is a polynomial in $n(n+1)$ whenever $m$ is odd .

Also, since we are informed that it is of degree $m+1$ in $n$ , we have that $\displaystyle \sum_{k=1}^n k^{2015}$ is a polynomial of degree 1008 in $n(n+1)$ .

Proof :

Let $\displaystyle \sum_{k=1}^n k^{2015} = c_{1008}n^{1008}(n+1)^{1008}+c_{1007}n^{1007}(n+1)^{1007}+\ldots$ , where $\lbrace c_i \rbrace$ are constants. Expanding $c_{1007}n^{1007}(n+1)^{1007}$ , we only obtain powers of $n$ of at most 2014, which will contribute to neither $a$ nor $b$ . This is obviously true for $c_{1006}n^{1006}(n+1)^{1006}, c_{1005}n^{1005}(n+1)^{1005},$ et cetera. Hence, we only need to observe the expansion of $c_{1008}n^{1008}(n+1)^{1008}$ .

Using the binomial theorem,

$c_{1008}n^{1008}(n+1)^{1008} = c_{1008}n^{1008}\left[ \sum_{i=1}^{1008} \binom{1008}{i}n^i \right]$

The relevant terms are then

$c_{1008}n^{1008} \left[ \binom{1008}{1008}n^{1008} \right] = c_{1008}n^{2016} = an^{2016}$

and

$c_{1008}n^{1008} \left[ \binom{1008}{1007}n^{1007} \right] = 1008c_{1008}n^{2015} = bn^{2015}$

By comparing coefficients, we have $a = c_{1008}$ and $b = 1008c_{1008}$ . As a result, we have $\displaystyle \frac{b}{a} = \frac{1008c_{1008}}{c_{1008}} = \boxed{1008}$ . (This extends easily to all $m$ odd.)