Analysis of Algorithms : An Active Learning Approach

1.3 MATHEMATICAL BACKGROUND 17

Equation 1.12 just shows that adding the numbers from N down to 0 is the
same as adding the numbers from 0 up to N. In some cases, it will be easier to
solve equations if we can apply Equation 1.12.

(1.13)

(1.14)

(1.15)

Equation 1.15 is easy to remember if you consider pairing up the values.
Matching the first and last, second and second last, and so on gives you a set of
values that are all N + 1. How many of these N + 1 totals do you get? Well,
you get half of the number of values you started with before you paired them,
orN / 2. So, the result is

(1.16)

(1.17)

Equation 1.17 is easy to remember if you consider binary numbers. When
you add the powers of 2 from 0 to 10, this is the same as the binary number

11111111111. If we add 1 to this number, we get 100000000000, which is
211. But because we added 1 to it, it is 1 larger than the sum of the powers of
2 from 0 to 10, so the sum must be 2^11
1. If we now substitute N for 10, we
get Equation 1.17.

, for some number A (1.18)

(1.19)

1

i=1

N

∑ = N

C

i=1

N

∑ = C * N

i

i=1

N

∑

NN()+ 1

= ----------------------- 2

N

---- 2 ()N+ 1

NN()+ 1

= ----------------------- 2

i^2

i=1

N

∑

NN()+ 1 () 2 N+ 1

--------------------------------------------- 6 -

2 N^3 ++ 3 N^2 N

==-------------------------------------- 6

2 i

i=0

N

∑^2

= N+1– 1

Ai

i=1

N

∑

AN+1– 1

A– 1

= ---------------------

i 2 i

i=1

N

∑ ()N–^12

= N+1+ 2