What is the simplified form of the sum with changed variables?

[benorin]

I think I should know this already, but I don't; yet I need it, so would you please help me sum this...

\sum_{n=k}^{\infty} \left(\begin{array}{c}n\\k\end{array}\right) \left( \frac{-z}{1-z}\right) ^{n} = (1-z)(-z)^{k}

 

[Hurkyl]

It's surely easier to look at:

<br /> f(x) = \sum_{n=k}^{+\infty} \binom{n}{k} x^n<br />

This is one of the basic combinatorial identities, but I must admit that I have forgotten it, and do not recall how to derive it.

Hrm, maybe comparing f(x) to the integral of f(x)/x will help?

Also, I notice that the k-th derivative of x^n is:

<br /> \left(\frac{d}{dx}\right)^k \left( x^n \right) = \frac{k!}{x^k} \binom{n}{k} x^n<br />

Oh, I think that does it. (Note that, in your sum, you may assume that n ranges over all nonnegative integers)

 

[AKG]

I was first thinking to look at derivatives of the left-hand side, and show that it too is a polynomial of degree k+1 with 0 being a zero of order k, but having no other zeroes where its defined (since its other zero would have to be at 1, but it's not defined there). However, the derivatives just got messy, so I couldn't make this work. The other idea was to express 1/(1-z) on the left as (1 + z + z² + ...). That turns the series on the left into a power series in z. It's easy to check that the resulting power series has 0's for coefficients of all powers of z before the k^th power. It's easy to check also that the k^th power of z has coefficient (-1)^k and that the k+1^th power of z has coefficient (-1)^k+1.

Somehow, you want to show that the rest have coefficient zero as well. Perhaps you can find a general expression for the j^th coefficient in terms of previous coefficients, and solve by method of undetermined coefficients (inductively assuming something about the coefficients). Or maybe you can deal with the derivatives and show that the k+2^th derivative is identically 0.

 

[benorin]

Thanx Hurkyl!

 

[AKG]

Never mind, Hurkyl's way works better. Change variables x = -z/(1-z).

\sum_{n=k}^{\infty} {{n}\choose{k}} \left( \frac{-z}{1-z}\right) ^n

= \sum_{n=0}^{\infty}{{n}\choose{k}} \left( \frac{-z}{1-z}\right) ^n

= \sum_{n=0}^{\infty}{{n}\choose{k}} x^n

= \frac{x^k}{k!}\sum_{n=0}^{\infty}\frac{k!}{x^k}{{n}\choose{k}} x^n

= \frac{x^k}{k!}\sum_{n=0}^{\infty}\left(\frac{d}{dx}\right)^k(x^n)

= \frac{x^k}{k!}\left(\frac{d}{dx}\right)^k\sum_{n=0}^{\infty}x^n

= \frac{x^k}{k!}\left(\frac{d}{dx}\right)^k\left(\frac{1}{1-x}\right)