I am reading up on combinatorics for an under graduate summer internship in mathematics. But I am in Computer Science. The book that I am using is "Combinatorics and Graph Theory" by John Harris and folks. There's an exercise that is stumping me, and maybe you guys can point me in the right direction. Here goes,
Problem 14.
Let $\triangle$ be the difference operator: $$\triangle(f(x)) = f(x+1) – f(x).$$
Show that, $$\triangle(x^\underline{n}) = nx^\underline{n-1},$$
and use this to prove, $$\sum_{k=0}^{m-1} k^\underline{n}= \frac{m^\underline{n+1}}{n+1}.$$
Now I know that the falling factorial is defined as, $$x^\underline{k} = x(x-1)(x-2)…(x-k+1).$$
Also, I know that this function returns to us the amount of k-element ordered lists from a collection of n different objects.
I have gotten up to here so far,
$$\triangle(x^\underline{n}) = (x+1)^\underline{n} – x^\underline{n}$$
$$=(x+1)x(x-1)(x-2)…[(x+1) – (n-1)] – x(x-1)(x-2)…(x-n+1)$$
rearranging that,
$$=x(x-1)(x-2)…(x-n+1)(x-n+2)(x+1) – x(x-1)(x-2)…(x-n+1)$$
$$=x(x-1)(x-2)…(x-n+1)[(x-n+2)(x+1)-1]$$
$$=x^\underline{n}[(x-n+2)(x+1) – 1].$$
And this guys is where I get lost, because I am tempted to manipulate the above product using the laws of exponents…but to my understanding, $x^\underline{n}$ isn't a power of x (or is it?). I am confused.
Thank you all!
Best Answer
You made a mistake when taking $x(x-1)\dots(x-k+1)$ as a common factor, when in fact there is no $(x-k+1)$ in $(x+1)^{\underline {n}}$: $$(x+1)^{\underline{n}} - x^{\underline n} = (x+1)\color{blue}{x(x-1)\dots(x-n+2)} \color{black}{-} \color{blue}{x(x-1)\dots(x-n+2)}\color{black}{(x-n+1)}$$ Then we take the common factor: $$x^{\underline{n-1}} ((x+1) - (x-n+1)) = n x^{\underline{n-1}}$$