Sums!

∑n=1k(−1)n+1(kn)∑1≤i≤j≤n1ij=1k2 \large \displaystyle\sum _{ n=1 }^{ k }{ { (-1) }^{ n+1 } } \dbinom{ k }{ n }\displaystyle\sum _{ 1\le i\le j\le n }{ \dfrac { 1 }{ ij } } =\dfrac { 1 }{ { k }^{ 2 } }

Prove the equation above.

This is a part of the set Formidable Series and Integrals

#Combinatorics

Note by Hamza A
5 years, 3 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} ai−1 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

For this solution, take (nk)=0\displaystyle \binom{n}{k} = 0 if k>nk>n.

Lemma 1: ∑k=1n∑i=1k1ik=∑i=1n(−1)i+1i2(ni) \displaystyle \sum _{k=1}^{n} \sum _{i=1}^{k} \frac {1}{ik} = \sum_{i=1}^n\frac{\left(-1\right)^{i+1}}{i^2}\binom{n}{i}

Proof: ∑k=1n∑i=1k1ik=∑k=1n1k∑i=1k1i=∫01∑k=1n1k∑i=1kxi−1dx=∫011x−1∑k=1n1k(xk−1)dx=∫011u∑k=1n1k(1−(1−u)k)du=∫011u∑k=1n1k(1−∑i=0k(−1)i(ki)ui)du=∑k=1n1k∫01(∑i=1k(−1)i+1(ki)ui−1)du=∑k=1n1k∑i=1k(−1)i+1i(ki)=∑k=1n1k∑i=1n(−1)i+1i(ki)=∑i=1n(−1)i+1i∑k=1n1k(ki)=∑i=1n(−1)i+1i2∑k=1n(k−1i−1)=∑i=1n(−1)i+1i2∑k=in(ki)−(k−1i)=∑i=1n(−1)i+1i2(ni) \begin{aligned} \sum_{k=1}^n\sum_{i=1}^k\frac{1}{ik} &= \sum_{k=1}^n\frac{1}{k}\sum_{i=1}^k\frac{1}{i} \\ &= \int_0^1\sum_{k=1}^n\frac{1}{k}\sum_{i=1}^kx^{i-1}dx \\ &= \int_0^1\frac{1}{x-1}\sum_{k=1}^n\frac{1}{k}\left(x^k-1\right)dx \\ &= \int_0^1\frac{1}{u}\sum_{k=1}^n\frac{1}{k}\left(1-\left(1-u\right)^k\right)du \\ &= \int_0^1\frac{1}{u}\sum_{k=1}^n\frac{1}{k}\left(1-\sum_{i=0}^k\left(-1\right)^i\binom{k}{i}u^i\right)du \\ &= \sum_{k=1}^n\frac{1}{k}\int_0^1\left(\sum_{i=1}^k\left(-1\right)^{i+1}\binom{k}{i}u^{i-1}\right)du \\ &= \sum_{k=1}^n\frac{1}{k}\sum_{i=1}^k\frac{\left(-1\right)^{i+1}}{i}\binom{k}{i} \\ &= \sum_{k=1}^n\frac{1}{k}\sum_{i=1}^n\frac{\left(-1\right)^{i+1}}{i}\binom{k}{i} \\ &= \sum_{i=1}^n\frac{(-1)^{i+1}}{i}\sum_{k=1}^n\frac{1}{k}\binom{k}{i} \\ &= \sum_{i=1}^n\frac{\left(-1\right)^{i+1}}{i^2}\sum_{k=1}^n\binom{k-1}{i-1}\\ &= \sum_{i=1}^n\frac{\left(-1\right)^{i+1}}{i^2}\sum_{k=i}^n\binom{k}{i}-\binom{k-1}{i} \\ &= \sum_{i=1}^n\frac{\left(-1\right)^{i+1}}{i^2}\binom{n}{i} \end{aligned}

So: \begin{aligned} \sum_{n=1}^k(-1)^{n+1}\binom{k}{n}\sum_{1\le i\le j\le n}\frac{1}{ij} &= \sum_{n=1}^k(-1)^{n+1}\binom{k}{n}\sum_{i=1}^n\frac{(-1)^{i+1}}{i^2}\binom{n}{i} \\ &= \sum_{n=1}^k(-1)^{n+1}\binom{k}{n}\sum_{i=1}^k\frac{(-1)^{i+1}}{i^2}\binom{n}{i} \\ &= \sum_{i=1}^k\frac{(-1)^{i}}{i^2}\sum_{n=1}^k(-1)^{n}\binom{k}{n}\binom{n}{i} \\ &= \sum_{i=1}^k\frac{(-1)^i}{i^2}\sum_{n=0}^{k-1}(-1)^{k-n}\binom{k}{k-n}\binom{k-n}{i} \\ &= \sum_{i=1}^k\frac{(-1)^i}{i^2}\sum_{n=0}^{k-1}(-1)^{k-n}\binom{k}{k-n}\binom{k-n}{i} \\ &= \sum_{i=1}^k\frac{(-1)^i}{i^2}\sum_{n=0}^{k-1}(-1)^{k-n}\binom{k}{i}\binom{k-i}{n} \\ &= \sum_{i=1}^k\frac{(-1)^i}{i^2}\binom{k}{i}\sum_{n=0}^{k-1}(-1)^{k-n}\binom{k-i}{n} \\ &= \sum_{i=1}^k\frac{(-1)^i}{i^2}\binom{k}{i}\sum_{n=0}^{k-i}(-1)^{k-n}\binom{k-i}{n} \\ &= \sum_{i=1}^k\frac{(-1)^i}{i^2}\binom{k}{i}\begin{Bmatrix} 0 & \text{ if } i<k \\ (-1)^k & \text{ if }i=k \end{Bmatrix} \\ &= \left \frac{(-1)^{i}}{i^{2}}\binom{k}{i}\right|_{i=k}(-1) ^{k} \\ &= \frac{1}{k^2} \end{aligned} If the above LaTeX has problems rendering, refer to the bottom image:

Note that what I did in this proof is essentially a binomial transform.

Julian Poon - 2 years, 7 months ago
×

Problem Loading...

Note Loading...

Set Loading...