Proof of combo formula using analytical NT

claim: a=0n(a+kk)=(n+k+1k+1)\sum_{a=0}^n \binom{a+k}{k}=\binom{n+k+1}{k+1} (wierd) proof: Consider Induction on: fk(pa)=(11111k times)(pn)=(k+nk)f_k(p^a)=(\underbrace{1*1*1*1*1\cdots}_{k\text{ times}})(p^n)=\binom{k+n}{k} then fk+1(pa)=(11111k times1)(pn)=papn(k+ak)=a=0n(k+ak)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 (11111k times1)(pn)=(k+n+1k+1)(\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: ζk(s)=i=1fk(i)is=pa=0(k+ak)pas=p1k!a=0(a+1)(a+2)...(a+k)(ps)a\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 a=0(a+1)(a+2)...(a+k)xa=k!(1x)k\sum_{a=0}^\infty (a+1)(a+2)...(a+k)x^a=\dfrac{k!}{(1-x)^k} Putting this in the product: ζk(s)=p1(1ps)k=ζk(s)\zeta^k(s)=\prod_p \dfrac{1}{(1-p^{-s})^k}=\zeta^k(s) s=ss=s Hence proved.

Note by Aareyan Manzoor
3 years, 9 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Looks like your claim is a corollary of this. By the way, the proof was interesting :).

Karthik Venkata - 3 years, 9 months ago

Log in to reply

never seen that before

Aareyan Manzoor - 3 years, 9 months ago

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.

Karthik Venkata - 3 years, 9 months ago

Log in to reply

Feel free to fill out the "exercise for reader" in the comment.

Aareyan Manzoor - 3 years, 9 months ago

Log in to reply

Actually, I initially derived 11...1 Convoluted k times (pn)=(k+nk)1*1*...*1 \text{ Convoluted k times }(p^n) = \binom{k+n}{k} by proving via induction that 11...1 Convoluted k times (pn)=0a1a2...akn11*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 - 3 years, 9 months ago

Log in to reply

Use \substack ;)

Jake Lai - 3 years, 9 months ago

Log in to reply

Initially i derivd 1111....k times(pa)=(a+1)(a+2)(a+3)...(a+k)k!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 - 3 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...