1.8 Evaluate the following sums:

i = 0 1 4 i

i=014i

i = 0 i 4 i

i=0i4i *

i = 0 i 2 4 i

i=0i24i **

i = 0 i N 4 i

1.11 Let Fi be the Fibonacci numbers as defined in Section 1.2. Prove the following:

N2i=1Fi=FN2i=1N2Fi=FN2

FN

** Give a precise closed-form expression for FN

2.10 Determine, for the typical algorithms that you use to perform calculations by hand, the running time to do the following:

Add two N-digit integers.

Multiply two N-digit integers.

Divide two N-digit integers.

2.22 Show that X62 can be computed with only eight multiplications.

Please nothing hand written.