Discovered series result

[BruceZ]

Sometimes a probability problem affords one solution by some general mathematical technique, and another solution purely from probability considerations, and this provides insight into a general mathematical problem. I just stumbled upon such a problem which enables me to sum the following series:

sum{n = k to infinity} C(n,k)*x^n = (x^k)/(1-x)^(k+1)

for 0 < x < 1.

At first glance this may appear to be a more familiar series, until you realize that k is held constant, and the sum is over n. Do not confuse this with the more familiar binomial expansion in which n is constant and the sum is over k.

Can you prove this? Is this series result well-known? Will I be famous? [img]/images/graemlins/smile.gif[/img]

[jay_shark]

This is my kind of problem .

It seems like a very interesting result and I haven't seen it anywhere .

I could be wrong but it looks as if this problem relates to gamblers ruin . Substitute x=q and 1-x = p

[jason1990]

Differentiate the power series for 1/(1-x) k times and multiply both sides by x^k/k!

[jay_shark]

Jason , there has to be a better way .

I always try to look for elegant solutions to complex problems . This one has a nice solution to it .

[jason1990]

Okay then. FWIW, that solution is elegant to me. It's 4 lines long on my scratch paper and I think it would make a nice example for one of my undergraduate classes. I'm sure Bruce's probabilistic interpretation is neat too. I like your posts, so I look forward to seeing what you come up with.

[f97tosc]

sum{n = k to infinity} C(n,k)*x^n =
= {reindex} =

sum{n = 0 to infinity} C(n+k,k)*x^(n+k) =

x^k sum{n = 0 to infinity} C(n+k,k)*x^n =

x^k sum{n = 0 to infinity} C(n+k,(n+k)-k)*x^n =

x^k [sum{n = 0 to infinity} C(n+k,n)*x^n ]

I hadn't seen the sum in the brackets before but it was listed at Wikipedia to be:

sum{n = 0 to infinity} C(n+k,n)*x^n = 1/(1-x)^(k+1)

The stated result follows.

[jay_shark]

I couldn't think of a probabilistic argument to show this .

Bruce , do you mind sharing to us your solution?

[AaronBrown]

Suppose I have a biased coin with probability x (0 < x < 1) of coming up heads. I flip it and count the number of tails after each flip until I get k+1 tails. On average, how many times will I flip the coin after a count of exactly k tails?

Clearly this answer does not depend on k. None of the flips matter until I hit k tails. Once I do, the probability is x that I get only one flip, x*(1-x) that I get two flips and so on. The expected number is x + x*(1-x) + x*(1-x)^2 + . . . = 1/(1-x).

I can also represent this amount by summing the probability of having exactly k tails after n flips for n = 0 to infinity since the expectation of a sum is the sum of the expectations. This probability is clearly zero for n < k, so I have:

sum{n = k to infinity} C(n,k)*x^(n-k)*(1-x)^k

which must equal 1/(1-x).

If I multiply both sides by [x/(1-x)]^k, I get BruceZ's result.

[jay_shark]

Aaron your posts are always very insightful and I always look forward to what you have to say .

However , x+x*(1-x)+x*(1-x)^2+.... = x/(1-(1-x)) which is just a geometric series with first term x and a common ratio of (1-x) . The Rhs is 1 and not 1/(1-x) like you mentioned .

[AaronBrown]

Good catch jay_shark. I actually solved it with x and (1-x) reversed, then screwed up the transcription. The real series should be 1 + x + x^2 + . . . which does indeed equal 1/(1-x). You're sure to get one flip with k tails, if that is a head (probability x) you'll get a second, if the first two are heads (probability x^2) you'll get a third, and so on.