Homework 1

Handed out September 9, 2011. Due within the first 15 minutes of class September 22, 2011.

Note: You may discuss homework problems and general solution strategies with classmates. However, you must write up the solutions yourself, and document any and all resources appropriately.¹

Problem 1.

Derive a closed form solution for the following summation using constructive induction assuming that $n\geq 0$.

$$\sum_{i=0}^{n} i^3$$

Problem 2.

Prove by mathematical induction on $n$, where $n\geq 0$:

$$\sum_{i=0}^{n} (i+1)\; i \;(i-1) = {\left (\frac{n(n+1)}{2}\right )}^2 - {\frac {n(n+1)}{2}}$$

Problem 3.

The product of two $n \times n$ matrices $A*B$ is defined to be the $n \times n$ matrix C where

$$c_{ij} = \sum_{k=0}^{n-1} a_{ik} b_{kj}.$$

a.

Write pseudo code to multiply two nxn matices.

b.

Use a triple sum to count the number of multiplications.

c.

Simplify the summation.

d.

Use a triple sum to count the number of additions. Simplify the summation.

Problem 4

Consider a slightly different matrix multiplcation problem. Assume that U is an $n \times n$ upper triangular matrix, where the entries below the diagonal are always zero. That is, for $i > j$, the value of $u_{ij} \equiv 0$. Assume that L is an $n \times n$ lower triangular matrix, in which the entries above the diagonal are all zero. That is, for $i<j$, the value of $l_{ij}\equiv 0$.

a.

Write psuedo code to (efficiently) multiply an nxn upper triangular matrix, U, by an nxn lower triangular matrix, L.

b.

Use a triple sum to count the number of multiplications.

c.

Simplify the summation.

d.

Use a triple sum to count the number of additions. Simplify the summation.