| Revision as of 18:46, 10 July 2002 editToby Bartels (talk | contribs)Administrators8,858 editsm Presumably will be defined there when written.← Previous edit | Revision as of 23:45, 24 August 2002 edit undoLC~enwiki (talk | contribs)950 edits first draftNext edit → | ||
| Line 1: | Line 1: | ||
| A '''sum''' is the addition of two or more ]s (see ]). A sum of several terms is usually written using plus symbols (+). A sum with many terms is often written using a capital sigma, which is defined as: | |||
| #REDIRECT ] | |||
| ''b'' | |||
| ∑ ''f''(''i'') = ''f''(''a'') + ''f''(''a''+1) + ''f''(''a''+2) + ... + ''f''(''b''-1) + ''f''(''b'') | |||
| ''i''=''a'' | |||
| The following are useful identities: | |||
| ''n'' | |||
| ∑ ''i'' = ''n''(''n''+1)/2 | |||
| ''i''=1 | |||
| ''n'' | |||
| ∑ ''i''<sup>2</sup> = (2''n''<sup>3</sup>+3''n''<sup>2</sup>+''n'')/6 | |||
| ''i''=0 | |||
| ''n'' | |||
| ∑ ''x''<sup>''i''</sup> = (''x''<sup>''n''+1</sup> -1) / (''x''-1) | |||
| ''i''=0 | |||
| ∞ | |||
| ∑ ''x''<sup>''i''</sup> = 1 / (1-''x'') | |||
| ''i''=0 | |||
| ''n''-1 / ''i'' \ / ''n'' \ | |||
| ∑ | | = | | (see ]) | |||
| ''i''=0 \ ''k'' / \ ''k''+1 / | |||
| The following are useful approximations (using ]): | |||
| ''n'' | |||
| ∑ ''i''<sup>''c''</sup> = Θ(''n''<sup>''c''+1</sup>) for every real constant ''c'' ≠ -1. | |||
| ''i''=1 | |||
| ''n'' | |||
| ∑ 1/''i'' = Θ(log(''n'')) | |||
| ''i''=1 | |||
| ''n'' | |||
| ∑ ''c''<sup>''i''</sup> = Θ(''c''<sup>''n''</sup>) for every real constant ''c''. | |||
| ''i''=1 | |||
| ''n'' | |||
| ∑ log(''i'')<sup>''c''</sup> = Θ(''n'' log(''n'')<sup>''c''</sup>) for every real constant ''c'' ≥ 0. | |||
| ''i''=1 | |||
| ''n'' | |||
| ∑ log(''i'')<sup>''c''</sup> ''i''<sup>''d''</sup> = Θ(''n''<sup>''d''+1</sup> log(''n'')<sup>''c''</sup>) for all real constants ''c'' ≥ 0 and ''d'' ≥ 0. | |||
| ''i''=1 | |||
| ''n'' | |||
| ∑ log(''i'')<sup>''c''</sup> ''i''<sup>''d''</sup> ''b''<sup>''i''</sup> = Θ(''n''<sup>''d''</sup> log(''n'')<sup>''c''</sup> ''b''<sup>''n''</sup>) for all real constants ''c'' ≥ 0, ''d'' ≥ 0 and ''b'' > 1. | |||
| ''i''=1 | |||
Revision as of 23:45, 24 August 2002
A sum is the addition of two or more numbers (see arithmetic). A sum of several terms is usually written using plus symbols (+). A sum with many terms is often written using a capital sigma, which is defined as:
b ∑ f(i) = f(a) + f(a+1) + f(a+2) + ... + f(b-1) + f(b) i=a
The following are useful identities:
n ∑ i = n(n+1)/2 i=1
n ∑ i = (2n+3n+n)/6 i=0
n ∑ x = (x -1) / (x-1) i=0
∞ ∑ x = 1 / (1-x) i=0
n-1 / i \ / n \ ∑ | | = | | (see binomial coefficient) i=0 \ k / \ k+1 /
The following are useful approximations (using theta notation):
n ∑ i = Θ(n) for every real constant c ≠ -1. i=1
n ∑ 1/i = Θ(log(n)) i=1
n ∑ c = Θ(c) for every real constant c. i=1
n ∑ log(i) = Θ(n log(n)) for every real constant c ≥ 0. i=1
n ∑ log(i) i = Θ(n log(n)) for all real constants c ≥ 0 and d ≥ 0. i=1
n ∑ log(i) i b = Θ(n log(n) b) for all real constants c ≥ 0, d ≥ 0 and b > 1. i=1