1
$\begingroup$

While working on another problem that involved a linear system of arbitrary size $n$, I managed to empirically come up with a solution for that system. My solution is correct if and only if the following identity is true:

$$\sum_{i=1}^n(-1)^i \binom{n}{i}i^{k-1} = 0$$ $$n, k \in \mathbb{N}$$ $$2 \le k \le n$$

I've checked this empirically up to $n = 200$ using Mathematica. I'd like to be able to prove that this identity is either true or find the minimum $n$ where it fails, but I have no idea where to begin.

$\endgroup$
  • $\begingroup$ Something seems to be off with your $i$'s and $k$'s. The summation is for $k$ from $1$ to $n$, while you say $2\leq k\leq n$ and I'm not quite sure where the $i$ is supposed to come from. If the summation is supposed to be over $i$ instead of $k$ and the term $i^{k-1}$ turns out to be independent of the index of summation, it is possible to use the identity provided by mr. Raczkowski below, which was my first instinct to use as well. $\endgroup$ – HSN Jun 20 '15 at 15:56
  • 1
    $\begingroup$ @HSN Thanks, that was a typo, I've fixed it. $\endgroup$ – Kyle Jun 20 '15 at 15:58
2
$\begingroup$

Note that $\binom ni$ is a polynomial in $n$ of degree $i$. Thus, for any given polynomial $a_0+\dotsb+a_dn^d$, there is exactly one way to write it as a linear combination of binomial coefficients: $$ \sum_{i=0}^d \binom ni b_i = a_0 + a_1 n + a_2 n^2 + \dotsb + a_d n^d $$ (Consider this as a linear system in the variables $b_i$; since each $\binom ni$ has degree $i$, the system's coefficient matrix is triangular and has nonzero diagonal entries; so the system has unique solutions.)

Note that on the LHS there, we wrote $\sum_{i=0}^d$, and worked in the vector space of polynomials of degree at most $d$. But we could also write $\sum_{i=0}^{d+1}$, set $a_{d+1}=0$, and do the same in the vector space of polynomials of degree at most $d+1$. We find that there is a unique way to write blah blah blah. But the solution in the at-most-degree-$d$ world extends to a solution in the at-most-degree-$(d+1)$ world, just by taking $b_{d+1}=0$; so this must be the unique solution in the at-most-degree-$(d+1)$ world.

So: if you write a polynomial of degree $d$ as a linear combination of binomial coefficients, the coefficients (in the linear combination) of the binomial coefficients $\binom{n}{d+1},\binom{n}{d+2},\binom{n}{d+3},\dotsc$ are all zero.

Now to your problem. Fix $k\ge 2$. Let $c_i$ be the unique coefficients such that $$ \sum_{i=0}^n \binom ni c_i = n^{k-1} \qquad\text{for all $n\ge 0$.} $$ As discussed above, since the RHS has degree $k-1$, we have $c_i=0$ for all $i\ge k$. Applying binomial inversion, we get $$ c_n = \sum_{i=0}^n \binom ni (-1)^{n+i} i^{k-1} \qquad\text{for all $n\ge 0$.} $$ Since $k\ge 2$, we have $0^{k-1}=0$, so the $i=0$ term of the RHS is zero; thus the RHS is $(-1)^n$ times your sum. Since $c_n=0$ for all $n\ge k$, the desired result is proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.