Homework Help: This ought to be an easy sum

1. Apr 30, 2006

benorin

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

2. Apr 30, 2006

Hurkyl

Staff Emeritus
It's surely easier to look at:

$$f(x) = \sum_{n=k}^{+\infty} \binom{n}{k} x^n$$

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:

$$\left(\frac{d}{dx}\right)^k \left( x^n \right) = \frac{k!}{x^k} \binom{n}{k} x^n$$

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

Last edited: Apr 30, 2006
3. Apr 30, 2006

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 kth power. It's easy to check also that the kth power of z has coefficient (-1)k and that the k+1th 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 jth 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+2th derivative is identically 0.

4. Apr 30, 2006

benorin

Thanx Hurkyl!

5. Apr 30, 2006

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)$$