# Combinatorics: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n

#### micromass

OK, but that solves it right? I don't get why you say "special case"? I'll write it here for future reference:

You need to find

$$\sum_{k=0}^n \binom{n+k}{n} \frac{1}{2^{n+k}}$$

Multiply by $4^n/4^n$ to get

$$\frac{1}{4^n} \sum_{k=0}^n \binom{n+k}{n} 2^{n-k}$$

Apply the relation $2^a = \sum_{j=0}^a \binom{a}{j}$ to get

$$\frac{1}{4^n} \sum_{k=0}^n \binom{n+k}{n} \sum_{j=0}^{n-k} \binom{n-k}{j}$$

Switching around the sums and allowing the convention that if $\binom{a}{b}=0$ if $b>a$, we get

$$\frac{1}{4^n} \sum_{j=0}^n \sum_{k=0}^n \binom{n-k}{j}\binom{n+k}{n}$$

the relation in Knuth is

$$\sum_{k=0}^l \binom{l-k}{m}\binom{q+k}{n} = \binom{l+q+1}{m+n+1}$$

Thus we get

$$\frac{1}{4^n} \sum_{j=0}^n \binom{2n+1}{j+n+1}$$

Change variables $l=j+n+1$:

$$\frac{1}{4^n} \sum_{l=n+1}^{2n+1} \binom{2n+1}{l}$$

Applying that $\binom{2n+1}{l} = \binom{2n+1}{2n+1-l}$, we see that

$$\frac{1}{2^{2n-1}} \sum_{l=0}^{2n+1} \binom{2n+1}{l}$$

Again applying $2^a = \sum_{j=0}^a \binom{a}{j}$, we see that this is equal to

$$\frac{1}{2^{2n+1}}2^{2n+1} = 1$$

Last edited:

Gold Member
Thanks again, micromass. Yes, the phrase "a special case" was misplaced; I was being overly careful before I had seen the reference in Knuth et al. (I have in fact not yet obtained a copy, so I still need to look at it.) Apparently, as you say, this now solves it, and your exposition is nice and clear -- except that I think you left something out in the line
"Applying that $\binom{2n+1}{l} = \binom{2n+1}{l}$, we see that..."

Last edited:

#### micromass

Thanks again, micromass. Yes, the phrase "a special case" was misplaced; I was being overly careful before I had seen the reference in Knuth et al. (I have in fact only got a copy of it a few minutes ago, so I still need to look at it.) Apparently, as you say, this now solves it, and your exposition is nice and clear -- except that I think you left something out in the line
"Applying that $\binom{2n+1}{l} = \binom{2n+1}{l}$, we see that..."
Thank you, that was a typo. Well, all that remains is proving the relation in Knuth, which is not done there. I think an induction proof works, but I don't like that. Consider the function

$$f_n(x) = \frac{x^n}{(1-x)^{n+1}}$$

We know the binomial series

$$\frac{1}{(1-x)^{n+1}} = \sum_{k=0}^{+\infty} \binom{k+n}{n} x^k$$

Thus

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

with the usual convention that $\binom{k}{n} = 0$ if $n>k$

Thus $xf_n(x)f_m(x) = f_{n+m+1}(x)$. By the Cauchy product of series, we then see that

$$\sum_{k=-1}^{+\infty} \binom{k+1}{n+m+1} x^k = \sum_{k=0}^{+\infty} x^k \sum_{j=0}^k \binom{j}{n}\binom{k-j}{m}$$

Thus we see the identity (with additionally substituting $t=k$

$$\sum_{j=0}^k \binom{j}{n}\binom{t-j}{m} = \binom{t+1}{n+m+1}$$

Substituting $j=l-k$, we get

$$\sum_{k=0}^{l-k} \binom{l-k}{n}\binom{t-l+k}{m} = \binom{t+1}{n+m+1}$$

The result now follows after substiting $q=t-l$.

Gold Member
Excellent! Thanks so very much. Yes, I finally got hold of Knuth and was surprised not to find a derivation for the the principle in question. So your explanation definitely fills a gap, completing the answer to my question. I am very grateful.

#### micromass

Excellent! Thanks so very much. Yes, I finally got hold of Knuth and was surprised not to find a derivation for the the principle in question. So your explanation definitely fills a gap, completing the answer to my question. I am very grateful.
Haha, I should be the one grateful here! It was fun and I learned some new techniques! If you have any more of these threads, be sure to shoot me a PM so I can join in the fun

"Combinatorics: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving