Suma $\sum_{k=0}^{n}\frac{1}{k+1} \binom{n}{k} = \frac{1}{n+1}(2^{n+1} - 1)$

[Martin Sleziak]

Dostal som mailom otázku k tejto úlohe:

Dokážte: $$\sum_{k=0}^{n}\frac{1}{k+1} \binom{n}{k} =
\frac{1}{n+1}(2^{n+1} - 1).$$

Je to úloha 3a z 07cvicenie_cesty.pdf

Tu je nejaká linka, kde sa dá nájsť riešenie na internete:
* How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k}$?
Túto sa mi podarilo nájsť ako prvú.

Zatiaľ napíšem stručný hint a neskôr sa skúsim doplniť detailnejšie riešenie. (Samozrejme, ak sa nájde niekto iný, kto sem napíše riešenie, budem len rád.)

Hint 1: Vedeli by ste upraviť výraz $\frac{1}{k+1} \binom{n}{k}$ tak, aby ste tam dostali iný binomický koeficient?

Spoiler:

Snažte sa ho upraviť na tvar $\frac1{n+1}\binom{n+1}{k+1}$.

(Skúste si spomenúť, ak sme niečo podobné robili na cviku.)

Hint 2: Ak už ste ten binomický koeficient upravili, pomôže vám to nejako pri vyjadrení celej sumy?