• Summe der ersten n natürlichen Zahlen (Der kleine Gauß ) n X i= i=1 n(n + 1) 2 • Summe der ersten n ungeraden natürlichen 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ätzung ln n < Hn < (ln n) + 1, also ist Hn ∈ Θ(log n). 1 • Fakultätsfunktion. Bei der Analyse von Algorithmen kommt gelegentlich die Fakultätsfunktion vor, für 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ätzung erlaubt sogar n! ∈ 1 n n+ 2 Θ e uns genügt aber meist erstere. Version vom 21. Oktober 2015 2
© Copyright 2024 ExpyDoc
