0
$\begingroup$

I am solving this problem:

What are the coefficients of particular powers of $x$ in polynomial $x*(x-1)*(x-2)*...*(x-k+1)$?

I know, how to start, how to get a recurrence relation, but I do not know how to get an explicit formula using just $n$ (means power) and $k$ (means $k$-th falling power).

$\endgroup$
  • $\begingroup$ This is a question in combinatorics. The algebraic combinatorics topic is different; read its definition. I know this is confusing, because the solution requires a lot of algebra in the "work with equations" sense, but not in the sense that modern math uses the word "algebra." $\endgroup$ – Mark Fischler Aug 20 at 15:59
1
$\begingroup$

The answer, valid for $k \geq 0$, will be

$$ x^{\underline{k}} = \sum_n\left[\matrix{k\\n}\right](-1)^{k-n}x^n $$

The easiest proof I find starts from the following lemmas about rising powers, both proven by induction: $$ \mbox{Lemma 1 : }\forall k \in \Bbb N : x^{\overline{k}} = \sum_n \left[\matrix{k\\n}\right]x^n $$

$$ \mbox{Lemma 2 : }\forall k \in \Bbb N : x^{\underline{k}} = (-1)^k (-x)x^{\overline{k}} $$

If we start with Lemma 1 and replace $x$ with $(-x)$ it becomes $$ (-x)^{\overline{k}} = \sum_n \left[\matrix{k\\n}\right](-x)^n \\ (-x)(-x+1)(-x+2)\cdots(-x+k-1) = \sum_n \left[\matrix{k\\n}\right](-1)^n x^n \\ (-1)^k (x)(x-1)(x-2)\cdots(x-k+1) = \sum_n \left[\matrix{k\\n}\right](-1)^n x^n \\ (x)(x-1)(x-2)\cdots(x-k+1) = \sum_n \left[\matrix{k\\n}\right](-1)^{n-k} x^n $$

$$ x^{\underline{k}} = \sum_n\left[\matrix{k\\n}\right](-1)^{k-n}x^n $$

I lied, we don't need lemma 2.

To prove lemma 1, note that it is true for $k=1$ because $x^1 = x = \left[ \matrix{1\\1}\right] x^1 = 1\cdot x$. Then assuming it is true for all $j < k$, $$ x^{\overline{k-1}} = \sum_n \left[\matrix{k-1\\n}\right]x^n \\ (x+k-1) x^{\overline{k-1}} = (x+k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + (x)\sum_n \left[\matrix{k-1\\n}\right]x^n \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + \sum_n \left[\matrix{k-1\\n}\right]x^{n+1} \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + \sum_m \left[\matrix{k-1\\m-1}\right]x^{m} \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + \sum_n \left[\matrix{k-1\\n-1}\right]x^{n} \\ x^{\overline{k}} = \sum_n \left((k-1)\left[ \matrix{k-1\\n}\right] + \left[\matrix{k-1\\n-1}\right]\right)x^{n} $$ and since $ \left[\matrix{k\\n}\right] =(k-1) \left[ \matrix{k-1\\n}\right] + \left[\matrix{k-1\\n-1}\right]$

$$ x^{\overline{k}} = \sum_n \left[\matrix{k\\n}\right]x^{n} $$

which establishes induction and proves lemma 1, thus proving the result stated at the start of this answer.

$\endgroup$
  • $\begingroup$ But I still don't get how to express [k n] (imagine k is written over n) explicitly, not recursively as you used it in your proof. $\endgroup$ – Barbra Aug 20 at 17:25
  • 1
    $\begingroup$ There is no closed form expression for $\left[ \matrix{k\\n}\right]$ analogous to expressing the binomial coefficients as fractions involving three factorials. That should not bother you too much; strictly speaking, you could say there is no closed form expression for $n!$ and it is "only" defined recursively, but the notation $n!$ bothers nobody. $\endgroup$ – Mark Fischler Aug 20 at 21:40

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.