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

  • Thread starter nomadreid
  • Start date
21,960
3,264
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

[tex]\sum_{k=0}^n \binom{n+k}{n} \frac{1}{2^{n+k}}[/tex]

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

[tex]\frac{1}{4^n} \sum_{k=0}^n \binom{n+k}{n} 2^{n-k}[/tex]

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

[tex]\frac{1}{4^n} \sum_{k=0}^n \binom{n+k}{n} \sum_{j=0}^{n-k} \binom{n-k}{j}[/tex]

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

[tex]\frac{1}{4^n} \sum_{j=0}^n \sum_{k=0}^n \binom{n-k}{j}\binom{n+k}{n}[/tex]

the relation in Knuth is

[tex]\sum_{k=0}^l \binom{l-k}{m}\binom{q+k}{n} = \binom{l+q+1}{m+n+1}[/tex]

Thus we get

[tex]\frac{1}{4^n} \sum_{j=0}^n \binom{2n+1}{j+n+1}[/tex]

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

[tex]\frac{1}{4^n} \sum_{l=n+1}^{2n+1} \binom{2n+1}{l}[/tex]

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

[tex]\frac{1}{2^{2n-1}} \sum_{l=0}^{2n+1} \binom{2n+1}{l}[/tex]

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

[tex]\frac{1}{2^{2n+1}}2^{2n+1} = 1[/tex]
 
Last edited:

nomadreid

Gold Member
1,253
81
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:
21,960
3,264
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

[tex]f_n(x) = \frac{x^n}{(1-x)^{n+1}}[/tex]

We know the binomial series

[tex]\frac{1}{(1-x)^{n+1}} = \sum_{k=0}^{+\infty} \binom{k+n}{n} x^k[/tex]

Thus

[tex]f_n(x) = \sum_{k=0}^{+\infty} \binom{k}{n} x^k[/tex]

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

[tex]\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}[/tex]

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

[tex]\sum_{j=0}^k \binom{j}{n}\binom{t-j}{m} = \binom{t+1}{n+m+1}[/tex]

Substituting ##j=l-k##, we get

[tex]\sum_{k=0}^{l-k} \binom{l-k}{n}\binom{t-l+k}{m} = \binom{t+1}{n+m+1}[/tex]

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

nomadreid

Gold Member
1,253
81
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.
 
21,960
3,264
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 :biggrin:
 

Want to reply to this thread?

"Combinatorics: 1= ((n+k)Cr)*((1/2)^(n+k)) from k = 0 to n" You must log in or register to reply here.

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

Latest threads

Top