Preview only show first 10 pages with watermark. For full document please download

• Summe Der Ersten N Natürlichen Zahlen (der Kleine Gauß) ∑ I = N

   EMBED

Share

Transcript

• Summe der ersten n nat¨ urlichen Zahlen (Der kleine Gauß ) n X i= i=1 n(n + 1) 2 • Summe der ersten n ungeraden nat¨ urlichen Zahlen n X (2i − 1) = n2 i=1 • Summe der ersten n Quadratzahlen n X i2 = i=1 n(n + 1)(2n + 1) 6 • Summe der ersten n Kubikzahlen n X  3 i = i=1 n(n + 1) 2 2 • Geometrische Reihe n X i=0 qi = q n+1 − 1 1 − q n+1 = q−1 1−q • Geometrische Reihe in leichter Variation (Start bei i = 1) n X qi = i=1 q n+1 − q q−1 • Reihe mit Binomialkoeffizienten n   X n n−k k a b = (a + b)n (a, b ∈ IR und n ∈ IN ) k k=0 • Spezialfall von eben mit a = b = 1 n   X n = 2n k k=0 • Harmonische Zahlen/Reihe. Mit Hn := n X 1 i=1 i wird die n-te Harmonische Zahl bezeichnet. Es gilt die Absch¨atzung ln n < Hn < (ln n) + 1, also ist Hn ∈ Θ(log n). 1 • Fakult¨ atsfunktion. Bei der Analyse von Algorithmen kommt gelegentlich die Fakult¨ atsfunktion vor, f¨ ur die die Stirlingische Formel gilt  n n √ n! ≈ 2πn e 1 dieser Wert ist um etwa 12n zu klein. Nutzt man dies noch, so kann man n leicht n! ∈ O(n ) sehen. Eine bessere Absch¨atzung erlaubt sogar n! ∈   1 n n+ 2 Θ e uns gen¨ ugt aber meist erstere. Version vom 21. Oktober 2015 2