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
5 years, 4 months ago
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Looks like your claim is a corollary of this. By the way, the proof was interesting :).
Log in to reply
never seen that before
Log in to reply
I came across it while spending time with simple binomial sums, and thought that would make a good problem on brilliant.
Feel free to fill out the "exercise for reader" in the comment.
Actually, I initially derived 1∗1∗...∗1 Convoluted k times (pn)=(kk+n) by proving via induction that 1∗1∗...∗1 Convoluted k times (pn)=0≤a1≤a2...≤ak≤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
Log in to reply
Use \substack ;)
Initially i derivd 1∗1∗1∗1....k times(pa)=k!(a+1)(a+2)(a+3)...(a+k) which i turned into binomial coefficient later.
There are obviously easier proof.... This was intended as a more interesting/wierd proof.