Waste less time on Facebook — follow Brilliant.
×

Proof of combo formula using analytical NT

claim: \[\sum_{a=0}^n \binom{a+k}{k}=\binom{n+k+1}{k+1}\] (wierd) proof: Consider Induction on: \[f_k(p^a)=(\underbrace{1*1*1*1*1\cdots}_{k\text{ times}})(p^n)=\binom{k+n}{k}\] then \[f_{k+1}(p^a)=(\underbrace{1*1*1*1*1\cdots}_{k\text{ times}}*1)(p^n)=\sum_{p^a|p^n}\binom{k+a}{k}=\sum_{a=0}^n \binom{k+a}{k}\] If our original claim is true, then \[(\underbrace{1*1*1*1*1\cdots}_{k\text{ times}}*1)(p^n)=\binom{k+n+1}{k+1}\] Now i am going to use dirichlet series to prove this to be true: \[\zeta^k(s)=\sum_{i=1}^\infty \dfrac{f_k(i)}{i^s}\\=\prod_{p}\sum_{a=0}^\infty \dfrac{\binom{k+a}{k}}{p^{as}}=\prod_{p}\dfrac{1}{k!}\sum_{a=0}^\infty \dfrac{(a+1)(a+2)...(a+k)}{(p^{s})^a}\] By continuously differentiating a version of GP(exercise for the reader), we have \[\sum_{a=0}^\infty (a+1)(a+2)...(a+k)x^a=\dfrac{k!}{(1-x)^k}\] Putting this in the product: \[\zeta^k(s)=\prod_p \dfrac{1}{(1-p^{-s})^k}=\zeta^k(s)\] \[s=s\] Hence proved.

Note by Aareyan Manzoor
7 months, 3 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Looks like your claim is a corollary of this. By the way, the proof was interesting :). Karthik Venkata · 7 months, 3 weeks ago

Log in to reply

@Karthik Venkata never seen that before Aareyan Manzoor · 7 months, 3 weeks ago

Log in to reply

@Aareyan Manzoor I came across it while spending time with simple binomial sums, and thought that would make a good problem on brilliant. Karthik Venkata · 7 months, 3 weeks ago

Log in to reply

Actually, I initially derived \[1*1*...*1 \text{ Convoluted k times }(p^n) = \binom{k+n}{k}\] by proving via induction that \[1*1*...*1 \text{ Convoluted k times }(p^n)=\sum_{0 \le a_1 \le a_2 ... \le a_{k} \le n}1\] and thereafter using the solution in this beautiful problem to evaluate the final answer.

So another alternative to proving the above identity is to just use that problem Julian Poon · 7 months, 3 weeks ago

Log in to reply

@Julian Poon Use \substack ;) Jake Lai · 7 months, 3 weeks ago

Log in to reply

@Julian Poon Initially i derivd \[1*1*1*1....\text{k times}(p^a)=\dfrac{(a+1)(a+2)(a+3)...(a+k)}{k!}\] which i turned into binomial coefficient later.

There are obviously easier proof.... This was intended as a more interesting/wierd proof. Aareyan Manzoor · 7 months, 3 weeks ago

Log in to reply

Feel free to fill out the "exercise for reader" in the comment. Aareyan Manzoor · 7 months, 3 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...